Бинарный поиск по ответу: приём для задач про минимальную скорость и вместимость

Короткий ответ. Бинарный поиск по ответу перебирает не массив, а диапазон возможных ответов. Берём кандидата, проверяем за O(n), подходит ли он, и отбрасываем половину диапазона. Приём нужен в задачах «минимальная скорость», «наименьшая вместимость», «максимальное минимальное расстояние». Ниже устройство, функция проверки, код на Python и задача про Коко и бананы.

Что такое бинарный поиск по ответу?

Обычный бинарный поиск ищет число в отсортированном массиве. Здесь массив не отсортирован. Зато сами ответы образуют диапазон от lo до hi.

Про каждого кандидата можно спросить: хватает ли его? Ответы на этот вопрос монотонны. До какого-то порога все «нет», после него все «да». Бинарный поиск находит порог.

Для метода нужны три вещи: нижняя граница, верхняя граница и функция проверки. Границы задают диапазон, проверка отвечает на вопрос про середину.

По каким словам в задаче узнать приём?

• «Минимальная скорость, чтобы успеть за h часов».
• «Наименьшая вместимость корабля, чтобы вывезти груз за d дней».
• «Разбить массив на k частей так, чтобы наибольшая сумма была минимальна».
• «Расставить k коров в стойлах, чтобы минимальное расстояние было максимальным».

Сигнал это слово «минимум» или «максимум» рядом с условием. Проверить фиксированное значение легко. Найти лучшее значение напрямую трудно. Этот разрыв и закрывает приём. Перебор всех кандидатов подряд тоже сработает, но за O(n · R), где R это размер диапазона.

Как устроена функция проверки?

Проверка берёт кандидата и возвращает True, если он удовлетворяет условию. Она должна быть монотонной: раз True, то True и для всех больших кандидатов. Для задач на максимум наоборот.

Задача про Коко. Кандидат это скорость k. Часов нужно сумма ceil(куча / k) по всем кучам. Возвращаем True, если сумма не больше h. Быстрее скорость, меньше часов. Монотонно.

Задача	Диапазон	Проверка(x)	Ищем
Коко и бананы	1 .. max(кучи)	часов при скорости x <= h	наименьший True
Вместимость корабля	max(w) .. sum(w)	дней при вместимости x <= d	наименьший True
Split Array Largest Sum	max(a) .. sum(a)	частей с лимитом x <= k	наименьший True
Коровы в стойлах	1 .. max разрыв	k коров на расстоянии x помещаются	наибольший True

Как написать бинарный поиск по ответу на Python?

import math

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)

    def ok(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid подходит, пробуем меньше
        else:
            lo = mid + 1      # mid не подходит, нужно больше
    return lo

# вариант на максимум: наибольший x, для которого ok(x) True
def largest_ok(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Цикл держит в lo наименьшее значение, которое ещё может подойти. Когда lo догнал hi, это ответ. Плюс один во втором варианте спасает от бесконечного цикла.

Как это выглядит на примере?

Кучи [3, 6, 7, 11], h = 8. Диапазон от 1 до 11. Пробуем 6: часов 1 + 1 + 2 + 2 = 6, подходит, hi = 6. Пробуем 3: часов 1 + 2 + 3 + 4 = 10, много, lo = 4.

Пробуем 5: часов 1 + 2 + 2 + 3 = 8, подходит, hi = 5. Пробуем 4: часов тоже 8, подходит, hi = 4. lo равен hi. Ответ 4.

Четыре проверки вместо одиннадцати. При диапазоне до миллиарда будет тридцать проверок вместо миллиарда.

Как выбрать границы?

Нижняя граница это наименьшее осмысленное значение. Для скорости это 1. Для вместимости это самый тяжёлый предмет, иначе он не поедет вообще.

Верхняя граница это значение, которое точно подходит. Самая большая куча, сумма всех весов. Лишний запас стоит пары проверок, поэтому берите с запасом.

На каких ошибках ломается бинарный поиск по ответу?

• Проверка не монотонна. Тогда половина с ответом выбрасывается.
• Границы не включают ответ. Вместимость меньше самого тяжёлого груза его не увезёт.
• mid = (lo + hi) // 2 в задаче на максимум. lo = mid тогда не сдвигается.
• Целочисленное деление там, где нужно округление вверх.

Как объяснить приём на собеседовании?

Скажите: «Ответ напрямую не посчитать, но догадку я проверю за O(n)». Потом скажите, что проверка монотонна. Назовите границы. Пишите цикл.

Сложность назовите как O(n log(hi - lo)). Логарифм берётся от диапазона ответов, а не от массива. Собеседующие проверяют, что вы знаете, какой это логарифм.

Отработать узнавание приёма можно на странице бинарный поиск по ответу. Версия для массива лежит на странице бинарный поиск.

Вопросы и ответы

Чем это отличается от обычного бинарного поиска?

Обычный сравнивает mid с целью в отсортированном массиве. Этот вызывает на mid функцию проверки. Массив вообще может быть не отсортирован.

Где приём встречается вне собеседований?

В планировании нагрузки: сколько серверов нужно, чтобы очередь разгребалась за час. Проверить одно число серверов легко. Найти минимум напрямую сложно. Это та же задача про Коко с другими словами.

Может ли ответ быть дробным?

Да. Крутите цикл фиксированное число раз, около ста, вместо условия lo равен hi. Или остановитесь, когда hi - lo меньше нужной точности.

Как понять, что проверка монотонна?

Спросите себя: если значение x подходит, подойдёт ли x + 1? Для скорости, вместимости и лимита суммы ответ да. Если ответ «не всегда», приём не подходит, и нужен другой способ.

Что делать, если проверка стоит O(n log n)?

Тогда всего будет O(n log n log R). Обычно это проходит. Одна сортировка до цикла часто возвращает проверку к O(n).