Бинарный поиск по ответу: метод и примеры задач
Бинарный поиск по ответу - один из самых мощных алгоритмических приёмов: вместо прямого перебора кандидатов мы бинарно ищем само значение ответа на числовой оси. Ключевое условие - существование монотонного предиката: функция feasible(x) принимает значение «да» при и «нет» при (или наоборот). Это превращает задачу оптимизации в задачу поиска точки перехода, которую классический бинарный поиск находит за шагов. Чтобы почувствовать геометрию метода, покрутите калькулятор ниже - он покажет, как делится пространство ответов на каждой итерации.
Идея метода: от перебора к делению пополам
Классический бинарный поиск ищет элемент в отсортированном массиве. Бинарный поиск по ответу - ищет не элемент, а само значение ответа в числовом диапазоне . Вместо проверки «есть ли в массиве» используется предикат : «можно ли достичь ответа при данных ограничениях».
Монотонность предиката - обязательное условие: если истинно, то истинно для всех (при поиске минимума). Именно это позволяет отбрасывать половину диапазона на каждом шаге.
Схема алгоритма:
Структура кода на любом языке практически одинакова:
Ответ - значение в конце (наименьший , при котором истинно).
Как формулировать предикат
Правильный предикат - половина решения. Нужно перефразировать задачу: «при данном значении ответа - можно ли выполнить условие задачи?»
Типовые примеры:
- «Найти минимальное время, за которое рабочих выполнят задач» → предикат: «за время рабочие выполняют не менее задач» → проверяется за .
- «Найти минимальный максимум нагрузки при разбивке массива на частей» → предикат: «можно ли разбить массив на частей, каждая с суммой не более » → жадная проверка за .
- «Найти -е наименьшее расстояние между парами точек» → предикат: «количество пар с расстоянием не меньше » → проверка за .

