В основе интерполяционного поиска лежит операция интерполирование. Интерполирование – нахождение промежуточных значений величины по имеющемуся дискретному набору известных значений. Интерполяционный поиск работает только с упорядоченными массивами; он похож на бинарный, в том смысле, что на каждом шаге вычисляется некоторая область поиска, которая, по мере выполнения алгоритма, сужается.
Но в отличие от двоичного, интерполяционный поиск не делит последовательность на две равные части, а вычисляет приблизительное расположение ключа (искомого элемента), ориентируясь на расстояние между искомым и текущим значением элемента.
Идея алгоритма напоминает хорошо знакомый старшим поколениям поиск телефонного номера в обычном справочнике: список имен абонентов упорядочен, поэтому не составит труда найти нужный телефонный номер, так как, если мы, например, ищем абонента с фамилией, начинающейся на букву «Ю», то для дальнейшего поиска разумно будет перейти в конец справочника.
Формула, определяющая алгоритм интерполяционного поиска выглядит следующим образом:
Здесь mid – номер элемента, с которым сравнивается значение ключа, key – ключ (искомый элемент), A – массив упорядоченных элементов, left и right – номера крайних элементов области поиска. Важно отметить, операция деления в формуле строго целочисленная, т. е. дробная часть, какая бы она ни была, отбрасывается.
Код программы на C++:
#include "stdafx.h"
#include <iostream>
using namespace std;
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()
{
setlocale(LC_ALL,"Rus");
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;
system("pause>>void");
}
Код программы на Pascal:
program InterpolationSearch;
uses crt;
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)) операций. Тем самым время его работы составляет O(log(log(N))). Но если, к примеру, последовательность экспоненциально возрастает, то скорость увеличиться до O(N), где N (как и в предыдущем случае) – общее количество элементов в списке. Наибольшую производительность алгоритм показывает на последовательности, элементы которой распределены равномерно относительно друг друга.