3. Алгоритм интерполирующего поиска

Интерполирующий поиск основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым как при линейном поиске, производится предсказание местонахождения элемента. Процедура похожа на двоичную, но вместо деления области поиска на две части, производится оценка новой области по расстоянию между ключом и текущим значением аргумента. Другими словами, бинарный поиск учитывает лишь знак разности между ключом и текущим значением, а интерполирующий - ещё и модуль этой разности и по этому значению производит предсказание позиции следующего элемента для проверки.

В среднем, интерполирующий поиск производит log(log(n)) операций, где n - число элементов в массиве. Количество необходимых операций зависит от равномерности распределения значений среди элементов. В плохом случае (например, когда значения элементов экспоненциально возрастают) интерполяционный поиск может потребовать до O(n) операций.

На практике, интерполяционный поиск часто быстрее бинарного, так как их отличают, прежде всего, применяемые арифметические операции:

1. интерполирование — в интерполирующем поиске и

2. деление на два — в двоичном.

При этом скорость вычисления отличается незначительно. С другой стороны интерполирующий поиск использует такое принципиальное свойство данных, как однородность распределения значений. Ключом может быть не только номер, число, но и, например, текстовая строка, тогда становится понятна аналогия с телефонной книгой: если мы ищем имя в телефонной книге, начинающееся на «А», то нужно искать его в начале, но никак не в середине. В принципе, ключом может быть всё что угодно, так как те же строки, например, кодируются посимвольно, в простейшем случае символ можно закодировать значением от 1 до 33 (только русские символы) или, например, от 1 до 26 (только латинский алфавит) и т. д.

Интерполяция может производиться на основе функции, аппроксимирующей распределение значений, либо набора кривых, выполняющих аппроксимацию на отдельных участках. В этом случае поиск может завершиться за несколько проверок. Преимущества метода состоят в уменьшении запросов на чтение медленной памяти (такой, например, как жесткий диск), если запросы происходят часто.

Часто анализ и построение аппроксимирующих кривых не требуется, например, когда все элементы отсортированы по возрастанию. В таком списке минимальное значение будет по индексу 0, а максимальное по индексу n - 1. В этом случае аппроксимирующую кривую можно принять за прямую и применять линейную интерполяцию.

Общий алгоритм интерполирующего поиска без задания исходного массива может быть таким. На каждой стадии рассчитывается позиция mid (средняя) для следующей проверки, по формуле:

mid = low + (аргумент - ключ [low])*(high - low) /

(ключ [high] - ключ[low])

где low – нижняя граница диапазона,

high – его верхняя граница.

Затем в зависимости от результата сравнения переносится верхняя или нижняя граница, определяя новую область поиска. Процесс заканчивается, если элемент с индексом mid равен искомому ключу или нижняя и верхняя границы поиска совпали.

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

1. Выполнять

1.1. Ввести аргумент поиска (целое число);

1.2. Если аргумент поиска больше или равен нулю,

1.2.1. Искомый номер (num) = - 1.

1.2.1. Нижняя_граница (low) = 0;

1.2.2. Верхняя_граница (high) = n - 1;

1.2.3. Пока (ключ[low] < аргумент И ключ [high] > аргумент)

1. Средний(mid) = low + (аргумент - ключ [low])*(high - low) / (ключ [high] - ключ[low]);

2. Если ключ [mid]< аргумента,

low = mid + 1;

Иначе

Если ключ [mid]< аргумента,

high = mid - 1;

Иначе

mid – искомый номер.

4. Если ключ[low] = аргумент,

low – искомый номер num

Иначе

Если ключ[high] = аргумент,

high – искомый номер num

Иначе

Номер num не найден

В заключение можно отметить, что рассмотренные алгоритмы могут применяться не только к числам, но и к строкам. Примером являются задачи поиска слова в словаре, справочнике, таблице и т.д. Применение дихотомического поиска требует упорядочения слов по алфавиту.