Специальные виды поиска

Интерполяционный поиск произошел от естественного поиска данных в упорядоченном массиве человеком. Если известно, что искомый ключ k находится между некоторым "нижним" ключом k_l и некоторым "верхним" ключом k_h,

k_l < k < k_h

то следующее сравнение делается на расстоянии

(l − h)(k − k_l) / (k_h − k_l)

от текущей позиции k_i. Предполагается что данные в массиве возрастают в арифметической прогрессии.

Именно по такому алгоритму выполняется поиск нужной карточки в "бумажном" библиотечном каталоге, или страницы в книге.

Этот алгоритм эффективнее бинарного поиска только в случае арифметической прогрессии, так как на каждом шаге уменьшает интервал анализа не до n/2 а до sqr(n_i) и требует в среднем около log₂(log₂(N)) шагов, если упорядоченные данные имеют равномерное распределение.

Недостаток этого алгоритма – затраты времени на дополнительные операции при внутреннем поиске. Разность между log₂(log₂(N)) и log₂(N) становится весьма существенной при больших N, а типичные наборы данных (которыми для этого поиска часто являются файлы) недостаточно случайны.

Этот алгоритм может быть достаточно успешным при поиске во внешних запоминающих устройствах.

Для поиска подстроки в строке могут использоваться алгоритмы Бойера–Мура (и его несколько модификаций) и Кнута–Морриса–Пратта.