Идея бинарного поиска

Если массив отсортирован, мы можем не идти по нему линейно. На каждом шаге мы делим оставшийся диапазон пополам и решаем, в какой половине искать. После каждого сравнения остаётся половина пространства поиска. Через k шагов от n элементов остаётся n / 2^k. Нам нужно n / 2^k = 1, отсюда k = log2(n).

Для миллиона элементов это 20 шагов. Для миллиарда — 30. Это и есть «магия» O(log n): рост настолько медленный, что практически не зависит от размера данных.

Инварианты

Бинарный поиск — алгоритм, где легко допустить ошибку, если не держать в голове инвариант. Инвариант — это условие, истинное на каждой итерации. Самая распространённая формулировка:

Если target существует, он лежит в полуоткрытом интервале [lo, hi). Всё, что слева от lo — точно меньше target. Всё, что справа от hi — точно больше или равно.

Эту формулировку нужно проговаривать вслух, потому что она диктует все границы:

• Начальные значения: lo = 0, hi = len(xs). Не hi = len(xs) - 1 — это другая версия с закрытым интервалом.
• Условие цикла: while lo < hi. Не <=.
• Обновление: если xs[mid] < target, то lo = mid + 1. Если xs[mid] >= target, то hi = mid.
• Возврат: после цикла lo == hi — это и есть позиция вставки или нахождения.

Разные книги выбирают разные конвенции (закрытый интервал, открытый, полуоткрытый). Важно выбрать одну и держаться её. Смешивать нельзя — получите off-by-one.

Итеративная реализация

def binary_search(xs, target):
    """
    Возвращает индекс target в отсортированном xs, или -1, если нет.
    Используем полуоткрытый интервал [lo, hi).
    """
    lo, hi = 0, len(xs)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if xs[mid] == target:
            return mid
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

Каждая строка тут — последствие инварианта.

lo + (hi - lo) // 2 вместо (lo + hi) // 2 — это защита от переполнения целого, актуальная в C/Java. В Python целые без ограничений, но я пишу так из привычки: один из самых известных багов в индустрии (баг в Java Arrays.binarySearch, 9 лет жил незамеченным) был именно (lo + hi) / 2. Об этом — в следующем уроке.

Поиск позиции вставки (lower_bound)

В Data Engineering чаще нужен не «найти равный», а «найти позицию, куда вставить, чтобы сохранить порядок» (или «найти первый элемент, не меньше target»):

def lower_bound(xs, target):
    """Первая позиция, где xs[i] >= target."""
    lo, hi = 0, len(xs)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo   # позиция вставки, даже если target нет

Этот вариант не возвращает -1: если target нет, он возвращает позицию, куда бы его вставили. Это и есть bisect.bisect_left из стандартной библиотеки Python — мы дальше будем использовать именно её.

import bisect

xs = [5, 12, 18, 25, 30, 42, 55]

# найти позицию для вставки 27 (сохранив порядок)
print(bisect.bisect_left(xs, 27))   # 4

# найти позицию существующего элемента
print(bisect.bisect_left(xs, 30))   # 4

# bisect_right — позиция ПОСЛЕ всех равных
print(bisect.bisect_right(xs, 30))  # 5

Разница между bisect_left и bisect_right важна при дубликатах: если есть несколько равных, _left даёт первую позицию, _right — последнюю + 1. Их разница — количество равных элементов.

Почему именно O(log n)

Покажем на числах:

Удвоение размера данных добавляет один шаг. Удесятерение — три шага. Это и есть смысл логарифмической сложности: вы платите за поиск практически фиксированную цену.

Цена сортировки

Бинарный поиск требует отсортированных данных. Сортировка — O(n log n). Если вы планируете делать поиск один раз, бинарный поиск проигрывает линейному: O(n log n) + O(log n) хуже, чем O(n).

Бинарный поиск окупается, когда:

1. Данные уже отсортированы (например, индекс в БД).
2. Сортировка делается один раз, а поисков много.
3. Данные приходят отсортированными (например, log по времени).

Если данные постоянно меняются и сортировать после каждой вставки накладно — нужны структуры, которые поддерживают порядок инкрементально: SortedList, B-tree, skip list. О sortedcontainers будет следующий урок.

Замеры

Сравним линейный и бинарный поиск на миллионе элементов:

import timeit
import bisect

n = 1_000_000
xs = list(range(n))
target = n - 1   # худший случай для линейного

# linear
t_linear = timeit.timeit(lambda: target in xs, number=100)

# binary (через bisect)
def bsearch(xs, t):
    i = bisect.bisect_left(xs, t)
    return i < len(xs) and xs[i] == t

t_binary = timeit.timeit(lambda: bsearch(xs, target), number=100)

print(f"linear: {t_linear * 10:.2f} ms per call")
print(f"binary: {t_binary * 1e6:.2f} us per call")
print(f"speedup: {t_linear / t_binary:.0f}x")

Типичный результат: linear около 8 мс, binary около 2 микросекунд. Ускорение порядка 4000 раз — это и есть log(1 000 000) / 1 000 000 умноженное на разницу констант.

Попробуй сам

Реализуйте бинарный поиск сами и проверьте на разных случаях:

def binary_search(xs, target):
    lo, hi = 0, len(xs)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if xs[mid] == target:
            return mid
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

# базовые случаи
assert binary_search([], 5) == -1
assert binary_search([5], 5) == 0
assert binary_search([5], 3) == -1
assert binary_search([1, 3, 5, 7, 9], 7) == 3
assert binary_search([1, 3, 5, 7, 9], 1) == 0
assert binary_search([1, 3, 5, 7, 9], 9) == 4
assert binary_search([1, 3, 5, 7, 9], 4) == -1

# граничные
assert binary_search([1, 2], 1) == 0
assert binary_search([1, 2], 2) == 1
assert binary_search([1, 2], 3) == -1

print("ok")

Если хоть один assert падает — у вас off-by-one. Это нормально с первого раза. Поправьте границы и повторите. Полный пройденный набор unit-тестов — единственный способ убедиться, что ваш бинарный поиск работает.