Двоичный поиск на Python: как решать + 7 задач с проверкой

Двоичный поиск — это приём, который помогает быстро находить ответ там, где «всё упорядочено» или где есть чёткая граница между «подходит» и «не подходит». В олимпиадных задачах он часто встречается в запросах к отсортированному массиву (например, найти первый элемент не меньше x, последний не больше x, количество в диапазоне), а также в задачах на подбор минимального/максимального значения (время, скорость, порог, размер), которое удовлетворяет условию.

Как распознать двоичный поиск по условию:

• дан массив/список отсортирован или его можно сделать отсортированным;
• просят первую/последнюю позицию с условием ("первый не ниже", "последний не больше");
• нужно найти минимальный i или максимальный x, и есть проверка вида: при маленьком x «не проходит», а дальше начинает «проходить» (или наоборот);
• прямой перебор слишком медленный, но проверка одного кандидата быстрая.

Суть приёма: держим границы поиска и каждый раз проверяем середину. Если в середине уже «достаточно» (условие выполняется), сдвигаем правую границу; если нет — левую. Так мы каждый шаг уменьшаем диапазон вдвое и получаем не O(n), а O(log n) проверок, что особенно важно при больших n и множестве запросов.

С чего начать учиться:

• освоить два базовых варианта: поиск точного значения и поиск границы (lower_bound/upper_bound: первый >= x, первый > x);
• потренировать аккуратные границы: индексы, ответ «не найден», дубликаты;
• выучить шаблон «двоичный поиск по ответу» через монотонную функцию ok(mid);
• проверять себя на крайних случаях: пустой диапазон, все меньше x, все больше x, одинаковые элементы.

Ниже — задачи с автопроверкой и разбором подхода: начнёшь с простых границ в отсортированном массиве и перейдёшь к двоичному поиску по ответу.