Бинарный поиск (binary search) — самый известный способ найти цель в отсортированной последовательности. На каждом шаге сравниваем со средним элементом и отбрасываем половину, где цели быть не может. Время O(log n): для миллиарда элементов всего 30 шагов. Для сравнения: линейный поиск — O(n).

![Поиск 23 в [2, 5, ..., 91]: три шага](img/lessons/algorithms/binary-search-trace.svg)

Алгоритм и инвариант

Держим две границы lo и hi, они задают замкнутый интервал a[lo..hi]. Инвариант: если x есть в списке, он в этом интервале. mid = (lo + hi) // 2 — середина. Если a[mid] == x, нашли. Если a[mid] < x, x может быть только справа: lo = mid + 1. Иначе слева: hi = mid - 1. Когда интервал опустел (lo > hi), x нет. Каждый шаг вдвое сужает интервал, поэтому шагов не больше floor(log2 n) + 1.

python
def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:                 # x, if present, lies in a[lo..hi]
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            lo = mid + 1            # discard the left half
        else:
            hi = mid - 1            # discard the right half
    return -1