Интерполирующий поиск основан на принципе поиска в телефонной книге или, например, в словаре.
Вместо сравнения каждого элемента с искомым как при линейном
поиске, данный алгоритм производит предсказание
местонахождения элемента: поиск происходит подобно двоичному
поиску, но вместо деления области поиска на две части,
интерполирующий поиск производит оценку новой области поиска по расстоянию
между ключом и текущим значением элемента. Другими словами, бинарный поиск
учитывает лишь знак разности между ключом и текущим значением, а
интерполирующий ещё учитывает и модуль этой разности и по данному значению
производит предсказание позиции следующего элемента для проверки. В среднем,
интерполирующий поиск производит log(log(N)) операций, где N есть число элементов, среди которых
производится поиск. Число необходимых операций зависит от равномерности
распределения значений среди элементов. В плохом случае (например, когда
значения элементов экспоненциально возрастают) интерполяционный поиск может
потребовать до O(N) операций.
Анализ
сложности – Королев-Миков страницы 122!!!
