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

За двадцать шагов найти нужное среди миллиона — и тот же приём применить к ответу задачи, а не к массиву.

Бинарный поиск — приём, который на каждом шаге вдвое сокращает область поиска, опираясь на монотонность: достаточно понять, в какой половине лежит ответ.

Зачем это нужно

Бинарный поиск — это не одна задача «найти число в массиве», а целый образ мышления. Его прямое применение — поиск элемента в отсортированном массиве за O(log n). Но настоящая сила раскрывается в приёме «бинпоиск по ответу»: когда сам ответ задачи лежит в некотором диапазоне и есть монотонная проверка «годится ли значение X», мы бинпоиском находим границу за O(log(диапазон)) проверок. Этот приём решает огромный класс олимпиадных задач на «минимальное/максимальное значение, при котором ...».

Часть 1. Поиск в отсортированном массиве

Идея: смотрим на средний элемент. Если он меньше искомого — ответ правее, отбрасываем левую половину; иначе — левее. Каждый шаг вдвое уменьшает диапазон, поэтому шагов всего log2(n). Реализуем самый полезный вариант — lower_bound: первая позиция, куда можно вставить x, сохранив порядок (она же — первый элемент ≥ x).

from bisect import bisect_left

a = [1, 3, 3, 5, 8, 13, 21]

def lower_bound(arr, x):
    lo, hi = 0, len(arr)          # ищем в полуинтервале [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1           # arr[mid] мал — ответ строго правее
        else:
            hi = mid               # arr[mid] годится — но ищем левее
    return lo

for x in (5, 4, 21, 100):
    i = lower_bound(a, x)
    present = i < len(a) and a[i] == x
    print(f"x={x}: индекс={i}, есть={present}, bisect={bisect_left(a, x)}")

Ключевая дисциплина — инвариант полуинтервала [lo, hi): всё левее lo точно < x, всё правее или равно hi — не рассматривается. Цикл сужает интервал, пока lo не упрётся в hi. На практике в Python почти всегда берут готовый bisect_left — он делает ровно то же, и его результат совпадает с нашим.

Вывод:

x=5: индекс=3, есть=True, bisect=3
x=4: индекс=3, есть=False, bisect=3
x=21: индекс=6, есть=True, bisect=6
x=100: индекс=7, есть=False, bisect=7

Часть 2. Бинпоиск по ответу — главный приём

А вот это нужно прочувствовать. Многие задачи звучат так: «найди минимальное X, при котором выполняется условие». Если условие монотонно — то есть существует порог, до которого «нельзя», а после которого «можно» (как ряд НЕТ НЕТ НЕТ ДА ДА ДА) — мы можем бинпоиском найти этот порог, проверяя кандидатов функцией check(X).

Разберём классику: обезьянка ест бананы из piles кучек со скоростью k бананов в час (одну кучку за раз). За какую минимальную скорость k она успеет съесть всё за h часов?

piles = [3, 6, 7, 11]
h = 8

def hours(speed):
    # сколько часов нужно при данной скорости (округление вверх по каждой кучке)
    return sum((p + speed - 1) // speed for p in piles)

# Монотонность: чем БОЛЬШЕ скорость, тем МЕНЬШЕ часов.
# Ищем минимальную скорость, при которой hours(speed) <= h.
lo, hi = 1, max(piles)
while lo < hi:
    mid = (lo + hi) // 2
    if hours(mid) <= h:
        hi = mid           # успевает — пробуем медленнее (левее)
    else:
        lo = mid + 1       # не успевает — нужно быстрее (правее)
print("Минимальная скорость:", lo, "часов:", hours(lo))

Обрати внимание: мы не перебираем все скорости от 1 до 11. Мы бинпоиском по диапазону скоростей за ~4 проверки находим границу между «не успевает» и «успевает». Функция check здесь — hours(mid) <= h. Это и есть рецепт: определи диапазон ответа → напиши монотонную проверку → бинпоиск по диапазону.

Вывод:

Минимальная скорость: 4 часов: 8

Как распознать «бинпоиск по ответу»

• В условии есть слова «минимальное/максимальное значение, при котором ...».
• Можно придумать функцию check(X), которая отвечает «годится ли X» за полиномиальное время.
• Свойство монотонно: если X годится, то и все большие (или все меньшие) тоже годятся.

Типичные примеры: «минимальная вместимость, чтобы развезти груз за D дней», «максимальная длина отрезка, на которую можно разбить», «минимальное время, за которое выполнят заказы». Все они сводятся к одному шаблону.

Вещественный бинпоиск

Иногда ответ — не целое число, а дробь: длина, скорость, вероятность. Тогда условие lo < hi бесполезно (вещественные почти никогда не сравняются точно), и цикл крутят фиксированное число раз — обычно 60–100 итераций. Каждая итерация удваивает точность, так что 100 итераций дают точность порядка 2^(-100) — заведомо достаточно. Найдём, например, кубический корень из числа бинпоиском по ответу: ищем такое x, что x^3 = target.

def cube_root(target):
    lo, hi = 0.0, max(1.0, target)     # ответ в [0, target] при target>=1
    for _ in range(100):               # фиксированное число итераций
        mid = (lo + hi) / 2
        if mid * mid * mid <= target:  # монотонно: куб растёт
            lo = mid
        else:
            hi = mid
    return lo

print("cbrt(27) =", round(cube_root(27), 6))
print("cbrt(2)  =", round(cube_root(2), 6))

Та же монотонность («куб x растёт с x»), тот же бинпоиск — только границы вещественные и цикл фиксированной длины. Этот приём решает уравнения, где аналитической формулы нет, но функция монотонна. Главное — не пытаться завершать цикл по lo < hi на вещественных числах: используй счётчик итераций.

Вывод:

cbrt(27) = 3.0
cbrt(2)  = 1.259921

Сложность

Поиск в массиве: O(log n) по времени, O(1) по памяти. Бинпоиск по ответу: O(log(R) · C), где R — длина диапазона значений, C — стоимость одной проверки check. Например, если check — это проход по массиву O(n), а диапазон ответа до 10^9, то итог — O(n · 30), что очень быстро.

Подводные камни

• Бесконечный цикл. Следи, чтобы интервал реально сужался. Шаблон с lo < hi, hi = mid, lo = mid + 1 — безопасный, его и держись.
• Перепутанная граница. Реши заранее: ты ищешь первое «ДА» (тогда hi = mid) или последнее «НЕТ». Это самый частый источник off-by-one.
• Немонотонная проверка. Если свойство не монотонно — бинпоиск неприменим, нужен другой подход.
• Вещественный бинпоиск. Для дробного ответа цикл делают на фиксированное число итераций (например, 100), а не по lo < hi.

Итог

• Бинарный поиск работает по монотонности и сокращает область вдвое каждый шаг — O(log n).
• В массиве используй готовый bisect_left / bisect_right.
• «Бинпоиск по ответу»: диапазон ответа + монотонная check = находим границу за O(log R · C).
• Главная аккуратность — границы интервала и направление монотонности.