Бинарный поиск — алгоритм с подвохом

Существует классическая шутка: «90% программистов не могут с первого раза написать корректный бинарный поиск». Это не преувеличение. Дональд Кнут писал, что первая публикация бинарного поиска появилась в 1946 году, а первая корректная реализация без багов — только в 1962. Шестнадцать лет на алгоритм из десяти строк.

Кажется, что три строки кода — что там может пойти не так? Оказывается, многое. И эти баги переживают код-ревью, потому что они проявляются только на граничных случаях.

Баг #1: знаменитый overflow (lo + hi) / 2

В 2006 году Joshua Bloch (автор Effective Java, тот самый) опубликовал пост «Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken». Он нашёл баг в реализации Arrays.binarySearch в JDK, который жил там девять лет.

Баг был в строчке вычисления середины:

int mid = (lo + hi) / 2;

Выглядит безобидно? Проблема в том, что в Java int — 32-битное со знаком, максимум 2^31 - 1 ~ 2.15 миллиарда. Если массив большой (а в Java бывают массивы по миллиарду элементов), и lo + hi превышает MAX_INT, происходит integer overflow. Сумма становится отрицательной, деление на 2 даёт отрицательное число, индексация падает или возвращает мусор.

Правильная форма:

int mid = lo + (hi - lo) / 2;

Тут разность hi - lo всегда меньше или равна размеру массива, переполнения нет.

В Python этого бага нет: целые числа неограниченные, переполнения не бывает. Но в C, C++, Java, Rust, Go — он есть. И если вы когда-нибудь будете писать критичный код на этих языках, помните: lo + (hi - lo) / 2.

Я и в Python пишу так — из привычки и чтобы код был портабельным. Это не вредит, и приучает к правильному паттерну.

Баг #2: off-by-one в условиях цикла

Это убийца №1 бинарного поиска. Все варианты:

# вариант A — полуоткрытый [lo, hi)
lo, hi = 0, len(xs)
while lo < hi:
    ...
    lo = mid + 1   # после неравенства <
    hi = mid       # без -1

# вариант B — закрытый [lo, hi]
lo, hi = 0, len(xs) - 1
while lo <= hi:
    ...
    lo = mid + 1
    hi = mid - 1   # с -1

Оба варианта корректны, но смешивать их нельзя. Типичная ошибка джуна:

# СЛОМАНО: смешан полуоткрытый и закрытый
lo, hi = 0, len(xs)         # полуоткрытый
while lo <= hi:             # но условие как у закрытого
    mid = (lo + hi) // 2
    if xs[mid] < target:
        lo = mid + 1
    else:
        hi = mid             # тут забыли -1

Этот код входит в бесконечный цикл, когда target отсутствует и lo == hi. Условие lo <= hi остаётся true, hi = mid = lo, цикл крутится.

Способ избежать: выберите одну конвенцию и пишите её всегда. Я предпочитаю полуоткрытый интервал — он лучше согласуется с range(0, n) и slicing в Python.

Баг #3: неправильное обновление границ

Ещё одна классика:

# ПЛОХО
while lo < hi:
    mid = lo + (hi - lo) // 2
    if xs[mid] < target:
        lo = mid     # забыли + 1!
    else:
        hi = mid

Когда lo == hi - 1 (то есть остался один элемент), mid = lo. Если xs[mid] < target, мы делаем lo = mid = lo — ничего не изменилось, цикл крутится бесконечно.

Правило: если использовали проверку без равенства (<), обновление обязательно с +1 или -1. Только так гарантировано убывание разности hi - lo.

Баг #4: граничные случаи

Что должен возвращать бинарный поиск, если:

• Массив пустой? binary_search([], 5) — должно быть -1, а не падение.
• Target меньше первого? binary_search([5, 10], 1) — должно быть -1.
• Target больше последнего? binary_search([5, 10], 20) — должно быть -1.
• Массив из одного элемента? binary_search([5], 5) — должно быть 0.
• Дубликаты? binary_search([1, 2, 2, 2, 3], 2) — что возвращать? Первое вхождение? Последнее? Любое?

Эти случаи всегда надо проверять unit-тестами. Большинство багов в проде — на пустых массивах или на массивах из одного элемента.

# минимальный набор тестов для бинарного поиска
def test_binary_search():
    bs = binary_search

    # пустой массив
    assert bs([], 5) == -1

    # один элемент
    assert bs([5], 5) == 0
    assert bs([5], 3) == -1
    assert bs([5], 7) == -1

    # два элемента
    assert bs([1, 2], 1) == 0
    assert bs([1, 2], 2) == 1
    assert bs([1, 2], 0) == -1
    assert bs([1, 2], 3) == -1

    # границы
    xs = [1, 3, 5, 7, 9]
    assert bs(xs, 1) == 0
    assert bs(xs, 9) == 4
    assert bs(xs, 0) == -1
    assert bs(xs, 10) == -1
    assert bs(xs, 4) == -1   # отсутствует посередине

Если все assert проходят — реализация скорее всего корректная. Если нет — там точно баг.

Баг #5: бинарный поиск по неотсортированному массиву

Это даже не баг алгоритма — это баг применения. Если массив не отсортирован, бинарный поиск даёт произвольный мусор: иногда находит, иногда нет, иногда находит не тот элемент.

import bisect

xs = [5, 3, 7, 1, 9]   # НЕ отсортирован
print(bisect.bisect_left(xs, 7))   # возвращает что-то, но не правильно

Симптомы: «иногда работает, иногда нет», «работает в тестах, в проде падает». Часто данные приходят отсортированными, а потом что-то изменилось — и бинарный поиск стал лгать.

Защита: assertion перед использованием.

def safe_binary_search(xs, target):
    if __debug__:
        assert all(xs[i] <= xs[i+1] for i in range(len(xs)-1)), "xs must be sorted"
    return binary_search(xs, target)

В Python __debug__ равен True по умолчанию и False при запуске с -O. Эта проверка O(n) — но она есть только в дев-режиме.

Сравнение реализаций

Рекомендация: не пишите свой бинарный поиск

Если задача — поиск в отсортированном массиве, используйте bisect. Он написан в C, протестирован миллиардами запусков, и не имеет ни одного из перечисленных багов.

import bisect

def contains(xs, target):
    i = bisect.bisect_left(xs, target)
    return i < len(xs) and xs[i] == target

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

1. Учебный проект (как у нас сейчас).
2. Поиск по предикату, который не сводится к сравнению ключей (например, «первый элемент, у которого suffix_sum < threshold»).
3. Поиск в нестандартной структуре (например, в файле на диске, где нет случайного доступа в RAM).

Во всех остальных случаях — bisect, и никаких изобретений велосипеда.

Попробуй сам

Возьмите свою реализацию из прошлого урока и проверьте на «противных» случаях:

import bisect

def my_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

# сравним с bisect на 10 000 случайных запросов
import random

xs = sorted(random.sample(range(1_000_000), 10_000))
queries = [random.randint(0, 1_000_000) for _ in range(10_000)]

for q in queries:
    my = my_binary_search(xs, q)
    ref = bisect.bisect_left(xs, q)
    ref_idx = ref if ref < len(xs) and xs[ref] == q else -1
    if my != ref_idx:
        print(f"MISMATCH: target={q}, my={my}, ref={ref_idx}")
        break
else:
    print("all 10 000 queries match bisect")

Если хоть одно несовпадение — у вас баг. Запустите на пустых массивах и массивах из одного элемента. Эти крайние случаи ловят 80% багов.