Интерполяционный поиск

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

Здесь r и l — соответственно правая и левая граница области поиска, k — искомый элемент, a_l и a_r - соответственно левый и правый элемент области поиска.

Рассмотрим пример. Пусть дан массив, упорядоченный по возрастанию.

Пусть требуется найти число k=22. Это число больше крайнего левого и меньше крайнего правого элементов. Следовательно, существует возможность найти его в массиве.

В данном примере l=1, r=9 (областью поиска является весь массив от первого до 9-го элемента включительно, a_l=2, a_r=36

Подставим данные в формулу для вычисления номера элемента.

P=(9 — 1) * (22 — 2) / (36 — 2);

P=8*20/34;

P=4, 7; (для определенности округлим в б о льшую сторону, P=5.

Рассмотрим элемент с номером l+P=6. Этот элемент равен 16 и он меньше искомого числа. Следовательно, поиск необходимо продолжить в правой части массива (теперь l будет равно 6,. a_l=16).

Вычислим шаг по формуле

P=(9 — 6)*(22 — 16) / (36 — 16);

P=3*6/20;

P=0, 9 (округлим P в большую сторону, P=1).

Рассмотрим элемент номер 7. Он равен искомому числу, поиск окончен.

Некоторые сложности могут возникнуть при реализации этого метода, например, в случае когда исходный массив выглядит так:

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

Из-за тонкостей реализации и меньшей очевидности при объяснении, интерполяционный поиск лучше дать просто как некое упражнение на технику программирования, нежели как основной алгоритм, который надо в обязательном порядке уметь писать на олимпиадах.

Для олимпиадного программирования более чем достаточно бинарного поиска, но зато доведенного до идеального написания.