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

Бинарный поиск по ответу - один из самых мощных алгоритмических приёмов: вместо прямого перебора кандидатов мы бинарно ищем само значение ответа на числовой оси. Ключевое условие - существование монотонного предиката: функция feasible(x) принимает значение «да» при $x \le x^*$ и «нет» при $x > x^*$ (или наоборот). Это превращает задачу оптимизации в задачу поиска точки перехода, которую классический бинарный поиск находит за $O(\log N)$ шагов. Чтобы почувствовать геометрию метода, покрутите калькулятор ниже - он покажет, как делится пространство ответов на каждой итерации.

Идея метода: от перебора к делению пополам

Классический бинарный поиск ищет элемент в отсортированном массиве. Бинарный поиск по ответу - ищет не элемент, а само значение ответа $x^*$ в числовом диапазоне $[lo, hi]$. Вместо проверки «есть ли $x$ в массиве» используется предикат $P(x)$: «можно ли достичь ответа $x$ при данных ограничениях».

Монотонность предиката - обязательное условие: если $P(x)$ истинно, то $P(x')$ истинно для всех $x' \le x$ (при поиске минимума). Именно это позволяет отбрасывать половину диапазона на каждом шаге.

Схема алгоритма:

Рассчитать для своей задачи

Структура кода на любом языке практически одинакова:

$$lo = \text{мин. возможный ответ}, \quad hi = \text{макс. возможный ответ}$$ $$\text{while } lo < hi: \quad mid = \lfloor (lo + hi) / 2 \rfloor$$ $$\text{if } P(mid) \text{ истинно} \Rightarrow hi = mid, \quad \text{иначе} \Rightarrow lo = mid + 1$$

Ответ - значение $lo$ в конце (наименьший $x$, при котором $P(x)$ истинно).

Как формулировать предикат

Правильный предикат - половина решения. Нужно перефразировать задачу: «при данном значении ответа $x$ - можно ли выполнить условие задачи?»

Типовые примеры:

• «Найти минимальное время, за которое $k$ рабочих выполнят $n$ задач» → предикат: «за время $x$ рабочие выполняют не менее $n$ задач» → проверяется за $O(k)$.
• «Найти минимальный максимум нагрузки при разбивке массива на $m$ частей» → предикат: «можно ли разбить массив на $m$ частей, каждая с суммой не более $x$» → жадная проверка за $O(n)$.
• «Найти $k$-е наименьшее расстояние между парами точек» → предикат: «количество пар с расстоянием $\le x$ не меньше $k$» → проверка за $O(n \log n)$.

Рассчитать для своей задачи

Предикат должен быть:

1. Монотонным: если $P(x)$ истинно, то $P(x+1)$ тоже истинно (при поиске минимума).
2. Вычислимым: проверка одного значения $x$ занимает не более $O(n \log n)$, иначе суммарная сложность $O(n \log n \cdot \log N)$ становится неприемлемой.

Целочисленный и вещественный случаи

Выбор типа границ влияет на схему поиска.

Целочисленный поиск (поиск наименьшего $x$, при котором предикат истинен):

$$lo = 0, \quad hi = N, \quad mid = \lfloor (lo + hi) / 2 \rfloor$$ $$P(mid) \text{ истинно} \Rightarrow hi = mid; \quad P(mid) \text{ ложно} \Rightarrow lo = mid + 1$$

Инвариант: ответ всегда в $[lo, hi]$. Цикл заканчивается при $lo = hi$ - это и есть ответ.

Вещественный поиск (например, найти радиус круга):

$$\text{while } hi - lo > \varepsilon: \quad mid = (lo + hi) / 2$$

Достаточно 50-100 итераций для точности $10^{-15}$ при любом начальном диапазоне. Ошибка $\varepsilon$ выбирается на порядок меньше нужной точности ответа.

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

Пусть диапазон ответов - $[0, N]$, а проверка предиката занимает $T(n)$ времени. Тогда:

$$\text{Число итераций} = \lceil \log_2 N \rceil$$ $$\text{Итоговая сложность} = O(T(n) \cdot \log N)$$

Для типичных задач: если предикат проверяется за $O(n)$, то весь алгоритм работает за $O(n \log N)$ - логарифмическое ускорение по сравнению с перебором $O(nN)$.

Классические задачи

Задача 1: Разбивка книги на страницы. Дан массив из $n$ чисел (страниц в главах книги). Нужно разбить на $m$ частей так, чтобы максимальная сумма части была минимальной.

Предикат: «Можно ли разбить на $m$ частей с суммой каждой $\le x$?». Проверяется жадно за $O(n)$: идём слева направо, открываем новую часть, когда текущая сумма превысит $x$.

Диапазон: $lo = \max(a_i)$ (одна часть из одного элемента), $hi = \sum a_i$ (вся книга - одна часть).

Задача 2: $k$ рабочих, $n$ задач с временами $t_i$. Каждый рабочий берёт задачи с суммой времени не более $x$.

Предикат: «Успеют ли $k$ рабочих выполнить все задачи за время $x$?». Жадно: сортируем задачи по убыванию, раздаём рабочему с наименьшей нагрузкой - или просто считаем $\sum \lfloor x / t_i \rfloor \ge n$.

Задача 3: $k$-е минимальное произведение. В двух отсортированных массивах найти $k$-е наименьшее произведение пары.

Предикат: «Сколько пар $(a_i, b_j)$ имеют произведение $\le x$?». Для каждого $a_i$ - бинарный поиск по $b_j$, итого $O(n \log n)$.

Связь с параметрическим поиском

Бинарный поиск по ответу - частный случай параметрического поиска: мы параметризуем задачу значением $x$ и сводим оптимизацию к серии задач принятия решений. Этот подход объединяет несколько классов задач:

• Минимакс: минимизировать максимум чего-либо (нагрузки, расстояния, разности элементов).
• Максимин: максимизировать минимум (максимальный минимальный промежуток между точками при выборе $k$ объектов).
• Задачи на $k$-й порядковый статистик: найти $k$-й по величине элемент в структуре, где прямой доступ невозможен.

Во всех этих случаях предикат формулируется единообразно: «при пороге $x$ условие выполнено?». Разные задачи отличаются только тем, что именно подставить в это «условие» и как его проверить. Освоив шаблон бинарного поиска по ответу один раз, вы получаете инструмент, который применим к сотням соревновательных задач без изменения каркаса алгоритма.

Частые ошибки

• Неверные границы диапазона. Если $lo$ или $hi$ не покрывают реальный ответ, алгоритм даёт мусор. Всегда проверяйте: $P(lo)$ ложно, $P(hi)$ истинно (или наоборот) до запуска цикла.
• Не та схема обновления границ. Для поиска минимального $x$ с $P(x)=\text{true}$: $P(mid)$ истинно $\Rightarrow hi=mid$, иначе $\Rightarrow lo=mid+1$. Для максимального: наоборот. Перепутав, получите бесконечный цикл или неверный ответ.
• Целочисленное переполнение при вычислении mid. Вместо $(lo+hi)/2$ безопаснее $lo + (hi-lo)/2$ - сумма $lo+hi$ может переполнить 32-битный тип.
• Немонотонный предикат. Если из $P(x)=\text{true}$ не следует $P(x+1)=\text{true}$, бинарный поиск по ответу неприменим. Сначала докажите монотонность.
• Вещественная точность. При вещественном бинарном поиске нельзя использовать while lo < hi - вещественные числа могут не сойтись. Нужно while hi - lo > eps или фиксированное число итераций (50-100).

FAQ

Чем бинарный поиск по ответу отличается от обычного? Обычный бинарный поиск ищет заданный элемент в отсортированном массиве. Поиск по ответу ищет само значение ответа: нет никакого массива, есть только диапазон возможных ответов и функция проверки. Метод применим, когда на вопрос «можно ли достичь результата $x$» можно ответить быстро, а множество допустимых $x$ монотонно.

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

Когда использовать вещественный, а когда целочисленный бинарный поиск по ответу? Целочисленный - когда ответ целое число (количество, индекс, число шагов). Вещественный - когда ответ непрерывен (расстояние, время, минимальный радиус). Граница: если в задаче написано «найти наименьшее целое $k$» - целочисленный; «найти минимальное расстояние» - вещественный с точностью $10^{-6}$ или лучше.

Коротко

Бинарный поиск по ответу работает там, где ответ $x^*$ лежит на числовой оси, а предикат $P(x)$ - монотонен: истинен для всех $x \ge x^*$ и ложен для $x < x^*$ (при поиске минимума). Алгоритм выполняет $O(\log N)$ итераций, на каждой проверяя предикат - итоговая сложность $O(T(n) \cdot \log N)$. Ключевые шаги: сформулировать монотонный предикат, выбрать правильные границы диапазона и верную схему обновления $lo$/$hi$.