Двоичный поиск по ответу: искать там, где нет массива

Коротко

Двоичный поиск работает не только по массиву, а по любому МОНОТОННОМУ условию: если для какого-то значения x ответ «да», то для всех больших (или всех меньших) - тоже «да». Тогда граница между «нет» и «да» ищется тем же делением пополам за Θ(log(диапазон)), даже когда никакого массива нет вовсе. Это называется двоичным поиском по ответу: мы не ищем элемент, а угадываем ЧИСЛО-ОТВЕТ (минимальную скорость, максимальный размер, порог), проверяя каждую догадку функцией «годится ли». Условие обязано быть монотонным - иначе делить пополам нельзя. Приём превращает задачу «найти оптимум» в задачу «проверить догадку», которая почти всегда проще.

Если ты умеешь свести задачу оптимизации к монотонному предикату «годится ли x» и найти его границу двоичным поиском по диапазону значений (а не по индексам), листай до «Теперь сам».

Как думаешь, что общего у поиска в массиве и у «подобрать минимальную скорость»

В массиве двоичный поиск опирается на порядок: слева меньшие, справа большие. Но приглядись - ему не нужен САМ массив, ему нужно лишь свойство «если тут да, то правее тоже да». Массив это свойство обеспечивает сортировкой, но его может давать и функция. Пусть вопрос: «какая МИНИМАЛЬНАЯ скорость чтения уложит все файлы за T часов?». Заметь монотонность: если скорости v хватает, то v + 1 тем более хватит (быстрее - не хуже). Значит ответы на вопрос «хватает ли v?» выстроены как нет, нет, …, нет, да, да, … - ровно как отсортированный массив из нулей и единиц. А в таком «массиве» границу между «нет» и «да» находит двоичный поиск - хоть массива и нет, есть только функция-проверка.

На что это похоже

Ты подбираешь горячую воду в душе краном без делений. Полностью холодно - «нет», кипяток - «да, даже слишком». Ты крутишь кран НА СЕРЕДИНУ диапазона: холодновато - значит нужная точка правее, крутишь в верхнюю половину; горячо - в нижнюю. Каждый поворот выбрасывает половину диапазона крана. Ты не перебираешь все положения подряд - ты делишь пополам, потому что «теплее» монотонно растёт с поворотом. Через десяток проб находишь границу комфортной температуры. Кран - это не массив, это непрерывный параметр, но раз «горячее» монотонно, двоичный поиск работает точно так же.

Механизм: предикат «годится ли» и поиск его границы

Схема одна для всех таких задач. Обозначим ok(x) - функцию, отвечающую «да/нет» на вопрос «годится ли значение x». Нужны три вещи:

Монотонность. ok должна быть ступенькой: либо нет…нет, да…да (ищем МИНИМАЛЬНЫЙ годный x), либо да…да, нет…нет (ищем МАКСИМАЛЬНЫЙ годный). Без этого делить пополам нельзя.
Диапазон [lo, hi] возможных значений ответа - заведомо широкий: lo такой, что точно «нет» (или ниже минимума), hi - такой, что точно «да».
Поиск границы тем же полуинтервалом, только mid - это КАНДИДАТ В ОТВЕТ, а вместо a[mid] сравниваем ok(mid):

пока lo < hi:
    mid = lo + (hi - lo) // 2
    если ok(mid):  hi = mid       # mid годится - ответ не правее, оставляем mid
    иначе:         lo = mid + 1   # mid не годится - ответ строго правее
# lo == hi - минимальный x, для которого ok(x) истинно

Стоимость - Θ(log(hi − lo) · C), где C - цена одной проверки ok. Мы платим логарифмом от ДИАПАЗОНА ЗНАЧЕНИЙ, а не от числа элементов.

Ответы предиката выстроены ступенькой нет→да. Двоичный поиск находит границу - минимальное годное значение - за log от ширины диапазона.

Правило

Двоичный поиск по ответу ищет не элемент, а число-ответ (порог, минимальную/максимальную годную величину) по МОНОТОННОМУ предикату ok(x). Условие: если ok(x) истинно, то истинно и для всех больших x (или для всех меньших) - ответы выстроены ступенькой нет→да. Задаём широкий диапазон [lo, hi] (lo заведомо «нет», hi заведомо «да») и тем же делением пополам находим границу, сравнивая не a[mid], а ok(mid). Стоимость - Θ(log(диапазон) · цена проверки). Приём меняет задачу «найти оптимум» на «проверить догадку», и второе почти всегда проще первого.

Разбор: почему без монотонности приём рушится

Двоичный поиск выбрасывает половину, потому что ВЕРИТ: раз здесь «да», то в ту сторону всё «да». Убери монотонность - и эта вера ложна. Пусть ответы нет, да, нет, да: проверили середину, получили «нет» - и куда идти? Годное значение может быть и левее, и правее, отброшенная половина могла содержать ответ. Деление пополам теряет корректность, поиск вернёт что попало. Поэтому ПЕРВЫЙ шаг любой такой задачи - доказать монотонность: сформулировать ok(x) так, чтобы «стало годно - и дальше годно». Часто это требует переформулировки: не «ровно k штук» (немонотонно - то да, то нет), а «не меньше k штук» (монотонно - чем больше ресурс, тем больше штук). Монотонность не дана свыше, её конструируют, и это главная работа в задаче.

