Двоичный поиск

Вчера всё работало, сегодня сломано, а между этими версиями сотни коммитов. Проверять каждый — долго: собрать, запустить, посмотреть. Но проверять каждый и не нужно. Возьмём середину: если там уже сломано, виноват кто-то в первой половине, если ещё нет — во второй. Каждая проверка отрезает половину подозреваемых. Ниже настоящая история этого сайта, 904 коммита с февраля по октябрь 2026 года. Выберите вопрос — например, когда появился учебник математики, — и посмотрите, сколько проверок понадобится.

Десять проверок на 904 коммита. Перебор от первого коммита до учебника математики сделал бы 484. На миллионе коммитов двоичному поиску хватило бы двадцати. Это команда git bisect: она так и работает, только проверку делаете вы — собираете версию, которую она выбрала, и говорите «good» или «bad».

Идея

Если ответ на вопрос «уже да?» вдоль ряда меняется ровно один раз — сначала идут «нет», потом только «да», — то границу можно найти, каждый раз спрашивая о середине оставшегося куска. Один ответ делит кусок пополам, и через log₂ n вопросов от него остаётся одна точка.

Обратите внимание: здесь ничего не сказано про числа и сортировку. Нужно только, чтобы вопрос был монотонным: если в коммите №483 учебник уже есть, то он есть и во всех следующих. Отсортированный массив — частный случай: вопрос «элемент ≥ x?» для него монотонен. А ещё монотонны «хватит ли k грузовиков?», «уложится ли программа в секунду при n элементах?», «сломан ли сайт в этой версии?» — и двоичный поиск работает для всех них. Последний случай подробно разобран в статье о двоичном поиске по ответу.

Нижняя и верхняя граница

Чаще всего двоичный поиск ищет не «есть ли x в массиве», а границу: первое место, где элемент не меньше x. Эту позицию называют нижней границей (lower bound). Первое место, где элемент строго больше x, — верхняя граница. Между ними лежат все элементы, равные x, а справа от нижней границы — все элементы, не меньшие x.

Вот все землетрясения силой от 5 баллов за 2015–2025 годы по каталогу USGS — 19 073 штуки, отсортированные по магнитуде. Сколько из них сильнее 7? Подвигайте порог и посмотрите, как lo и hi сходятся к ответу.

Подсвеченная полоса — это всё, о чём мы пока ничего не знаем. Код держит одно утверждение, инвариант: все элементы левее lo меньше порога, все элементы начиная с hi — не меньше. В начале lo = 0 и hi = n, и утверждение верно, потому что слева и справа пусто. Каждый шаг смотрит на середину и сдвигает одну из границ так, что утверждение остаётся верным. Когда lo и hi встретились, неизвестного не осталось, и lo — ответ.

Почему цикл правильный и конечный

Возьмём середину mid = ⌊(lo + hi)/2⌋. Пока lo < hi, она лежит в полуинтервале [lo, hi): mid ≥ lo и mid < hi.

• Если a[mid] < x, то и все элементы левее mid меньше x — массив отсортирован. Сдвигаем lo = mid + 1: инвариант «левее lo всё меньше» по-прежнему верен.
• Иначе a[mid] ≥ x, и все правее тоже. Сдвигаем hi = mid: «начиная с hi всё не меньше» по-прежнему верно.

В обоих случаях длина hi − lo строго уменьшается: в первом lo вырос как минимум на единицу, во втором hi стал меньше прежнего. Значит, цикл закончится, причём каждый раз длина уменьшается почти вдвое, поэтому шагов не больше ⌈log₂(n + 1)⌉.

Именно здесь прячутся почти все ошибки: напишите lo = mid вместо lo = mid + 1, и при hi = lo + 1 середина будет равна lo, длина перестанет уменьшаться, и цикл не кончится никогда.

Код

Обе границы на полуинтервале [lo, hi). Это самая надёжная запись: ответ n («такого элемента нет») получается сам собой, без особых случаев.

В стандартных библиотеках это уже есть. В Python — модуль bisect: bisect_left(a, x) — нижняя граница, bisect_right(a, x) — верхняя. В Go — sort.Search(n, f): он находит первый индекс, на котором функция f стала истинной, то есть работает с любым монотонным вопросом, а не только с массивом. Для срезов есть ещё slices.BinarySearch.

А это git bisect по истории сайта. Проверка коммита здесь — заготовленный ответ, а не сборка, но поиск тот же самый:

Ошибки, которые делают все

Джон Бентли в книге «Жемчужины программирования» рассказывал, как давал задачу написать двоичный поиск профессиональным программистам на курсах в Bell Labs и IBM. Времени было достаточно, а правильный код в итоге оказался примерно у каждого десятого. Ошибки повторяются из года в год:

• Бесконечный цикл. lo = mid при mid, округлённом вниз: на отрезке из двух элементов поиск стоит на месте.
• Смесь соглашений. Полуинтервал [lo, hi) в одном месте и отрезок [lo, hi] в другом: тогда то цикл пропускает последний элемент, то читает за концом массива. Выберите одно соглашение и держитесь его.
• Переполнение. В Java и C (lo + hi) / 2 переполняется, когда lo + hi больше 2³¹ − 1. Такая ошибка девять лет жила в Arrays.binarySearch из стандартной библиотеки Java, пока в 2006 году о ней не написал Джошуа Блох. Надёжная запись — lo + (hi - lo) / 2. В Python целые не переполняются, в Go int 64-битный, но привычка полезная.
• Неотсортированные данные. Двоичный поиск по неотсортированному массиву ничего не находит и ничего не сообщает об ошибке — просто возвращает чепуху. Если массив меняется, сортировать его заново или держать в дереве поиска.

Сколько это стоит

Каждая проверка — это ответ «да» или «нет», ровно один бит информации. Чтобы различить n + 1 возможный ответ, нужно не меньше log₂(n + 1) бит, поэтому двоичный поиск оптимален среди всех способов, которые узнают о данных только сравнениями. Памяти — пара переменных.

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

История

Идею двоичного поиска по отсортированной таблице упомянул Джон Мокли в лекциях школы Мура в 1946 году — одном из первых курсов программирования в истории. Но, как заметил Дональд Кнут в «Искусстве программирования», вариант, правильно работающий для таблицы любой длины, появился в печати на годы позже. Короткий алгоритм, который все понимают с первого взгляда, оказался одним из самых трудных для безошибочной записи.

Задачи

Первая — нижняя и верхняя граница на тех же землетрясениях. Во второй двоичный поиск идёт не по массиву, а по числам, и здесь легко попасть в ловушку плавающей точки.