Поиск и бинарный поиск, в том числе по ответу

Бинарный поиск — самый недооценённый алгоритм в индустрии. Его «знают все», но корректно с первого раза пишут единицы: Джон Бентли в 1980-х давал эту задачу профессиональным программистам, и около 90% решений содержали ошибку даже после нескольких часов работы. А Джошуа Блох в 2006 году нашёл переполнение в java.util.Arrays.binarySearch — коде, который девять лет лежал в стандартной библиотеке JDK и был формально верифицирован в книге Бентли.

Причина не в сложности идеи, а в том, что почти все пишут бинарный поиск по памяти, а не выводят его из инварианта. Эта статья строит его из инварианта — и дальше показывает, что бинарный поиск это вообще не «алгоритм для отсортированного массива», а общий приём поиска границы монотонного предиката, применимый к скорости поедания бананов, размеру батча на GPU, номеру коммита в git и пропускной способности сервиса.

Три вопроса перед выбором метода поиска

Сколько будет запросов? Один запрос к неотсортированным данным — это O(n) линейным поиском, и сортировать ради него бессмысленно. Порог окупаемости: q · n против n log n + q · log n, то есть сортировка выигрывает начиная примерно с q ≳ log n. Тот же размен «предобработка против запроса» объясняет, почему БД строит индексы.

Нужен ли порядок? Если нужен только факт наличия — хеш-таблица даёт в среднем константу и бьёт бинарный поиск. Бинарный поиск нужен, когда важны соседи: следующий элемент, диапазон [l, r], ближайшее значение, k-я порядковая статистика. Хеш этого не умеет.

Есть ли монотонность? Главный вопрос. Отсортированность массива — лишь частный случай монотонности предиката a[i] ≥ x. Научившись видеть монотонность там, где массива нет вообще, вы получаете основной инструмент.

