Бинарный поиск
Бинарный поиск по массиву и по ответу: O(log n), инварианты и типичные ошибки.
Если данные отсортированы (или условие монотонно: «до какого-то места — нет, дальше — да»), искать можно делением пополам: каждый шаг отбрасывает половину вариантов. Миллиард элементов — всего 30 шагов. Это и есть бинарный поиск, O(log n).
Писать его нужно аккуратно: ошибки «на единицу» и вечные циклы — визитная карточка темы. Надёжный шаблон — полуинтервал [l, r): ищем первый индекс, где условие выполняется.
Первое вхождение x. Введите: 6 5, затем отсортированный массив 1 3 5 5 7 9
В STL это уже есть: std::lower_bound(a.begin(), a.end(), x) возвращает итератор на первый элемент не меньше x, upper_bound — строго больше. Но писать поиск руками вы обязаны уметь — из-за главного олимпиадного приёма ниже.
Бинарный поиск ПО ОТВЕТУ. Часто сам ответ монотонен: «можно ли уложиться за время t?» — если можно за t, можно и за t+1. Тогда бинарным поиском ищется граница между «нельзя» и «можно», а вам остаётся написать только проверку. Пример: целочисленный квадратный корень — наибольшее m, такое что m² не превышает n.
Целочисленный корень бинпоиском по ответу. Введите: 1000000000000
Три классические ошибки:
1. Вечный цикл: если ищете ПОСЛЕДНЕЕ подходящее (l = mid), середину надо округлять вверх: (l + r + 1) / 2. Иначе при r - l = 1 цикл зависнет.
2. Переполнение середины: в других языках пишут l + (r - l) / 2; в C++ с long long обычно безопасно, но помните об этом.
3. Неверные границы: ответ обязан лежать в стартовом [l, r] — проверяйте крайние значения.
Задание: дано k станков, каждый печатает лист за t секунд, и нужно n листов. За какое минимальное время они справятся? Решите бинпоиском по ответу с проверкой «сколько листов успеем за время T».
Отметьте урок пройденным — Уровень 2 завершён!