Бинарный поиск на Go: разбираем алгоритм O(log n)

Представьте, что вы ищите перевод нужного слова в книжном словаре (или нужный товар в отсортированном каталоге). Вы же не будете просматривать все записи по порядку? Вместо этого вы откроете книгу примерно посередине и, в зависимости от того, что найдете, продолжите поиск в левой или правой части. Этот интуитивный подход и есть суть бинарного поиска.

В мире алгоритмов и программирования бинарный поиск — это не просто догадка, а мощный и эффективный алгоритм, который находит позицию целевого элемента в отсортированном массиве за логарифмическое время.

Почему бинарный поиск так эффективен?

Давайте сравним его с линейным поиском, когда мы просто перебираем элементы один за другим.

• Линейный поиск: В худшем случае переберет все n элементов. Сложность — O(n). Для массива из 1 000 000 элементов это 1 000 000 операций.
• Бинарный поиск: На каждом шаге отбрасывает половину оставшихся элементов. Сложность — O(log n). Для того же массива из 1 000 000 элементов потребуется всего около 20 операций! (Поскольку log₂1000000 ≈ log₂2²⁰ = 20 * 1 = 20)

Разница огромна, особенно на больших объемах данных.

Как работает алгоритм?

1. Определяем границы: Начинаем с двух переменных — low (начало массива, индекс 0) и high (конец массива).
2. Находим середину: Вычисляем средний индекс mid = (low + high) / 2.
3. Сравниваем:
   1. Если элемент по индексу mid равен целевому — поиск завершен!
   2. Если целевой элемент меньше элемента на mid, смещаем правую границу: high = mid - 1. Искомый элемент должен быть в левой половине.
   3. Если целевой элемент больше, смещаем левую границу: low = mid + 1. Ищем в правой половине.
4. Повторяем: Шаги 2 и 3 повторяем до тех пор, пока элемент не будет найден или пока границы low и high не «пересекутся» (low > high), что означает отсутствие элемента в массиве.

Реализация бинарного поиска на Go

Вот чистый и понятный код на Go, реализующий этот алгоритм. Функция возвращает индекс найденного элемента или -1, если элемент отсутствует.

package main

import "fmt"

func binarySearch(slice []int, target int) int {
    low := 0
    high := len(slice) - 1

    for low <= high {
        mid := (low + high) / 2

        if slice[mid] == target {
            return mid
        }

        if slice[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return -1
}

func main() {
    sortedSlice := []int{11, 22, 33, 44, 55}

    fmt.Println(binarySearch(sortedSlice, 22)) // 1
    fmt.Println(binarySearch(sortedSlice, 66)) // -1
}

Трассировка алгоритма бинарного поиска

Давайте проследим каждый шаг для среза [11, 22, 33, 44, 55] и целевого значения 22.

// Демонстрация поиска числа 22
Итерация 1:
    low = 0, high = 5 - 1 = 4
    mid = (0 + 4) / 2 = 2
    slice[2] == 22, 33 = 22 - false
    33 < 22 - false, значит high = 2 - 1 = 1

Итерация 2:
    low = 0, high = 1
    mid = (0 + 1) / 2 = 0
    slice[0] == 22, 11 = 22 - false
    11 < 22 - true, значит low = 0 + 1 = 1

Итерация 3:
    low = 1, high = 1
    mid = (1 + 1) / 2 = 1
    slice[1] == 22, 22 = 22 - true
    элемент найден, возвращаем индекс 1

Попробуйте теперь проделать то же самое для числа 66 из нашего примера.

Важные нюансы

1. Сортировка — обязательна! Алгоритм корректно работает только с отсортированными данными. Если передать неотсортированный массив (срез), результат будет непредсказуемым.
2. Обработка дубликатов: Стандартная реализация не гарантирует, какой именно из дубликатов будет найден первым. Если это критично, алгоритм нужно дорабатывать.
3. Область применения: Бинарный поиск используется не только в массивах (слайсах). Это основа для более сложных структур данных (деревья, графы) и алгоритмов (например, поиск в логарифмическом времени по ответу).

Ключевой вывод

Бинарный поиск — это элегантный и невероятно эффективный алгоритм, который является отличным примером принципа «разделяй и властвуй». Его понимание и умение реализовывать — признак хорошего тона в разработке.

А у вас есть опыт использования бинарного поиска в реальных проектах? Поделитесь своими мыслями и кейсами в комментариях.