Экспоненциальный поиск

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

Отсортированный ряд столбиков с прыжками удваивающейся длины через места 1, 2, 4 и 8 и затенённым отрезком между двумя последними прыжками
Отсортированный ряд столбиков с прыжками удваивающейся длины через места 1, 2, 4 и 8 и затенённым отрезком между двумя последними прыжками

Идея

Проверьте значение на месте 1, затем 2, 4, 8, 16 и так далее, каждое место вдвое дальше предыдущего. Пока значение там меньше искомого, искомое должно быть дальше. Как только значение впервые окажется не меньше, искомое поймано: оно лежит после предыдущего проверенного места и не дальше этого. Этот отрезок отсортирован, поэтому двоичный поиск находит искомое или показывает, что его нет.

Пример

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

Сколько сравнений

Для искомого на месте i удвоение останавливается примерно через log₂ i шагов и оставляет отрезок короче i мест, который двоичный поиск проходит ещё примерно за log₂ i. Итого поиск стоит около 2 log₂ i сравнений при любой длине списка. Когда искомое у начала, это лучше двоичного поиска, который всегда платит около log₂ n. Когда оно у конца, экспоненциальный поиск платит больше, примерно до двух раз. Для 40 значений приложение в среднем делает около 3 сравнений для первых пяти мест и около 9 для последних пяти, против примерно 4,6 у двоичного поиска.

Неизвестная длина и галоп

Jon Bentley и Andrew Yao описали эту стратегию удвоения в 1976 году для неограниченного поиска: поиска значения в отсортированной последовательности без известного конца, например в бесконечном списке или в потоке, к которому можно только обращаться по месту. Та же идея ускоряет слияние. Когда одна из двух отсортированных серий раз за разом выигрывает, Timsort переходит в режим галопа: он заглядывает на 1, 2, 4, 8 мест вперёд в другой серии, чтобы найти, куда встаёт следующее значение, вместо того чтобы идти по одному месту.

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

Откройте приложение, выберите значение в поле «Искать» и нажмите «Шаг». Каждая проверка места 1, 2, 4, 8 и так далее подсвечивается; как только значение окажется не меньше, отрезок между двумя последними местами затеняется, и дальше работает двоичный поиск. Поищите маленькое значение, а затем большое, и сравните счётчик с плиткой двоичного поиска.

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

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

O(log i) для искомого на месте i, то есть не больше O(log n) для списка из n значений. Нужны O(1) дополнительной памяти и отсортированный список.

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

Двоичный поиск начинает со всего списка, и ему нужна его длина. Экспоненциальный поиск сначала удвоением находит отрезок, содержащий искомое, а затем ищет двоичным поиском только на этом отрезке. Он быстрее, когда искомое у начала, и работает без знания длины.

Почему шаг удваивают, а не прибавляют постоянную величину?

Постоянный шаг — это поиск прыжками (jump search): чтобы пройти список, ему нужно около n, делённого на шаг, проверок. Удвоение доходит до места i примерно за log₂ i проверок, а оставшийся отрезок никогда не больше чем вдвое шире нужного, так что двоичный поиск после него остаётся коротким.

Где применяется экспоненциальный поиск?

При поиске в неограниченных или очень длинных отсортированных данных, при слиянии отсортированных серий (галоп в Timsort) и при поиске первого места, где условие становится истинным, когда верхняя граница неизвестна.

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

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

Попробовать экспоненциальный поиск