Специальные виды поиска
Интерполяционный поиск произошел от естественного поиска данных в упорядоченном массиве человеком. Если известно, что искомый ключ k находится между некоторым "нижним" ключом kl и некоторым "верхним" ключом kh, kl < k < kh то следующее сравнение делается на расстоянии (l − h)(k − kl) / (kh − kl) от текущей позиции ki. Предполагается что данные в массиве возрастают в арифметической прогрессии. Именно по такому алгоритму выполняется поиск нужной карточки в "бумажном" библиотечном каталоге, или страницы в книге. Этот алгоритм эффективнее бинарного поиска только в случае арифметической прогрессии, так как на каждом шаге уменьшает интервал анализа не до n/2 а до sqr(ni) и требует в среднем около log2(log2(N)) шагов, если упорядоченные данные имеют равномерное распределение. Недостаток этого алгоритма – затраты времени на дополнительные операции при внутреннем поиске. Разность между log2(log2(N)) и log2(N) становится весьма существенной при больших N, а типичные наборы данных (которыми для этого поиска часто являются файлы) недостаточно случайны. Этот алгоритм может быть достаточно успешным при поиске во внешних запоминающих устройствах. Для поиска подстроки в строке могут использоваться алгоритмы Бойера–Мура (и его несколько модификаций) и Кнута–Морриса–Пратта.
|