Разбор: почему логарифм от диапазона, а не от числа вариантов подряд

Наивный способ найти минимальную годную скорость - перебирать v = 1, 2, 3, … до первого «да»: это Θ(диапазон · C), для скоростей до миллиарда - миллиард проверок. Двоичный поиск по ответу делает Θ(log(диапазон) · C) - для миллиарда это ~30 проверок вместо миллиарда. Логарифм тут от ШИРИНЫ диапазона значений, и это принципиально: даже если годных значений мало, а диапазон огромен, поиск дёшев. Оговорка про цену: каждая проверка ok(mid) может быть недешёвой (например, промоделировать раздачу файлов - Θ(n)), тогда итог Θ(n · log(диапазон)). Всё равно это резкий выигрыш против перебора всех значений, и почти всегда - против прямого решения задачи оптимизации «в лоб».

Что ломается без этого

Первая ошибка - применить приём к немонотонному условию: поиск «отработает» и вернёт неверное число, молча. Всегда сначала докажи ступеньку нет→да. Вторая - взять слишком узкий диапазон [lo, hi], не покрывающий ответ: если hi окажется «нет», граница уедет за диапазон и ответ будет ложным; бери концы с запасом (lo заведомо мал, hi заведомо велик). Третья - искать «ровно k» вместо «≥ k»: равенство немонотонно, переформулируй через неравенство. Четвёртая - на вещественных значениях крутить lo < hi до бесконечности (из-за неточности дробей поиск не сойдётся в точку): там задают ЧИСЛО итераций (скажем, 100 удвоений точности) или требуемую точность hi − lo < ε.

Зачем это в работе

Двоичный поиск по ответу - один из самых универсальных приёмов в олимпиадах и инженерии. Им решают «минимальная вместимость грузовика, чтобы развезти за d дней», «максимальная длина верёвки, чтобы нарезать k кусков», «минимальная задержка, при которой система ещё стабильна», подбор порога в калибровке, поиск корня монотонной функции (тот самый метод бисекции из численных методов). Общий признак, по которому его узнают: задача просит ОПТИМУМ («минимальное/максимальное такое, что…»), а проверить конкретную догадку куда легче, чем сразу найти лучшую. Увидев этот признак, ты сводишь оптимизацию к предикату и получаешь log вместо линии или перебора. Это и есть переход от «искать в массиве» к «искать в пространстве ответов» - главная идея, ради которой стоит весь урок.

Теперь сам

Задача: раздать n конфет так, чтобы КАЖДЫЙ из детей получил хотя бы по x конфет одного вкуса, и найти МАКСИМАЛЬНЫЙ такой x. Проверка ok(x) считает, скольким детям хватит порций размера x, и говорит «да», если это число ≥ числа детей. Почему тут применим двоичный поиск по ответу и в какую сторону выстроена ступенька?

Ответ. Предикат монотонен, но «наоборот»: чем МЕНЬШЕ размер порции x, тем больше детей можно накормить, значит ok(x) истинно для маленьких x и ложно для больших - ступенька да…да, нет…нет. Мы ищем МАКСИМАЛЬНЫЙ годный x - последнее «да» перед переходом в «нет». Диапазон: lo = 1 (порция хотя бы одна конфета, заведомо «да» при достатке) и hi = размер самой большой кучи вкуса (заведомо «нет», если детей больше одного). Двоичный поиск сходится к границе, а раз мы хотим последнее «да», сдвиги зеркальны примеру из механизма: при ok(mid) двигаем lo = mid (годно - пробуем больше), при не ok(mid) - hi = mid − 1. Одна тонкость завершаемости: раз при годном mid мы пишем lo = mid (без плюс-единицы), середину надо округлять ВВЕРХ - mid = lo + (hi − lo + 1)//2. Иначе на участке из двух значений обычное округление вниз даёт mid = lo, и lo = mid не сдвинется - ровно то зависание, о котором предупреждал первый урок. «Последнее да» - зеркало «первого да», и середина у него тоже зеркальная. Монотонность есть, диапазон широкий - приём применим, и вместо перебора всех размеров порции мы делаем log проверок.

Главное

Двоичный поиск работает по любому МОНОТОННОМУ предикату ok(x), а не только по массиву: если «да» для x влечёт «да» для всех больших (или всех меньших), ответы образуют ступеньку нет→да, и границу находят делением пополам за Θ(log(диапазон) · цена проверки). Так задачу «найти оптимум» сводят к «проверить догадку». Обязателен первый шаг - доказать (или сконструировать переформулировкой) монотонность: «≥ k», а не «ровно k». Берут широкий диапазон с запасом, а на вещественных значениях задают число итераций или точность. Признак задачи - просят минимальное/максимальное «такое, что…».