Бинарный поиск: как работает и как реализовать

Идея за минуту

Бинарный поиск работает только на отсортированных данных. Вместо перебора всех элементов мы смотрим на середину диапазона:

• если середина равна искомому — нашли;
• если середина меньше — искомое правее, левую половину отбрасываем;
• если больше — искомое левее, отбрасываем правую.

Каждый шаг делит диапазон пополам, поэтому сложность — O(log n). Для миллиона элементов это около двадцати сравнений вместо миллиона.

Итеративная реализация

Используем закрытый интервал [lo, hi]: обе границы входят в поиск.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Ключевые детали:

• Условие lo <= hi, потому что при lo == hi остаётся ещё один кандидат.
• Сдвиг mid + 1 и mid - 1, потому что mid уже проверен.
• lo + (hi - lo) // 2 вместо (lo + hi) // 2 защищает от переполнения в языках с фиксированными целыми (Java, C++). В Python это не обязательно, но привычка полезна.

Рекурсивная реализация

def binary_search_rec(a, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if a[mid] == target:
        return mid
    if a[mid] < target:
        return binary_search_rec(a, target, mid + 1, hi)
    return binary_search_rec(a, target, lo, mid - 1)

Логика та же, но каждый шаг — новый вызов. Глубина рекурсии всего O(log n), так что стек не переполнится. Тем не менее итеративная версия обычно проще в отладке и не тратит память на вызовы.

Ошибки на единицу

Большинство багов в бинарном поиске — это off-by-one. Чтобы их избежать, выберите одно соглашение и держитесь его:

Типичные проблемы:

• Бесконечный цикл: смешали lo < hi и lo = mid. Диапазон перестаёт сужаться.
• Пропуск элемента: написали lo < hi при закрытом интервале.
• Выход за массив: hi = n при обращении к a[hi].

Проверяйте код на пустом массиве, массиве из одного элемента, искомом в начале, в конце и на отсутствующем значении.

Поиск первого вхождения

Если в массиве есть дубликаты, обычная версия вернёт любое из совпадений. Чтобы найти первое (lower bound), не останавливаемся при совпадении, а продолжаем двигаться влево:

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # первая позиция, где a[i] >= target

Если lo < len(a) и a[lo] == target, это первое вхождение. Аналогично upper bound (условие a[mid] <= target) даёт позицию сразу после последнего вхождения. Количество вхождений — разница между ними. В Python для этого есть модуль bisect, в C++ — std::lower_bound и std::upper_bound.

Бинарный поиск по ответу

Приём применим не только к массивам. Если ответ — число в диапазоне, и проверка «подходит ли x» монотонна (все значения до какой-то точки «нет», после — «да»), можно искать бинарно по самому ответу.

Пример: минимальная грузоподъёмность, чтобы перевезти посылки за D дней.

1. Нижняя граница — самая тяжёлая посылка, верхняя — сумма всех.
2. Функция can(capacity) жадно проверяет, хватит ли D дней.
3. Ищем минимальное значение, при котором can возвращает «да», — тем же шаблоном lower bound.

Так же решаются задачи на целочисленный квадратный корень, минимальное время, максимальное минимальное расстояние.