Бинарный (двоичный) поиск по ответу
Существует класс задач, в которых мы можем быстро проверять является ли какое-либо значение ответом к задаче или нет. Но сам ответ быстро найти не можем. При этом, мы можем сказать, что ответ всегда лежит в определенных границах. Кроме этого, если перебирать значения линейным перебором (от минимально возможного до максимального возможного) и проверять подходит ли нам это значение в качестве ответа, то мы будем получать такие ответы: нет нет ... нет да да ... да (или наоборот, сначала да, потом нет).
В этом случае, мы можем для поиска ответа использовать двоичный поиск.
Основная идея решения задачи методом двоичного поиска заключается в том, чтобы сформулировать задачу "найдите максимальное (минимальное) X, такое что какое-то свойство от X выполняется" и решить её, подбирая значение X бинпоиском.
Обычно, для нахождения ответа методом двоичного поиска, создают отдельную функцию, которая проверяет может ли являться переданное значение ответом или нет и возращает
True или
False.
Сам двоичный поиск будет выглядеть следующим образом (приведем 2 варианта реализации, которых достаточно для решения любой задачи).
// Функция check() возвращает
// сначала True, потом False
// Необходимо найти
// последний check() == True
l = 0;
r = ??? // определяется из условия
while (l + 1 < r)
{
m = (l + r) / 2;
if (check(m))
l = m;
else
r = m;
}
if (check(r))
ans = r;
elif (check(l))
ans = l;
else
ans = -1; // решения нет
|
// Функция check() возвращает
// сначала False, потом True
// Необходимо найти
// первый check() == True
l = 0
r = ??? // определяется из условия
while (l + 1 < r)
{
m = (l + r) / 2;
if (not check(m))
l = m;
else
r = m;
}
if (check(l))
ans = l;
elif (check(r))
ans = r;
else
ans = -1; // решения нет
|
Значения границ (
l и
r) выбираются таким образом, что при значении
l точно не подходит (не является решением), значение
r точно подходит, хоть это значение и не является оптимальным.