Поиск в упорядоченных последовательностях

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

Проход по всем элементам. O(n), не требует сортировки.

func linearSearch(a []int, target int) int {
    for i, v := range a {
        if v == target { return i }
    }
    return -1
}

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

Делит диапазон пополам на каждом шаге. O(log n), требует отсортированного среза.

func binarySearch(a []int, target int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        if a[mid] == target { return mid }
        if a[mid] < target  { lo = mid + 1 } else { hi = mid - 1 }
    }
    return -1
}

В стандартной библиотеке: sort.SearchInts, sort.Search.

Интерполяционный поиск

Оценивает позицию цели по значению, а не делит пополам. O(log log n) для равномерных распределений, O(n) в худшем.

func interpolationSearch(a []int, target int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi && target >= a[lo] && target <= a[hi] {
        pos := lo + (target-a[lo])*(hi-lo)/(a[hi]-a[lo])
        if a[pos] == target { return pos }
        if a[pos] < target  { lo = pos + 1 } else { hi = pos - 1 }
    }
    return -1
}

Эффективен для равномерно распределённых числовых данных (телефонные книги, временные ряды).

Экспоненциальный поиск

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

func exponentialSearch(a []int, target int) int {
    if a[0] == target { return 0 }
    i := 1
    for i < len(a) && a[i] <= target { i *= 2 }
    lo := i / 2
    hi := min(i, len(a)-1)
    return binarySearch(a[lo:hi+1], target) // с поправкой на смещение
}

Поиск Фибоначчи

Использует числа Фибоначчи для деления диапазона. O(log n), лучше бинарного при дорогостоящем обращении к памяти.

Числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, ... Диапазон делится в соотношении F(k-1) : F(k-2), что даёт более равномерное распределение сравнений при последовательном чтении.

Итог

Упражнения