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

Двоичный поиск — это то, как вы ищете слово в словаре: открываете его посередине, смотрите, раньше или позже идёт слово, и повторяете с этой половиной. В отсортированном списке он находит любое значение среди миллиона не более чем за 20 сравнений.

Отсортированный ряд столбиков с выделенным средним столбиком, побледневшей половиной ряда и пунктирной линией на высоте искомого значения
Отсортированный ряд столбиков с выделенным средним столбиком, побледневшей половиной ряда и пунктирной линией на высоте искомого значения

Идея

В отсортированном списке одно сравнение говорит больше, чем то, нашли ли вы искомое значение: оно говорит, с какой оно стороны. Сравните искомое значение со значением в середине. Если они равны, поиск закончен. Если среднее значение меньше, всё перед ним тоже меньше, поэтому искомое может быть только после него. Если больше, искомое может быть только перед ним. Оставьте только эту половину и повторите.

Пример

Ищем 23 в списке 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Среднее значение — 16, оно меньше, поэтому остаются только значения от 23 до 91. Их середина — 56, это больше, поэтому остаются только 23 и 38. Их середина — 23: найдено на месте 6 за 3 сравнения, тогда как линейному поиску нужно 6. Поиск 40 в том же списке сравнивает 16, 56, 23 и 38, после чего ничего не остаётся: 4 сравнения, чтобы узнать, что 40 нет, против 10 у линейного поиска.

Деление пополам работает быстро

После одного сравнения остаётся не больше половины списка, после двух — четверть, после k — не больше примерно n/2ᵏ. Поиск останавливается, когда ничего не осталось, поэтому ему нужно не больше ⌊log₂ n⌋ + 1 сравнений: 6 для 40 значений, 10 для 1000, 20 для миллиона и 30 для миллиарда. Удвоение списка добавляет всего одно сравнение. Это записывают как O(log n).

Легко описать, трудно написать правильно

John Mauchly описал двоичный поиск в 1946 году, но, по словам Donald Knuth, первая версия, работавшая для списка любой длины, была опубликована только в 1962 году. Позже Jon Bentley выяснил, что лишь примерно один из десяти профессиональных программистов писал его правильно: условия окончания и плюс или минус один при делении на половины легко перепутать. В 2006 году Joshua Bloch показал, что обычный способ найти середину, (low + high) / 2, может вызвать переполнение (overflow) на очень длинных списках, и эта ошибка годами сидела в библиотеке Java. Запись low + (high − low) / 2, как в приложении, этого избегает.

Джон Мокли (пятый слева) с другими руководителями проекта ENIAC перед машиной, фотография армии США. Мокли описал двоичный поиск в 1946 году.
Джон Мокли (пятый слева) с другими руководителями проекта ENIAC перед машиной, фотография армии США. Мокли описал двоичный поиск в 1946 году.

Варианты и применения

При повторах двоичный поиск находит одно из совпадений; версии, которые продолжают влево или вправо, находят первое или последнее либо место, куда нужно вставить отсутствующее значение. Та же идея деления пополам находит корень уравнения (метод бисекции), версию, в которой впервые появилась ошибка (git bisect), и ответ во многих задачах на оптимизацию. Двоичные деревья поиска хранят данные так, чтобы каждый поиск шёл по тому же пути делений пополам.

Попробуйте сами

Откройте приложение, выберите значение в поле «Искать» и нажмите «Шаг». Затенённая часть — это где искомое значение ещё может быть; среднее значение выделено, а отсечённая половина бледнеет. Плитки показывают, сколько значений ещё возможно и сколько сравнений понадобилось бы линейному поиску для того же значения. Поищите отсутствующее значение или возьмите 40 столбиков, чтобы увидеть, как растёт разница.

Часто задаваемые вопросы

Какова временная сложность двоичного поиска?

O(log n): не больше ⌊log₂ n⌋ + 1 сравнений для n значений. В лучшем случае хватает одного сравнения, когда искомое значение в середине. Итеративной версии нужно O(1) дополнительной памяти.

Чем двоичный поиск отличается от линейного?

Линейный поиск проверяет значения по очереди и работает с любым списком, но ему может понадобиться n сравнений. Двоичный поиск работает только с отсортированным списком, но каждое сравнение отсекает половину оставшегося, поэтому ему нужно около log₂ n.

Стоит ли сортировать список только ради двоичного поиска?

Только если искать в нём много раз. Сортировка занимает около n log n шагов, больше, чем один линейный поиск. Зато после сортировки каждый следующий поиск обходится очень дёшево.

Работает ли двоичный поиск не только со списками?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать двоичный поиск