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

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

Бинарный поиск по ответу — приём, где мы ищем не позицию в массиве, а минимальное (или максимальное) значение параметра, при котором выполняется монотонное условие.

Когда применять

Признак: «найдите минимальное X, при котором что-то возможно» (или максимальное), причём функция «возможно ли при X» монотонна — если возможно при X, то возможно и при любом большем (или меньшем). Тогда диапазон ответов можно делить пополам так же, как массив.

Классическая задача: минимальная скорость поедания

Коко ест бананы из куч. За час она съедает не больше speed бананов из одной кучи. Нужно успеть за h часов. Найти минимальную скорость. Чем больше скорость — тем меньше часов нужно: это монотонность. Бинарим по скорости.

import math

def hours_needed(piles, speed):
    return sum(math.ceil(p / speed) for p in piles)

def min_eating_speed(piles, h):
    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if hours_needed(piles, mid) <= h:
            right = mid
        else:
            left = mid + 1
    return left

print(min_eating_speed([3, 6, 7, 11], 8))
print(min_eating_speed([30, 11, 23, 4, 20], 5))
print(min_eating_speed([30, 11, 23, 4, 20], 6))

Вывод:

4
30
23

Как работает под капотом

Здесь массив ответов виртуальный: это все скорости от 1 до max(piles). Мы не строим его в памяти — проверяем середину функцией hours_needed. Условие часов <= h монотонно по скорости: график «успеваем ли» — это ступенька «нет...нет...да...да». Бинарный поиск ищет границу этой ступеньки. Шаблон while left < right с right = mid при успехе ищет именно первое «да» — минимальный подходящий ответ.

Частые ошибки

Применять приём, когда условие не монотонно — тогда границу ступеньки найти нельзя.
Неверно выбрать диапазон: нижняя граница 1 (нельзя есть 0 в час), верхняя — max кучи (быстрее смысла нет).
Перепутать шаблон «первое да» и «последнее да» — для минимума нужен right = mid, для максимума left = mid + 1 с округлением вверх.

Итог

Бинарный поиск по ответу применим, когда условие монотонно по параметру.
Сложность — O(n log(диапазон)): на каждый из log шагов делаем проверку за O(n).
Шаблон left < right с right = mid находит минимальный подходящий ответ.