Бинарный поиск: почему его 9 из 10 пишут с багом

Угадать число от 1 до 100 за 7 попыток умеет каждый, а написать это без бага — почти никто.

«Я всегда думал, что бинарный поиск тривиален, пока не попробовал доказать его корректность» — этим грешили очень многие.

Идея, которую понимает ребёнок

Вы загадали число от 1 до 100. Я называю 50 — вы говорите «больше». Я называю 75 — «меньше». Каждый вопрос вдвое сокращает оставшийся диапазон, поэтому за $\lceil \log_2 100 \rceil = 7$ вопросов я гарантированно угадаю. На массиве из миллиона элементов линейный перебор делает до миллиона сравнений, а бинарный поиск — около двадцати. Это разница между «мгновенно» и «свариться».

Условие у алгоритма одно и жёсткое: данные должны быть отсортированы. Без порядка «больше/меньше» теряет смысл, и весь фокус рассыпается.

Где прячется баг

Классический способ найти середину отрезка [lo, hi] выглядит так:

$$mid = \frac{lo + hi}{2}$$

Математически безупречно. Но в языке с фиксированной разрядностью int сумма lo + hi может переполниться: если оба индекса близки к максимуму, их сумма вылезает за границу типа и превращается в отрицательное число. Именно эта ошибка девять лет жила в реализации Arrays.binarySearch в Java и была публично признана инженером Google Джошуа Блохом в 2006 году. Лечится переписыванием так, чтобы суммы не было:

$$mid = lo + \frac{hi - lo}{2}$$

Вторая ловушка: границы и зацикливание

Даже без переполнения легко получить бесконечный цикл или промах на один элемент. Беда в том, что вариантов «правильно» несколько — с полузакрытым интервалом, с закрытым, — и смешивать их нельзя. Вот аккуратная версия с полуинтервалом [lo, hi), где инвариант держится строго:

def binary_search(arr, target):
    lo, hi = 0, len(arr)          # полуинтервал [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2 # без переполнения
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1          # цель строго правее
        else:
            hi = mid              # цель строго левее (mid уже отброшен)
    return -1

data = [1, 3, 4, 7, 9, 11, 15, 20, 24, 30]
for x in (7, 24, 8):
    print(f"{x}: индекс {binary_search(data, x)}")

Почему так трудно

Алгоритм держится на инварианте цикла: «если цель есть в массиве, она лежит внутри [lo, hi)». Каждая ветка обязана этот инвариант сохранить. Стоит написать hi = mid - 1 вместо hi = mid для полуинтервала — и вы случайно выбросите кандидата, которого ещё не проверили. Граница «строго меньше» или «меньше либо равно» в условии while зависит от того, открыт правый конец или закрыт. Эти решения связаны, и непродуманное сочетание даёт либо промах, либо зацикливание.

Не только «найти число»

Настоящая сила бинарного поиска — в обобщении на любую монотонную функцию-предикат. Ищете минимальную скорость, при которой грузчик успеет разнести посылки за смену? Минимальную мощность станка, проходящего тест? Если ответ «да/нет» монотонен по параметру (всё, что больше порога — «да», всё, что меньше — «нет»), вы можете бинарным поиском найти этот порог, не имея отсортированного массива вообще. Так задачи оптимизации сводятся к задаче поиска границы.

Мораль

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