Двоичный поиск в олимпиадной информатике: когда применять и как не ошибиться
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 классы.
Ответы
Ответов пока нет. Будьте первым, кто ответит.