Lecture
Interpolation search is based on the operation of interpolation. Interpolation is finding intermediate values of a quantity from an available discrete set of known values. Interpolation search only works with ordered arrays; it is similar to binary search in the sense that at each step it computes a certain search region, which narrows as the algorithm proceeds. But unlike binary search, interpolation search does not divide the sequence into two equal parts, but instead estimates the approximate location of the key (the sought element), based on the distance between the sought value and the current element's value. The idea of the algorithm resembles a search well known to older generations — looking up a phone number in an ordinary directory: the list of subscriber names is ordered, so it's not hard to find the needed phone number, since, for example, if we are looking for a subscriber whose name begins with the letter "E", it makes sense to jump to the end of the directory to continue the search.
The formula defining the interpolation search algorithm is as follows:
Here, mid is the index of the element being compared to the key value, key is the key (the sought element), A is the array of ordered elements, and left and right are the indices of the extreme elements of the search region. It's important to note that the division in the formula is strictly integer division, i.e., the fractional part, whatever it may be, is discarded.
|
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 using namespace std; const int N=17; //interpolation search 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]else if (A[mid]>key) right=mid-1; else return mid; } if (A[left]==key) return left; else return -1; } //main function 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<<"Element sought > "; cin>>key; //enter key cout<<"Original array: "; for (i=0; iif (InterpolSearch(A, key)==-1) cout<<"\nElement not found"; else cout<<"\nElement index: "<system("pause>>void"); } |
|
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); {interpolation search} 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]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; {main program block} begin write('Element sought > '); read(key); {enter key} write('Original array: '); for i:=1 to N do write(A[i], ' '); {print array} writeln; if (InterpolSearch(A, key)=-1) then write('Element not found') else write('Element index: ', InterpolSearch(A, key)); end. |
Interpolation search generally outperforms binary search in efficiency, on average requiring log(log(N)) operations. Its running time is therefore O(log(log(N))). But if, for example, the sequence grows exponentially, the speed drops to O(N), where N (as in the previous case) is the total number of elements in the list. The algorithm performs best on a sequence whose elements are evenly distributed relative to one another.
Comments