Найти элемент в срезе/массиве линейным или бинарным поиском в Golang

Линейный поиск

В Go нет встроенной функции линейного поиска для срезов и массивов. Вот два примера реализации линейного поиска, которые вы можете использовать в качестве шаблонов.

// Find возвращает наименьший индекс i, 
// при котором x == a[i],
// или len(a), если такого индекса нет.
func Find(a []string, x string) int {
    for i, n := range a {
        if x == n {
            return i
        }
    }
    return len(a)
}

// Contains указывает, содержится ли x в a.
func Contains(a []string, x string) bool {
    for _, n := range a {
        if x == n {
            return true
        }
    }
    return false
}

Бинарный поиск

"Бинарный поиск быстрее линейного, но работает, только если ваши данные в порядке. Это сортировка." - Дэн Бентли

Если массив отсортирован, вы можете использовать бинарный поиск. Это будет намного эффективнее, поскольку бинарный поиск выполняется в наихудшем логарифмическом времени, делая O(log n) сравнений, где n - размер среза.

Существует три пользовательские функции бинарного поиска: sort.SearchInts, sort.SearchStrings или sort.SearchFloat64s.

Все они имеют сигнатуру

func SearchType(a []Type, x Type) int

и возвращают

• наименьший индекс i, при котором x <= a[i]
• или len(a), если такого индекса нет.

Срез должен быть отсортирован в порядке возрастания.

a := []string{"A", "C", "C"}

fmt.Println(sort.SearchStrings(a, "A")) // 0
fmt.Println(sort.SearchStrings(a, "B")) // 1
fmt.Println(sort.SearchStrings(a, "C")) // 1
fmt.Println(sort.SearchStrings(a, "D")) // 3

Общий бинарный поиск

Существует также универсальная функция бинарного поиска sort.Search.

func Search(n int, f func(int) bool) int

Она возвращает:

• наименьший индекс i, при котором f(i) истинно (равно true)
• или n, если такого индекса нет.

Требуется, чтобы f было false для некоторого (возможно, пустого) префикса входного диапазона, а затем true для остальной части.

Этот пример отражает предыдущий, но использует общую sort.Search вместо sort.SearchInts.

a := []string{"A", "C", "C"}
x := "C"

i := sort.Search(len(a), func(i int) bool { return x <= a[i] })
if i < len(a) && a[i] == x {
    fmt.Printf("Найдено %s по индексу %d в %v.\n", x, i, a)
} else {
    fmt.Printf("Не найдено %s в %v.\n", x, a)
}
// Вывод: Найдено C по индексу 1 в [A C C].

Вариант карты

Если вы делаете повторный поиск и обновление, вы можете использовать карту (map) вместо среза. Карта обеспечивает операции поиска, вставки и удаления за O(1) ожидаемое амортизированное время.

---

Читайте также:

• Массивы, срезы и строки: механика работы append в Golang
• Срезы в Golang: внутреннее устройство и использование
• Эффективный Go: срезы (slices)

Канал в Телеграм