Двоичный поиск мы знаем как способ найти число в отсортированном массиве: делим пополам, отбрасываем половину, повторяем. Оказывается, тот же приём работает там, где никакого массива нет вовсе — и это одно из самых неочевидных применений идеи деления пополам.

Задача, где ответ не вычисляется

На складе лежат партии товара. Сборщик работает h часов, за час берёт одну партию и собирает из неё не больше speed позиций; если в партии осталось меньше — час всё равно тратится целиком. Какая наименьшая скорость позволит успеть за h часов?

Формулы для ответа нет — скорость входит в задачу через округление вверх, и вывести её напрямую не получается. Зато проверить конкретную скорость легко: посчитать, сколько часов уйдёт, и сравнить с h. Это O(N) на проверку.

Перебирать все скорости подряд можно, но их бывает миллиард. Здесь и выручает главное наблюдение.

Монотонность — условие применимости

Если скорость 10 позволяет успеть, то 11 тем более. Если 5 не позволяет, то и 4 не позволит. То есть по мере роста скорости ответ на вопрос «успеваем?» меняется ровно один раз: сначала сплошные «нет», потом сплошные «да».

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

Это и есть монотонность. По сути перед нами отсортированный массив из «нет» и «да» — просто он не лежит в памяти, а вычисляется по требованию. А в отсортированном массиве границу между «нет» и «да» ищут двоичным поиском.

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

Решение

Ищем не в данных, а в диапазоне возможных ответов: от минимально мыслимой скорости до заведомо достаточной.

static int minSpeed(int[] piles, int h) {
    int low = 1;
    int high = 0;
    for (int p : piles) high = Math.max(high, p);
    while (low < high) {
        int mid = low + (high - low) / 2;
        long hours = 0;
        for (int p : piles) hours += (p + mid - 1) / mid;
        if (hours <= h) high = mid;
        else low = mid + 1;
    }
    return low;
}

Сложность — O(N · log(максимальная партия)). Миллиард вариантов скорости превращается в тридцать проверок.

Три места, где обычно ошибаются

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

Зацикливание. Инвариант цикла такой: high всегда указывает на подходящий вариант, low — на первый ещё не отвергнутый. Поэтому при успехе пишем high = mid (сам mid подходит, отбрасывать его нельзя), а при неудаче low = mid + 1 (mid точно не подходит). Если по невнимательности написать low = mid, цикл может застрять: при high - low == 1 середина совпадёт с low, и границы перестанут сближаться.

Переполнение и округление. low + (high - low) / 2 — не украшательство: (low + high) / 2 на больших границах выходит за пределы int. А (p + mid - 1) / mid — это деление с округлением вверх; обычное деление здесь дало бы заниженное число часов.

Как узнать приём в задаче

Верные признаки:

  • в условии есть слова «минимальный такой, что» или «максимальный такой, что»;
  • ответ — число из диапазона, а не элемент данных;
  • посчитать ответ напрямую нельзя, но проверить готовый ответ просто;
  • если ответ подходит, то и любой больший (или любой меньший) тоже подходит.

Типичные задачи такой формы: минимальная вместимость машины, чтобы развезти всё за k рейсов; наибольшая длина, на которые можно нарезать верёвки, чтобы получить k кусков; минимальный день, к которому успевают все работы.

Коротко

  • Двоичный поиск по ответу ищет не в данных, а в диапазоне возможных ответов; данные нужны только для проверки.
  • Условие применимости — монотонность: ответ на вопрос «подходит?» меняется по диапазону ровно один раз.
  • Стоимость — O(проверка · log(ширина диапазона)); миллиард вариантов сводится к трём десяткам проверок.
  • Границы: нижняя заведомо возможна, верхняя заведомо достаточна.
  • При успехе high = mid, при неудаче low = mid + 1 — иначе цикл может не сойтись.
  • low + (high - low) / 2 вместо (low + high) / 2 спасает от переполнения; деление вверх пишется как (a + b - 1) / b.

Дальше — монотонный стек: приём для вопросов вида «а когда впервые станет больше».