Бинарный (двоичный) поиск по ответу
Существует класс задач, в которых мы можем быстро проверять является ли какое-либо значение ответом к задаче или нет. Но сам ответ быстро найти не можем. При этом, мы можем сказать, что ответ всегда лежит в определенных границах. Кроме этого, если перебирать значения линейным перебором (от минимально возможного до максимального возможного) и проверять подходит ли нам это значение в качестве ответа, то мы будем получать такие ответы: нет нет ... нет да да ... да (или наоборот, сначала да, потом нет).
В этом случае, мы можем для поиска ответа использовать двоичный поиск.
Основная идея решения задачи методом двоичного поиска заключается в том, чтобы сформулировать задачу "найдите максимальное (минимальное) 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 точно подходит, хоть это значение и не является оптимальным.