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

Находит значение в отсортированном массиве: смотрит в середину и отбрасывает половину, где его быть не может. Каждое сравнение вдвое уменьшает то, что осталось.

лучший Ω(1)
средний Θ(log n)
худший O(log n)
память O(1)

Что это значит?

Отсортировано: по возрастанию. Двоичному поиску это нужно; на неотсортированных данных он ошибается.
Деление пополам: каждое сравнение отбрасывает половину остатка — ту, где цели быть не может.
log₂ n: сколько раз n можно разделить пополам, пока не останется 1. Для 64 значений это 6, то есть не больше 7 сравнений.

середина (mid)
найдено
отброшено
цель

0 / 14 шагов

Каждая середина, которую может выбрать поиск; прогон — один путь вниз. Уровней: 5 = ⌈log₂(24 + 1)⌉ — столько сравнений может понадобиться в худшем случае.

Скорость 8 шагов/с

Пробел: воспроизведение или пауза. Стрелки влево и вправо: шаг. Home и End: в начало или в конец.

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

Как это работает

Двоичный поиск держит две метки, lo и hi, вокруг той части массива, где цель ещё может быть. Он смотрит на значение в середине: если это цель — готово; если оно меньше, цель может быть только справа, и lo переходит за середину; если больше, hi переходит перед ней. Каждый шаг делит остаток пополам: для 64 значений хватает 7 сравнений, для миллиона — 20. Когда lo обгоняет hi, ничего не остаётся: значения в массиве нет.

Когда стоит применять

Двоичный поиск подходит, когда данные отсортированы и можно перейти к любой позиции: слово в отсортированном списке, версия в истории релизов, git bisect, место вставки в отсортированный массив. На неотсортированных данных он ошибается, а сортировать заранее выгодно, только если искать много раз.