Бинарный поиск

Интуиция: игра «угадай число»

Друг загадал число от 1 до 100. Ты называешь 50, он отвечает «больше». Ты называешь 75, он отвечает «меньше». Каждый вопрос отрезает половину вариантов, поэтому за 7 вопросов ты угадаешь любое число. Это и есть бинарный поиск.

Работает он только при одном условии: данные упорядочены. Тогда по одному сравнению видно, в какой половине ответ, и вторую половину можно смело выбросить.

Классический поиск: схема

Ищем 9 в отсортированном массиве. Держим две границы left и right, смотрим в середину mid.

Три шага вместо пяти. На миллионе элементов понадобится около 20 шагов вместо миллиона.

Инвариант: как не ошибиться с границами

Почти все баги в бинпоиске связаны с границами. Чтобы их избежать, договорись с собой об инварианте, то есть о правиле, которое верно на каждом шаге:

Если ответ есть, он лежит в отрезке [left, right] включительно.

Из этого правила следуют все детали:

• Старт: left = 0, right = n - 1, потому что весь массив — кандидат.
• Цикл while left <= right: пока отрезок не пуст, искать есть где. При left == right остаётся ровно один кандидат, и его тоже надо проверить.
• Сдвиг left = mid + 1 / right = mid - 1: сам mid мы уже проверили, поэтому его исключаем. Если написать left = mid, цикл может зависнуть навсегда.
• Середина mid = left + (right - left) / 2: запись (left + right) / 2 в Java, C++ и Go может переполнить int на больших индексах. В Python переполнения нет, но привычку лучше держать одну на все языки.

Совет: если сомневаешься, прогони код руками на массиве из 1 и 2 элементов. Так ловится 90% ошибок с границами.

Позиция вставки (lower bound)

Часто вопрос звучит не «есть ли элемент?», а «куда его вставить, чтобы массив остался отсортированным?». Иначе говоря, нужен первый индекс, где a[i] >= target.

Здесь удобнее полуоткрытый отрезок [left, right):

• старт: left = 0, right = n. Ответ может быть и n, если элемент больше всех;
• цикл while left < right;
• если a[mid] < target, ответ правее: left = mid + 1;
• иначе mid может оказаться ответом, поэтому его не выбрасываем: right = mid.

Цикл закончится при left == right, и это и есть ответ. Главное, не смешивай две схемы в одном коде. Выбери пару «<= и mid ± 1» или пару «< и right = mid» и держись её до конца.

Бинарный поиск по ответу

Самый мощный приём главы. Иногда массива нет вовсе, но есть вопрос вида «какое минимальное k подходит?», и проверка «хватит ли k?» монотонна:

k	1	2	3	4	5	6
хватит?	нет	нет	нет	да	да	да

Если k хватает, то большего k тоже хватит. Значит, ответы выстроены как «нет-нет-нет-да-да», и нужно найти первое «да». Это тот же lower bound, только вместо массива у нас функция ok(k).

Пример для шаблона: у нас pages страниц и T минут, каждый принтер печатает страницу в минуту. Сколько минимум принтеров нужно? Проверка: ok(k) = k * T >= pages. Ответ тут можно посчитать и формулой, но на собесе ok обычно сложнее, например с жадным проходом по массиву. Схема поиска при этом остаётся той же.

Алгоритм по шагам:

1. Задай границы lo и hi, где ok(hi) гарантированно истинно.
2. Ищи первое k, для которого ok(k) истинно.

Шаблон

def binary_search(a, target):
    left, right = 0, len(a) - 1
    while left <= right:                  # ответ в [left, right]
        mid = left + (right - left) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(a, target):
    left, right = 0, len(a)               # ответ в [left, right)
    while left < right:
        mid = left + (right - left) // 2
        if a[mid] < target:
            left = mid + 1
        else:
            right = mid                   # mid может быть ответом
    return left

def min_k(lo, hi, ok):
    # первое k в [lo, hi], где ok(k) истинно; ok(hi) обязано быть True
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

# пример: 100 страниц, 30 минут, сколько принтеров?
print(min_k(1, 100, lambda k: k * 30 >= 100))  # 4

Сложность

Вариант	Время	Память
Классический / lower bound	O(log n)	O(1)
По ответу	O(log(hi − lo) · стоимость ok)	O(1)

Как это звучит на собесе

«Массив отсортирован, значит, можно отбрасывать половину за шаг. Это бинарный поиск за O(log n). Держу инвариант: ответ лежит в [left, right]. Середину считаю как left + (right - left) / 2, чтобы не было переполнения».

Для поиска по ответу: «Проверка "хватит ли k" монотонна: если хватает k, то хватит и k+1. Поэтому ищу минимальное подходящее k бинпоиском по диапазону ответов».

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

• Смешали схемы: написали while left < right и при этом right = mid - 1. В итоге один кандидат остаётся непроверенным.
• left = mid при mid с округлением вниз: на двух элементах получается вечный цикл.
• Неверная граница hi в поиске по ответу: ok(hi) должно быть истинным, иначе результат бессмыслен.
• Переполнение в ok: произведения вроде k * T считай в long.
• Забыли про сортировку: на неотсортированном массиве бинпоиск молча возвращает чушь.

Запомни одну фразу: «инвариант + монотонность». Если ты можешь их назвать, бинпоиск у тебя под контролем.