Отдельно про линейный поиск: не спешите его хоронить. Для n в пределах 30–60 элементов он на практике часто быстрее бинарного — идеально предсказуем для префетчера, без непредсказуемых ветвлений, векторизуется. Поэтому гибридные сортировки (см. https://courses.digitable.life/post/algorithms/02-sorting/) переключаются на вставки на малых подмассивах, а реальные реализации бинарного поиска добирают хвост линейно.

Бинарный поиск, выведенный из инварианта

Забудьте формулировку «делим пополам и сравниваем с серединой». Правильная такая:

Есть монотонный предикат P на диапазоне индексов: сначала идут False, потом True, и переключение происходит ровно один раз. Задача — найти первый индекс, где P истинен.

Отсортированный массив даёт монотонность автоматически: если a не убывает, то P(i) = (a[i] ≥ x) монотонен, а его граница — это lower_bound.

def first_true(lo: int, hi: int, pred) -> int:
    """Наименьшее k в [lo, hi], для которого pred(k) истинен.

    Предусловие: pred монотонен — False...False True...True.
    Соглашение: pred(hi) считается истинным (hi — «страж» за концом диапазона),
    поэтому возврат hi означает «истинных значений внутри нет».

    Инвариант цикла: ответ всегда лежит в полуинтервале [lo, hi).
    Время: O(log(hi - lo)) вызовов pred. Память: O(1).
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2       # без переполнения; гарантированно mid ∈ [lo, hi)
        if pred(mid):
            hi = mid                    # ответ не правее mid
        else:
            lo = mid + 1                # ответ строго правее mid
    return lo                           # lo == hi, интервал схлопнулся

Корректность разбирается по трём пунктам, как в https://courses.digitable.life/post/algorithms/01-analysis-and-proofs/.

Инициализация. До первой итерации [lo, hi) — весь диапазон, и ответ по определению (с учётом стража) лежит в [lo, hi]. Договорённость «pred(hi) истинен» делает границу корректной и в вырожденном случае, когда истинных значений внутри нет.

Сохранение. Из lo < hi следует mid = lo + ⌊(hi−lo)/2⌋ ∈ [lo, hi), то есть mid < hi. Если pred(mid) истинен, граница не правее mid, и hi = mid её не теряет — mid остаётся кандидатом, потому что правый конец инварианта включительный. Если pred(mid) ложен, то по монотонности ложны все индексы ≤ mid, значит lo = mid + 1 тоже безопасно.

Завершение. Каждая итерация строго уменьшает hi − lo: при истинном pred(mid) уменьшается hi (так как mid < hi), иначе растёт lo. Цикл конечен, завершается при lo == hi, где инвариант оставляет единственного кандидата. Число итераций — ⌈log₂(hi − lo + 1)⌉.

Почему lo + (hi - lo) // 2, а не (lo + hi) // 2

В Python целые неограниченные, разницы нет. В Java, C, C++, Go, Rust, C# — есть: при lo и hi порядка 2³⁰ сумма переполняет 32-битный знаковый int, становится отрицательной, и mid уезжает за пределы массива. Именно этот баг девять лет жил в JDK. Форма lo + (hi - lo) // 2 математически эквивалентна, но не переполняется при lo ≤ hi. Пишите так везде, включая Python, — как мышечную память. Вариант (lo + hi) >>> 1 (беззнаковый сдвиг), которым чинили JDK, тоже корректен, но доступен не во всех языках.

lower_bound, upper_bound и весь семейный набор

def lower_bound(a, x):
    """Первый индекс i, где a[i] >= x. Точка вставки слева. O(log n)."""
    return first_true(0, len(a), lambda i: a[i] >= x)

def upper_bound(a, x):
    """Первый индекс i, где a[i] > x. Точка вставки справа. O(log n)."""
    return first_true(0, len(a), lambda i: a[i] > x)

def contains(a, x):
    i = lower_bound(a, x)
    return i < len(a) and a[i] == x

Одно правило — и границы больше не путаются:

Не пишите это руками — во всех языках есть готовое:

import bisect

a = [1, 3, 3, 4, 7, 9, 9, 12]
bisect.bisect_left(a, 9)                             # 5 — это lower_bound
bisect.bisect_right(a, 9)                            # 7 — это upper_bound
bisect.insort_left(a, 5)                             # вставка, O(n) из-за сдвига памяти
bisect.bisect_left(people, 34, key=lambda p: p[1])   # Python 3.10+: поиск по ключу

// Go: sort.Search — это ровно first_true с предикатом.
i := sort.Search(len(a), func(i int) bool { return a[i] >= x })
if i < len(a) && a[i] == x { /* нашли */ }
idx, found := slices.BinarySearch(a, x)   // Go 1.21+, обобщённая версия

• C++: std::lower_bound / upper_bound / equal_range — но на std::list это O(n) шагов при O(log n) сравнений.
• Java: Arrays.binarySearch возвращает -(точка вставки) - 1, если не нашёл, и не гарантирует, какое из одинаковых значений вернёт.
• Rust: partition_point — это буквально first_true.

Практический вывод: опирайтесь на partition_point-подобный примитив, а не на «поиск значения». Он покрывает все случаи, не требует помнить про точки вставки и обобщается на поиск по ответу.

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

Ключевое наблюдение: first_true нигде не обращается к массиву. Ему нужен только монотонный предикат и диапазон целых чисел. Значит, если ответ задачи — число k и выполняется свойство «если решение с параметром k возможно, то и с любым k' > k возможно», задача решается бинарным поиском по значению ответа, а pred(k) становится проверкой осуществимости.

Канонический пример — Koko Eating Bananas: есть кучи бананов, за час можно съесть не более k бананов из одной кучи; найти минимальное k, при котором всё съедается за h часов. Формулы нет, но проверить конкретное k тривиально, а монотонность очевидна: чем больше скорость, тем меньше часов.

def min_eating_speed(piles: list[int], h: int) -> int:
    def ok(k: int) -> bool:
        # ceil(p / k) часов на кучу p; целочисленный ceil без float
        return sum((p + k - 1) // k for p in piles) <= h

    # k = 0 бессмыслен; k = max(piles) заведомо подходит — это и есть страж справа.
    return first_true(1, max(piles), ok)

# Время: O(len(piles) · log(max(piles))). Память: O(1).

Главный инженерный приём здесь — что ok это отдельная, тестируемая функция. Если вы можете её написать и объяснить, почему она монотонна, задача решена. Если монотонность вызывает сомнения, проверьте её перебором на малых входах: предикат не должен «мигать» с True на False.

Ещё четыре узнаваемых шаблона:

• Минимизировать максимум. «Разделить массив на m частей, минимизировав максимальную сумму»: ok(S) = «влезаем в m частей при лимите S на часть», проверяется жадным проходом за O(n). Больший бюджет не может ухудшить ситуацию — монотонно. Итог: O(n · log(сумма)).
• Максимизировать минимум. «Расставить k коров по стойлам так, чтобы минимальный зазор был максимален»: ok(d) = «можно расставить k объектов с зазором ≥ d», жадно слева направо. Предикат здесь убывающий — ищите последний истинный, инвертировав шаблон.
• k-й элемент без материализации. Если умеете быстро считать «сколько элементов ≤ x», то k-й по порядку находится бинарным поиском по значению: так ищут k-й элемент матрицы, отсортированной по строкам и столбцам, и квантили по гистограмме.
• Обратная функция. Любое монотонное уравнение f(x) = y решается без производных — медленнее Ньютона (линейная сходимость против квадратичной), но надёжно и без требований гладкости.

Вещественный случай: считайте итерации, а не epsilon

def solve_monotone(f, lo: float, hi: float, y: float, iters: int = 100) -> float:
    """Решает f(x) = y для неубывающей f на [lo, hi]."""
    for _ in range(iters):
        mid = (lo + hi) / 2
        if f(mid) < y:
            lo = mid
        else:
            hi = mid
    return (lo + hi) / 2

Почему фиксированное число итераций, а не while hi - lo > eps? Потому что условие с eps даёт бесконечный цикл, когда hi и lo стали соседними представимыми числами и их среднее совпадает с одним из них: интервал перестал сужаться, а условие не выполнено. Особенно коварно на больших значениях, где шаг double заметно больше вашего 1e-9. Каждая итерация даёт бит точности; 60 итераций исчерпывают мантиссу double, 100 — с запасом. Это наносекунды и минус целый класс инцидентов. Если нужна относительная точность — берите относительный критерий или ищите по логарифму величины.

Тернарный поиск для унимодальных функций

Бинарный поиск требует монотонности. Если функция сначала убывает, потом возрастает, минимум ищется тернарным поиском: берём m1 = lo + (hi−lo)/3 и m2 = hi − (hi−lo)/3; если f(m1) < f(m2), то минимум не правее m2 (hi = m2), иначе lo = m1. Каждая итерация режет отрезок на треть, поэтому итераций нужно примерно в 1.7 раза больше, чем бинарному. На целых числах сведите его к бинарному по предикату f(m) < f(m + 1) — это снимает возню с округлением. Плато из равных значений ломает тернарный поиск полностью: он не отличает «ещё не дошли до дна» от «мы на плоском дне». Разбор — cp-algorithms: Ternary Search.

Экспоненциальный (galloping) поиск

Что если верхняя граница неизвестна — поток, API с пагинацией, монотонная функция без априорного максимума? Находим границу удвоением, потом обычный бинарный поиск:

def exponential_search(a, x) -> int:
    """lower_bound для x, когда искомая позиция вероятно близко к началу.
    O(log i), где i — итоговая позиция: не зависит от длины массива.
    """
    n = len(a)
    if n == 0:
        return 0
    bound = 1
    while bound < n and a[bound - 1] < x:      # удваиваем, пока не перескочили
        bound *= 2
    return first_true(bound // 2, min(bound, n), lambda i: a[i] >= x)

Фаза удвоения делает ⌈log₂(i+1)⌉ шагов, фаза бинарного поиска — столько же, итого O(log i). При i ≪ n это радикально быстрее O(log n), а в худшем случае лишь вдвое медленнее. Тот же приём работает в проде:

• Timsort — режим galloping при слиянии, когда один прогон систематически выигрывает; описание в Objects/listsort.txt CPython;
• пересечение инвертированных индексов в поисковых движках: по длинному постинг-листу прыгают галопом (advance / skipTo в Lucene);
• поиск по ответу без известной верхней границы.

Интерполяционный поиск

Если данные распределены примерно равномерно, можно угадывать позицию линейной интерполяцией — как ищут слово в словаре, открывая ближе к нужной букве: pos = lo + (x − a[lo]) · (hi − lo) / (a[hi] − a[lo]) вместо середины. Ожидаемая сложность на равномерном распределении — O(log log n) (разбор у Кнута, TAOCP, том 3, раздел 6.2.1), но худший случай — O(n): на экспоненциально растущих данных интерполяция каждый раз промахивается на один элемент. Не забудьте защиту от деления на ноль при a[hi] == a[lo].

На практике применяется редко: выигрыш в числе сравнений съедается делением (десятки тактов) и непредсказуемостью доступа. Разумный гибрид — несколько интерполяционных шагов с откатом на бинарный после фиксированного числа неудач; примерно так устроены learned-index структуры вроде RMI и PGM-index.

Сложность и нижняя граница

Бинарный поиск делает ⌈log₂(n+1)⌉ сравнений в худшем случае при O(1) дополнительной памяти, и это оптимально в модели сравнений. Доказательство — через дерево решений, тем же приёмом, что даёт границу Ω(n log n) для сортировки. Любой алгоритм на попарных сравнениях есть двоичное дерево решений; у него минимум n + 1 листьев (n позиций попадания плюс «не найдено»), а двоичное дерево высоты h имеет не более 2^h листьев. Из 2^h ≥ n + 1 получаем h ≥ log₂(n + 1), и бинарный поиск достигает этой границы.

Обойти её можно, только отказавшись от модели сравнений: хеширование (O(1) в среднем), интерполяция с предположением о распределении (O(log log n) в среднем) или van-Emde-Boas-структуры на целых ключах (O(log log U)).

Важнее числа сравнений часто число обращений к памяти: у бинарного поиска это log₂ n промахов кэша, у B-дерева с узлом в кэш-линию — log_B n, при B = 16 вчетверо меньше. Поэтому «теоретически оптимальный» бинарный поиск проигрывает на больших массивах — см. также https://courses.digitable.life/post/algorithms/17-streaming-and-external-memory/.

Кэш-дружественные раскладки: Eytzinger и B-tree layout

Классический бинарный поиск обращается к a[n/2], a[n/4], a[n/8]… — адреса разнесены на мегабайты, каждая проба это промах TLB и кэша, а адрес следующей пробы зависит от результата текущего сравнения, так что префетчер бесполезен. Решение — переложить массив в порядке обхода дерева поиска. В раскладке Eytzinger (BFS-layout, «раскладка кучи») корень лежит в ячейке 1, а потомки узла k — в ячейках 2k и 2k+1.

// Eytzinger-поиск: массив t одноиндексный, t[0] не используется.
// Возвращает индекс в eytzinger-массиве или 0, если все элементы меньше x.
func eytzingerSearch(t []int32, x int32) int {
    k := 1
    for k < len(t) {
        // Адреса 2k и 2k+1 соседние — префетчер покрывает обе ветки одним запросом.
        if t[k] < x {
            k = 2*k + 1
        } else {
            k = 2 * k
        }
    }
    // k «вывалился» за массив; последний поворот налево восстанавливаем сдвигом
    // на количество младших единиц плюс один.
    k >>= bits.TrailingZeros(^uint(k)) + 1
    return k
}

Что здесь выигрывается:

• Первые уровни дерева попадают в одну-две кэш-линии. 16 первых узлов int32 — это 64 байта, ровно одна линия: четыре первых сравнения бесплатны после первого промаха.
• Ветвление убирается. k = 2*k + b, где b — результат сравнения: арифметика вместо перехода, никаких штрафов за ошибку предсказателя (см. https://courses.digitable.life/post/algorithms/18-practical-optimization/).
• Префетч работает. Соседние 2k и 2k+1 позволяют подгружать данные на несколько уровней вперёд.

Пол-Вирджиль Хуонг и Пэт Морен в работе Array Layouts for Comparison-Based Searching измерили это аккуратно: Eytzinger с префетчем даёт ускорение в 2–4 раза относительно классического бинарного поиска на массивах, не помещающихся в кэш, а B-tree layout выигрывает ещё немного на очень больших объёмах. Цена: разовая перестройка O(n), неудобство итерации по порядку и диапазонных запросов, невозможность дешёвой вставки. Это оптимизация для статических больших индексов — ровно то, что лежит внутри аналитических БД и поисковых движков.

Если структура уже дерево — спускайтесь по нему

Частая ошибка: накрутить бинарный поиск поверх структуры, которая сама умеет спуск. Пример — «найти наименьший индекс с префиксной суммой ≥ k» в дереве Фенвика. Наивно это O(log² n) (log проб × log на запрос суммы), а спуск даёт O(log n):

def fenwick_kth(tree: list[int], n: int, k: int) -> int:
    """Наименьший i (одноиндексно) с префиксной суммой >= k. O(log n)."""
    pos, step = 0, 1 << n.bit_length()
    while step:
        nxt = pos + step
        if nxt <= n and tree[nxt] < k:
            pos = nxt
            k -= tree[pos]
        step >>= 1
    return pos + 1

Так реализуют k-ю порядковую статистику в мультимножестве, скользящую медиану и квантили в мониторинге. Аналогично устроен спуск по дереву отрезков и по B-дереву.

Типичные ошибки

1. Переполнение в (lo + hi) / 2 — реальный баг в языках с фиксированной шириной int.
2. Бесконечный цикл при lo = mid вместо lo = mid + 1: при hi = lo + 1 получаем mid = lo, и lo не двигается. Правило: хотя бы одна граница должна двигаться строго. Шаблон first_true обладает этим свойством по построению.
3. Немонотонный предикат в поиске по ответу — самая опасная ошибка, потому что код не падает, а молча возвращает мусор на части входов. Проверяйте рассуждением и перебором на малых входах.
4. Данные отсортированы не по тому ключу, по которому ищете (по id, а ищете по timestamp). Бинарный поиск не может это заметить; в отладочных сборках проверяйте is_sorted за O(n).
5. while hi - lo > eps в вещественном поиске — бесконечный цикл на границах double.
6. «Найти значение» при дубликатах: Arrays.binarySearch и аналоги не гарантируют, какое вхождение вернут. Нужен первый или последний — берите lower_bound / upper_bound.
7. Бинарный поиск без random access (связный список, forward-итераторы) — сложность незаметно превращается в линейную.
8. Не обработан случай «ответа нет»: проверяйте i < n && a[i] == x, а в поиске по ответу заранее убедитесь, что правая граница действительно осуществима.
9. Смешение [lo, hi] и [lo, hi) в одном коде. Выберите одно соглашение — рекомендую полуинтервал — и держите его везде.
10. Дорогой предикат внутри логарифма: first_true вызывает pred log n раз, и если pred стоит O(n log n), итог O(n log² n) может оказаться хуже прямого решения.

Как это выглядит в проде

Индексы баз данных. B-дерево в PostgreSQL, InnoDB, SQLite — это бинарный поиск, адаптированный к блочной памяти: внутри страницы (8–16 КБ) идёт бинарный поиск по слоту, между страницами — спуск по дереву. Стоимость запроса меряется не сравнениями, а числом прочитанных страниц: log_B n вместо log₂ n.

LSM-деревья и колоночные форматы. В RocksDB у каждого SSTable есть разреженный индекс блоков: поиск ключа — это фильтр Блума, затем бинарный поиск по индексу, чтение одного блока и бинарный поиск внутри него. В Parquet так же ищут row group по min/max статистикам.

Поисковые движки. Пересечение постинг-листов в Lucene использует galloping-поиск, а skip-списки внутри списка — это заранее материализованные точки бинарного поиска.

git bisect. Прямое применение поиска границы монотонного предиката: «в этом коммите баг есть» монотонно по истории, если баг внесён одним коммитом и не чинился. git bisect run ./test.sh автоматизирует всё и находит виновника за log₂ N прогонов вместо N.

Нагрузочное тестирование и capacity planning. Найти максимальный RPS, при котором p99 держится ниже SLO, — это поиск по ответу с ok(rps) = «прогон выдержал SLO». Предикат практически монотонен, а проверка стоит минуты, поэтому логарифм экономит часы. Тем же приёмом подбирают максимальный batch size, влезающий в память GPU, и порог классификатора под целевую точность (precision монотонна по порогу — см. https://courses.digitable.life/post/machine-learning/00-overview/). Вообще любая настройка вида «найти наибольшее значение параметра, при котором система ещё работает» — от Path MTU Discovery до размеров буферов — это first_true.

Ещё три варианта, которые стоит знать

Поиск в повёрнутом массиве вида [7, 9, 12, 1, 3, 4]. Глобальной монотонности нет, но на каждом шаге одна из половин гарантированно отсортирована — определяем какая (сравнив a[lo] с a[mid]), проверяем, попадает ли x в её диапазон, и отбрасываем половину. O(log n) при различных элементах; дубликаты роняют худший случай до O(n), потому что a[lo] == a[mid] == a[hi] не даёт информации.

Поиск пика. В массиве, где a[i] != a[i+1], локальный максимум ищется за O(log n) по предикату a[mid] > a[mid + 1] — хотя массив вообще не отсортирован. Хороший тест на понимание: монотонность нужна не данным, а предикату.

Параллельный бинарный поиск. Когда нужно ответить на q независимых запросов «в какой момент выполнилось условие», все q поисков ведут синхронно: на каждом из log уровней группируем запросы по текущим серединам и обрабатываем события одним проходом. Вместо O(q · log · f) получается O(log · (q + f)). Разбор — в cp-algorithms; часто нужен вместе с DSU (см. https://courses.digitable.life/post/algorithms/10-mst-and-flows/). Родственный приём — фракционный каскадинг: поиск одного ключа в k отсортированных списках за O(log n + k) вместо O(k log n), базовая техника вычислительной геометрии (https://courses.digitable.life/post/algorithms/12-computational-geometry/).

Мини-итог

• Бинарный поиск — это поиск границы монотонного предиката, а не «деление массива пополам». Пишите first_true(lo, hi, pred) и выражайте через него всё остальное.
• Один шаблон на полуинтервале [lo, hi) закрывает lower_bound, upper_bound, подсчёты, предшественника и поиск по ответу. Не заводите пять вариантов с разными границами.
• mid = lo + (hi - lo) // 2. Всегда.
• Поиск по ответу превращает «не знаю формулу» в «умею проверить кандидата»: сложность становится O(стоимость проверки · log диапазона).
• Вещественный поиск — фиксированные 60–100 итераций, никогда не while hi - lo > eps.
• O(log n) сравнений оптимальны в модели сравнений, но log n промахов кэша — нет: на больших статических массивах Eytzinger и B-tree layout дают кратное ускорение.
• Если структура уже дерево — спускайтесь по нему, а не оборачивайте запросы бинарным поиском.

Источники

• T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4-е изд. — поиск, деревья решений, нижние границы.
• D. Knuth. TAOCP, том 3, раздел 6.2.1 «Searching an Ordered Table» — каноническая история бинарного и интерполяционного поиска.
• J. Bentley. Programming Pearls, 2-е изд., колонки 4 и 9 — вывод бинарного поиска из инварианта.
• J. Bloch. Nearly All Binary Searches and Mergesorts Are Broken, 2006.
• P.-V. Khuong, P. Morin. Array Layouts for Comparison-Based Searching, arXiv:1509.05053.
• R. Sedgewick, K. Wayne. Algorithms, 4th ed.
• cp-algorithms: Binary search, Ternary search.
• Доки: Python bisect, Go sort.Search, C++ std::lower_bound, Rust binary_search, git bisect, CPython listsort.txt.

Что дальше

Бинарный поиск сужает интервал прыжками. Есть противоположный по духу приём — два указателя, которые движутся монотонно и вместе дают O(n) там, где наивно получается O(n²). Он тоже опирается на монотонность, но использует её совсем иначе.

Два указателя и скользящее окно