Двоичный поиск в олимпиадной информатике: когда применять и как не ошибиться

1 мин чтения

Двоичный (бинарный) поиск — первый алгоритм, который отделяет решение «на частичные баллы»
от полного решения на олимпиаде по информатике.

Когда он нужен

  • Ограничения большие (n до 10⁵–10⁶, значения до 10⁹), а перебор всех вариантов не укладывается во время.
  • Есть монотонность: если ответ x подходит, то подходит и любой больший (или меньший).
  • Формулировка «найдите минимальное/максимальное значение, при котором…» — почти всегда бинпоиск по ответу.

Шаблон без ошибок

Держите инвариант: l — точно «плохо», r — точно «хорошо».

l, r = 0, 10**9 + 1
while r - l > 1:
    m = (l + r) // 2
    if good(m): r = m
    else: l = m
print(r)

Цикл останавливается, когда границы соседние, и ответ — r. Такой вариант не зацикливается и не теряет крайние значения.

Пример задачи

Нужно распилить брёвна на k кусков одинаковой длины, длина — как можно больше. Функция good(L): сумма (длина бревна // L) ≥ k.
Чем меньше L, тем больше кусков — монотонность есть, значит бинпоиск по L.

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

  • Переполнение при (l + r) в C++ — используйте long long или l + (r − l) / 2.
  • Неверные стартовые границы: r должен быть заведомо «хорошим», l — заведомо «плохим».
  • Поиск по вещественным числам: делайте фиксированное число итераций (60–100), а не сравнение с eps.

Есть вопрос по задаче или теме — пишите в наш Telegram, разберём.

Частые вопросы

Когда проходит Двоичный поиск в олимпиадной информатике: когда применять и как не ошибиться?

Ограничения большие (n до 10⁵–10⁶, значения до 10⁹), а перебор всех вариантов не укладывается во время. Есть монотонность: если ответ x подходит, то подходит и любой больший (или меньший). Формулировка «найдите минимальное/максимальное значение, при котором…» — почти всегда бинпоиск по ответу.

Для каких классов эта работа?

7–11 классы.

Ответы

Ответов пока нет. Будьте первым, кто ответит.

Ответы и разборы — в Telegram