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

Двоичный поиск по ответу — это метод решения задач, при котором искомое значение (обычно числовое) находится путём многократного деления интервала возможных значений пополам и проверки некоторого условия. В отличие от классического двоичного поиска по массиву, где проверяется наличие элемента в отсортированном списке, здесь объектом поиска является не индекс, а само число, удовлетворяющее заданному критерию (например, минимальное время, за которое можно выполнить работу, или максимальная длина, при которой возможно размещение). Метод применяется в задачах, где ответ монотонно зависит от проверяемого параметра, и позволяет заменить перебор с линейной сложностью на логарифмическую.

История

Двоичный поиск по ответу не имеет единого автора или даты открытия, так как является прямым следствием общей идеи дихотомии (деления пополам), известной ещё в античной математике. Метод «вилки» (regula falsi) использовался для приближённого решения уравнений. В контексте алгоритмических задач на программирование техника получила широкое распространение в конце XX века с развитием олимпиадного программирования и теории сложности вычислений. В русскоязычной литературе термин «двоичный поиск по ответу» закрепился в 2000-е годы благодаря задачам на платформах Codeforces, Timus и других.

Принцип работы

Основная идея метода заключается в том, что если для некоторого значения x условие задачи выполняется, то для всех значений y > x (или y < x — в зависимости от монотонности) оно также выполняется. Такая монотонность позволяет сужать диапазон поиска.

Алгоритм

1. Задать начальные границы поиска: левую (L) и правую (R), такие, что для L условие заведомо не выполняется, а для R — выполняется (или наоборот).
2. Пока R - L > eps (для вещественных чисел) или L < R (для целых чисел), выполнять:

• Вычислить середину mid = (L + R) / 2.
• Проверить выполнение условия для mid.
• Если условие выполняется, сдвинуть правую границу R = mid (или левую L = mid — в зависимости от логики).
• Если не выполняется, сдвинуть другую границу.

1. После завершения цикла L (или R) будет содержать искомое значение.

Условия применимости

• Монотонность: функция проверки должна быть монотонной (неубывающей или невозрастающей) на интервале поиска. Например, если проверяется, можно ли уложиться в заданное время, то с увеличением времени вероятность успеха не уменьшается.
• Детерминированность: проверка для одного и того же значения всегда даёт одинаковый результат.
• Вычислимость: проверка должна быть достаточно быстрой, чтобы выполняться за логарифмическое число раз (обычно 30–60 итераций для вещественных чисел, 30–40 для целых).

Классификация

По типу искомого значения

• Целочисленный поиск: ищется целое число (например, минимальное количество предметов). Границы сдвигаются на 1, условие остановки — L < R.
• Вещественный поиск: ищется дробное число (например, максимальная длина отрезка). Используется точность eps (например, 1e-9) или фиксированное число итераций (например, 100).

По направлению монотонности

• Поиск минимума: условие выполняется для всех значений, больших или равных ответу. Границы: L — заведомо не подходит, R — подходит.
• Поиск максимума: условие выполняется для всех значений, меньших или равных ответу. Границы: L — подходит, R — не подходит.

Примеры применения

Задача о вещественном корне уравнения

Пусть дано уравнение f(x) = 0, где f — непрерывная монотонная функция на отрезке [a, b], причём f(a) * f(b) < 0. Двоичный поиск по ответу позволяет найти корень с заданной точностью. На каждой итерации вычисляется f(mid) и выбирается половина отрезка, на которой знак функции меняется.

Задача о минимальном времени

Требуется перевезти груз на расстояние S со скоростью не более V_max, причём каждые T часов нужно делать остановку на t минут. Нужно найти минимальное время в пути. Двоичный поиск по ответу проверяет, можно ли уложиться в заданное время X, моделируя движение с учётом остановок.

Задача о максимальной длине

Имеется N отрезков различной длины. Нужно разрезать их на K одинаковых кусков максимально возможной длины. Двоичный поиск по ответу проверяет, можно ли получить куски длиной L (суммируя целые части от деления длины каждого отрезка на L).

Задача о минимальном пороге

В массиве чисел нужно выбрать подмножество так, чтобы сумма элементов была не меньше S, а количество элементов — минимально. Двоичный поиск по ответу находит минимальное количество элементов, проверяя, можно ли набрать сумму S заданным числом элементов (например, сортировкой и выбором самых больших).

Оценка сложности

Пусть длина интервала поиска равна D, а время выполнения одной проверки — O(P). Тогда общее время работы алгоритма составляет O(P log(D/eps)) для вещественных чисел или O(P log(D)) для целых. Логарифмическая зависимость делает метод эффективным даже при больших диапазонах (например, D = 10^18 требует около 60 итераций).

Особенности реализации

• Выбор начальных границ: границы должны быть гарантированно шире возможного ответа. Часто используют L = 0 или L = -inf, R = 10^9 или R = inf. Для вещественных чисел можно задать R = 1e9 и L = 0.
• Остановка для вещественных чисел: вместо сравнения с eps часто используют фиксированное число итераций (например, 100), чтобы избежать проблем с плавающей точкой.
• Обработка целых чисел: при поиске минимума условие остановки — L < R, а mid = (L + R) // 2. При поиске максимума — mid = (L + R + 1) // 2 (округление вверх), чтобы избежать бесконечного цикла.
• Проверка монотонности: если функция немонотонна, двоичный поиск по ответу неприменим; требуется другой метод (например, тернарный поиск).

Критика и ограничения

• Необходимость монотонности: метод не работает для немонотонных функций, что ограничивает его применение.
• Зависимость от точности проверки: если проверка содержит ошибки округления или неточности, результат может быть неверным.
• Вычислительная сложность проверки: если проверка сама по себе трудоёмка (например, O(N^2)), то даже логарифмическое число итераций может быть слишком большим.
• Сложность определения границ: в некоторых задачах трудно заранее установить, что для L условие не выполняется, а для R — выполняется.

Интересные факты

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

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — Глава 2, раздел «Двоичный поиск».
• Скиена С. Алгоритмы. Руководство по разработке. — 2-е изд. — СПб.: БХВ-Петербург, 2011. — Глава 4, раздел «Бинарный поиск».
• Материалы образовательных платформ Codeforces, Timus, e-olymp (разделы «Бинарный поиск по ответу», «Binary search on answer»).
• Лекции по дискретной математике и алгоритмам (МФТИ, ВШЭ, СПбГУ).