Binary Search

Линейный поиск в отсортированном массиве просматривает элементы по одному, хотя после первого же сравнения половина из них заведомо не подходит. На миллионе элементов это миллион сравнений вместо двадцати.

Вторая, менее очевидная форма той же боли — подбор ответа. «Какая минимальная скорость позволит успеть за 8 часов», «какой наименьший размер сервера выдержит нагрузку»: формулы нет, зато есть проверка конкретного значения. Перебор значений подряд стоит столько же, сколько велик диапазон ответа, — а диапазон бывает до $10^{18}$.

Такая формулировка сразу покрывает оба случая: в массиве граница — это позиция первого элемента, не меньшего искомого; в задаче на подбор — наименьшее допустимое значение ответа. Алгоритм в обоих случаях один и тот же.

1  2  3  4  5  6  7  8  9        ищем 7
            ^
           mid = 5:  7 > 5  ->  левая половина больше не нужна

               6  7  8  9
                     ^
                    mid = 7:  нашли

Тот же цикл в задаче про подбор скорости. Проверка — симуляция: успеваем ли за 8 часов. Она даёт «нет, нет, …, да, да», и мы ищем первое «да».

скорость:   1   2   3   4   5   6   7   8
успеваем:  нет нет нет нет нет  да  да  да
                                 ^
                                 ответ: 6

mid = 4:  не успеваем  ->  все скорости <= 4 отпадают
mid = 6:  успеваем     ->  ответ не правее 6
mid = 5:  не успеваем  ->  ответ ровно 6

def lower_bound(a, target):
    lo, hi = 0, len(a)          # инвариант: ответ лежит в [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2   # без переполнения
        if a[mid] < target:
            lo = mid + 1            # a[mid] точно не ответ
        else:
            hi = mid                # a[mid] может быть ответом
    return lo                       # lo == hi

lo, hi = 1, 10**18              # заведомо плохое и заведомо хорошее
while lo < hi:
    mid = lo + (hi - lo) // 2
    if ok(mid):                 # проверка может быть сколь угодно сложной
        hi = mid
    else:
        lo = mid + 1
return lo

• Время — $O(\log n)$ сравнений; для поиска по ответу это $O(\log R)$ проверок, где $R$ — длина диапазона.
• Память — $O(1)$.
• Предусловие — отсортированность массива или монотонность предиката: «нет, …, нет, да, …, да».
• Полуинтервал [lo, hi): пустота — это lo == hi, и большинство ошибок на единицу исчезает само.

Корректность держится на инварианте: ответ всегда лежит в текущем отрезке [lo, hi]. Каждая ветка цикла сохраняет это свойство — либо мы отбрасываем половину, про которую доказано, что ответа там нет, либо сужаем отрезок, оставляя кандидата внутри. Когда границы сходятся, в отрезке остаётся ровно один элемент, и по инварианту это и есть ответ.

Завершимость — отдельное требование, и именно на нём зацикливаются реализации. Каждая ветка обязана строго уменьшать длину отрезка. lo = mid вместо lo = mid + 1 этого не делает: при hi - lo == 1 середина совпадает с lo, и цикл крутится вечно.

• Повёрнутый массив — на каждом шаге определяем, какая половина отсортирована, и только потом сравниваем.
• Массив неизвестной длины — сначала удваиваем правую границу, пока не перешагнём значение.
• Вещественный ответ — фиксированное число итераций вместо условия сходимости: сто шагов дают точность $10^{-30}$ от диапазона.
• Унимодальная функция — половинное деление по производной или тернарный поиск.
• Матрица, отсортированная по строкам и столбцам — обход от правого верхнего угла: шаг влево или вниз отбрасывает строку или столбец целиком.

• Зацикливание. Ветка, не уменьшающая отрезок (lo = mid), — самая частая причина бесконечного цикла.
• Переполнение. (lo + hi) // 2 в языках с ограниченным целым типом переполняется на больших индексах; lo + (hi - lo) // 2 — нет.
• Не тот ответ из двух. «Любое вхождение» и «первое вхождение» — разные задачи; при дубликатах разница видна сразу.
• Немонотонный предикат. Метод молча вернёт какую-то границу — неверную.
• Диапазон поиска. Границы должны быть заведомо плохой и заведомо хорошей; ответ вне диапазона не найдётся.
• Вещественные сравнения. Условие lo < hi на float не завершается — цикл делают по числу итераций.

1. Почему lo = mid + 1, а не lo = mid?
2. Чем lower_bound отличается от upper_bound и как из них получить число вхождений элемента?
3. Сформулируйте предикат для задачи «минимальная скорость, чтобы успеть за 8 часов», и докажите его монотонность.
4. Повёрнутый массив [4, 5, 6, 7, 0, 1, 2]: как за один шаг понять, какая половина отсортирована?
5. Почему для вещественного ответа цикл делают фиксированной длины?