В основе интерполяционного поиска лежит операция интерполирование. Интерполирование – нахождение промежуточных значений величины по имеющемуся дискретному набору известных значений. Интерполяционный поиск работает только с упорядоченными массивами; он похож на бинарный, в том смысле, что на каждом шаге вычисляется некоторая область поиска, которая, по мере выполнения алгоритма, сужается.
Но в отличие от двоичного, интерполяционный поиск не делит последовательность на две равные части, а вычисляет приблизительное расположение ключа (искомого элемента), ориентируясь на расстояние между искомым и текущим значением элемента.
Идея алгоритма напоминает хорошо знакомый старшим поколениям поиск телефонного номера в обычном справочнике: список имен абонентов упорядочен, поэтому не составит труда найти нужный телефонный номер, так как, если мы, например, ищем абонента с фамилией, начинающейся на букву «Ю», то для дальнейшего поиска разумно будет перейти в конец справочника.
Формула, определяющая алгоритм интерполяционного поиска выглядит следующим образом:
Здесь mid – номер элемента, с которым сравнивается значение ключа, key – ключ (искомый элемент), A – массив упорядоченных элементов, left и right – номера крайних элементов области поиска. Важно отметить, операция деления в формуле строго целочисленная, т. е. дробная часть, какая бы она ни была, отбрасывается.
Код программы на C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
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. |
Похожие записи: