Бинарный (двоичный) поиск по ответу


Бинарный (двоичный) поиск по ответу

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

Задача для тренировки:

Бинарный (двоичный) поиск по ответу (C++)

Бинарный (двоичный) поиск по ответу

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

Задача для тренировки:

Бинарный (двоичный) поиск по ответу (Python)