Как работает бинарный поиск?

Условие — данные упорядочены. Держим границы lo и hi, внутри которых может быть искомое. Смотрим на средний элемент:

• равен искомому — нашли;
• меньше — искомое правее, lo = mid + 1;
• больше — левее, hi = mid - 1.

Каждый шаг уменьшает область вдвое, поэтому шагов не больше log₂ n + 1. Для сравнения: линейный поиск в худшем случае смотрит все n элементов.

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

• неверные границы и условие цикла (< против <=), из-за чего пропускается последний элемент или цикл не заканчивается;
• в языках с переполнением целых — (lo + hi) / 2 может переполниться; безопасно lo + (hi - lo) / 2;
• поиск в неотсортированных данных.

Варианты: найти первое или последнее вхождение (lower bound / upper bound — не останавливаться при равенстве, а сдвигать границу), найти место вставки (bisect в Python). Поиск по ответу — когда есть монотонное условие: «минимальная пропускная способность, при которой всё успеем», «первая сломанная версия» (git bisect).

def lower_bound(a, target):
    """Первый индекс i, где a[i] >= target (или len(a))."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 3, 3, 3, 7, 9]
lower_bound(a, 3)   # 1 — первое вхождение
lower_bound(a, 4)   # 4 — место вставки