Двоичный поиск по ответу

Хочется прочитать «Войну и мир» за месяц: каждый день по нескольку глав, по порядку, не разрывая глав. Сколько слов в день придётся читать в самый тяжёлый день, если распределить главы как можно лучше? Перебирать все способы разложить 361 главу на 30 дней безнадёжно. Но проверить конкретный предел — «хватит ли 15 тысяч слов в день?» — можно одним проходом по главам. А раз так, ответ можно найти делением пополам. Двигайте число дней.

За 30 дней — не больше 15 802 слов в день, около восьмидесяти минут чтения. Ровно поровну было бы 15 088, но главы не режутся. За год ответ — 3476: это длина самой длинной главы, и меньше нельзя при любом числе дней. А поиск при любом k делает около девятнадцати проверок.

Идея

Вместо вопроса «какой наименьший предел?» задаём вопрос «хватит ли предела L?». Ответ на него монотонный: если L хватает, то и любого большего хватит. Значит, на оси пределов есть граница — слева «не хватает», справа «хватает», — и её ищет обычный двоичный поиск, только не по массиву, а по самим ответам.

Вот эта граница на графике. Чем больше дневной предел, тем меньше дней нужно: функция идёт вниз ступеньками. Мы ищем первую точку, где она опустилась до k дней или ниже. Каждая проба — проверка одного L; зелёные хватает, красные нет, и отрезок поиска каждый раз сокращается вдвое.

Для приёма нужны две вещи. Монотонная проверка: «подходит» для одного значения влечёт «подходит» для всех больших (или для всех меньших). И дешёвая проверка: ответить «хватит ли L» гораздо проще, чем найти лучшее L. Здесь проверка жадная: класть очередную главу в текущий день, пока она помещается, иначе начинать новый день. Жадность тут права: если какой-то план укладывается в k дней, то и жадный — ведь он заполняет каждый день не меньше, чем любой другой план к тому же моменту.

Код

Отрезок поиска — от самой длинной главы (меньше нельзя) до суммы всех глав (весь роман за день). Пока отрезок не сжался в точку, проверяем середину: хватает — правая граница на середину, не хватает — левая за середину.

Число проверок — log₂ ширины отрезка: от 3476 до 452 626 слов — около 449 тысяч значений, это 19 делений пополам. Каждая проверка — проход по 361 главе. Перебор пределов подряд от самой длинной главы потребовал бы для месяца больше двенадцати тысяч проверок.

Первое «да» и последнее «да»

Задачи бывают двух видов, и в них отличается одна строчка.

• Наименьшее подходящее — «какой наименьший предел позволяет уложиться». Проверка «да» справа от границы. Середина — с округлением вниз, при «да» правый край переходит на середину, при «нет» левый — на середину плюс один.
• Наибольшее подходящее — «как далеко друг от друга можно расставить станции». Проверка «да» слева от границы. Середина — с округлением вверх, (lo + hi + 1) / 2, иначе на двух соседних числах поиск топчется на месте вечно. Это вторая задача статьи.

Если ответ вещественный — скорость, время, длина, — вместо «пока отрезок не сжался» делают фиксированное число шагов: сто делений пополам сужают отрезок в 2¹⁰⁰ раз, этого хватает для любой точности, доступной числам double. Так устроен метод бисекции для корней уравнений.

Сколько это стоит

O(log D) проверок, где D — ширина отрезка возможных ответов, умножить на стоимость одной проверки. Здесь проверка — O(n), и всё вместе — O(n log S), где S — сумма длин глав. Логарифм от ширины отрезка растёт медленно: даже если ответ может быть любым числом до 10¹⁸, хватит шестидесяти проверок.

Главная работа — заметить, что задачу можно перевернуть. Признаки: в условии «наименьшее наибольшее» или «наибольшее наименьшее», ответ — число из широкого диапазона, а проверка конкретного числа — жадная или простая. Если же проверка немонотонна — увеличили параметр, а «подходит» сменилось на «не подходит» и обратно, — двоичный поиск даст неверный ответ без всякого предупреждения.

Задачи

Первая — план чтения из сцены для нескольких сроков сразу. Во второй ищется наибольшее подходящее, и середину приходится округлять вверх; тест — 177 перекрёстков маршрута через весь центр Алматы.