Предикат должен быть:
- Монотонным: если истинно, то тоже истинно (при поиске минимума).
- Вычислимым: проверка одного значения занимает не более , иначе суммарная сложность становится неприемлемой.
Целочисленный и вещественный случаи
Выбор типа границ влияет на схему поиска.
Целочисленный поиск (поиск наименьшего , при котором предикат истинен):
Инвариант: ответ всегда в . Цикл заканчивается при - это и есть ответ.
Вещественный поиск (например, найти радиус круга):
Достаточно 50-100 итераций для точности при любом начальном диапазоне. Ошибка выбирается на порядок меньше нужной точности ответа.
Оценка сложности
Пусть диапазон ответов - , а проверка предиката занимает времени. Тогда:
Для типичных задач: если предикат проверяется за , то весь алгоритм работает за - логарифмическое ускорение по сравнению с перебором .
Частая ошибка: выбирать диапазон [0, n] вместо реального диапазона ответа. Если ответ может быть 10^9, то hi = n даст неверный результат. Всегда думайте: каков физический смысл минимального и максимального допустимого ответа.
Классические задачи
Задача 1: Разбивка книги на страницы. Дан массив из чисел (страниц в главах книги). Нужно разбить на частей так, чтобы максимальная сумма части была минимальной.
Предикат: «Можно ли разбить на частей с суммой каждой ?». Проверяется жадно за : идём слева направо, открываем новую часть, когда текущая сумма превысит .
Диапазон: (одна часть из одного элемента), (вся книга - одна часть).
Задача 2: рабочих, задач с временами . Каждый рабочий берёт задачи с суммой времени не более .
Предикат: «Успеют ли рабочих выполнить все задачи за время ?». Жадно: сортируем задачи по убыванию, раздаём рабочему с наименьшей нагрузкой - или просто считаем .
Задача 3: -е минимальное произведение. В двух отсортированных массивах найти -е наименьшее произведение пары.
Предикат: «Сколько пар имеют произведение ?». Для каждого - бинарный поиск по , итого .
Связь с параметрическим поиском
Бинарный поиск по ответу - частный случай параметрического поиска: мы параметризуем задачу значением и сводим оптимизацию к серии задач принятия решений. Этот подход объединяет несколько классов задач:
- Минимакс: минимизировать максимум чего-либо (нагрузки, расстояния, разности элементов).
- Максимин: максимизировать минимум (максимальный минимальный промежуток между точками при выборе объектов).
- Задачи на -й порядковый статистик: найти -й по величине элемент в структуре, где прямой доступ невозможен.
Во всех этих случаях предикат формулируется единообразно: «при пороге условие выполнено?». Разные задачи отличаются только тем, что именно подставить в это «условие» и как его проверить. Освоив шаблон бинарного поиска по ответу один раз, вы получаете инструмент, который применим к сотням соревновательных задач без изменения каркаса алгоритма.
Частые ошибки
- Неверные границы диапазона. Если или не покрывают реальный ответ, алгоритм даёт мусор. Всегда проверяйте: ложно, истинно (или наоборот) до запуска цикла.
- Не та схема обновления границ. Для поиска минимального с : истинно , иначе . Для максимального: наоборот. Перепутав, получите бесконечный цикл или неверный ответ.
- Целочисленное переполнение при вычислении mid. Вместо безопаснее - сумма может переполнить 32-битный тип.
- Немонотонный предикат. Если из не следует , бинарный поиск по ответу неприменим. Сначала докажите монотонность.
- Вещественная точность. При вещественном бинарном поиске нельзя использовать
while lo < hi- вещественные числа могут не сойтись. Нужноwhile hi - lo > epsили фиксированное число итераций (50-100).
FAQ
Чем бинарный поиск по ответу отличается от обычного? Обычный бинарный поиск ищет заданный элемент в отсортированном массиве. Поиск по ответу ищет само значение ответа: нет никакого массива, есть только диапазон возможных ответов и функция проверки. Метод применим, когда на вопрос «можно ли достичь результата » можно ответить быстро, а множество допустимых монотонно.
Всегда ли предикат должен быть монотонным? Да, это обязательное условие. Если функция «допустимости» меняет значение несколько раз на числовой оси, классический бинарный поиск даст неверный результат. В таких случаях нужны другие методы - тернарный поиск (для унимодальных функций) или разбиение на монотонные участки.
Когда использовать вещественный, а когда целочисленный бинарный поиск по ответу? Целочисленный - когда ответ целое число (количество, индекс, число шагов). Вещественный - когда ответ непрерывен (расстояние, время, минимальный радиус). Граница: если в задаче написано «найти наименьшее целое » - целочисленный; «найти минимальное расстояние» - вещественный с точностью или лучше.
Коротко
Бинарный поиск по ответу работает там, где ответ лежит на числовой оси, а предикат - монотонен: истинен для всех и ложен для (при поиске минимума). Алгоритм выполняет итераций, на каждой проверяя предикат - итоговая сложность . Ключевые шаги: сформулировать монотонный предикат, выбрать правильные границы диапазона и верную схему обновления /.
Читайте также

Алгоритм Хопкрофта-Карпа: паросочетание по фазам
Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе. Разбираем поиск кратчайших цепей, BFS и DFS, пример двух фаз и оценку сложности.

Дерево Фенвика: суммы и обновления по шагам
Дерево Фенвика хранит суммы блоков массива и помогает быстро отвечать на запросы и менять элементы. Разбираем lowbit, пример вычислений, реализацию на Python и сложность операций.

Метод Ньютона в оптимизации: формула и пример
Метод Ньютона для поиска минимума: как построить квадратичную модель, вычислить шаг по градиенту и гессиану и проверить условия сходимости на примере.

Метод ветвей и границ в целочисленном программировании
Метод ветвей и границ для целочисленной задачи: LP-релаксация, верхняя оценка, ветвление по дробной переменной и доказательство оптимума на числовом примере.

Список смежности: представление графа с примерами
Как построить список смежности графа по рёбрам и восстановить граф по спискам. Разбираем ориентированные и взвешенные графы, сложность операций и отличие от матрицы.

Тест Миллера-Рабина: проверка простоты числа
Как работает тест Миллера-Рабина: разложение числа n − 1, цепочка остатков, подробные примеры вычисления и оценка вероятности ошибки при независимых раундах проверки простоты.