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

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

Формула, определяющая алгоритм интерполяционного поиска выглядит следующим образом:

 

 

Здесь mid – номер элемента, с которым сравнивается значение ключа, key – ключ (искомый элемент), A – массив упорядоченных элементов, left и right – номера крайних элементов области поиска. Важно отметить, операция деления в выражении строго целочисленная, т. е. дробная часть, какая бы она ни была, отбрасывается.

 

Код программы на C++:

 

const int n=17;

int InterpolSearch(int A[], int key) //интерполяционный поиск

{

int mid, left=0, right=n-1;

while (A[left]<=key && A[right]>=key)

{

mid=left+((key-A[left])*(right-left))/(A[right]-A[left]);

if (A[mid]<key) left=mid+1;

else if (A[mid]>key) right=mid-1;

else return mid;

}

if (A[left]==key) return left;

else return -1;

}

 

void main() //главная функция

{

int i, key;

int A[n]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};

cout<<"Искомый элемент > "; cin>>key; //ввод ключа

cout<<"Исходный массив: ";

for (i=0; i<n; i++) cout<<A[i]<<" "; //вывод массива

if (InterpolSearch(A, key)==-1) cout<<"\nЭлемент не найден";

else cout<<"\nНомер элемента: "<<InterpolSearch(A, key)+1;

}

 

Код программы на Pascal:

 

const n=17;

type Arr=array[1..n] of integer;

var mid, left, right, key, i: integer;

const A: Arr=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59);

function InterpolSearch(A: Arr; key: integer): integer; {интерполяционный поиск}

begin

left:=1; right:=n;

while ((A[left]<=key) and (A[right]>=key)) do

begin

mid:=left+((key-A[left])*(right-left)) div (A[right]-A[left]);

if (A[mid]<key) then left:=mid+1

else if (A[mid]>key) then right:=mid-1

else

begin

InterpolSearch:=mid;

exit;

end;

end;

if (A[left]=key) then InterpolSearch:=left

else InterpolSearch:=-1;

end;

 

begin {основной блок программы}

write('Искомый элемент > '); read(key); {ввод ключа}

write('Исходный массив: ');

for i:=1 to n do write(A[i], ' '); {вывод массива}

writeln;

if (InterpolSearch(A, key)=-1) then write('Элемент не найден')

else write('Номер элемента: ', InterpolSearch(A, key));

end.

 

Интерполяционный поиск в эффективности, как правило, превосходит двоичный, в среднем требуя log*log n операций, где n – объем входных данных. Тем самым время его работы составляет O(log*log n). Но если, к примеру, последовательность экспоненциально возрастает, то скорость увеличиться до O(n). Наибольшую производительность алгоритм показывает на последовательности, элементы которой распределены равномерно относительно друг друга.