• Interpolation search is an improvement over binary search.

• Binary Search always checks the value at middle index. But, interpolation search may check at different locations based on the value of element being searched.

• For interpolation search to work efficiently the array elements/data should be sorted and uniformly distributed.

• Steps:

1. `A` - Array of elements, `e` - element to be searched, `pos` - current position
2. Make `start = 0` & `end = n-1`
3. calculate position ( pos ) to start searching at using formula:
1. If `A[pos] == e` , element found at index `pos`.

2. Otherwise if `e > A[pos]` we make `start = pos + 1`

3. Else if `e < A[pos]` we make `end = pos -1`

4. Do stpes 3, 4, 5, 6 `While : start <= end` && `e >= A[start]` && `e =< A[end]`

• `start <= end` - that is untill we have elements in the sub-array.
• `e >= A[start]` - element we are looking for is greater than or equal to the starting element of sub-array we are looking in.
• `e =< A[end]` - element we are looking for is less than or equal to the last element of sub-array we are looking in.
• Example if we are looking for element 4 in the given array.

### # Source Code - C++

``````#include <iostream>
using namespace std;

//Function to perform interpolation Search
int interpolationSearch ( int A[] , int n, int e)
{
int start, end , pos;
start= 0;
end = n-1;

while( start<=end && e>=A[start] && e<=A[end])
{

pos = start + (((double)(end-start)/(A[end]-A[start]))*(e-A[start]));

if (A[pos] == e)
return pos;
if (e > A[pos])
start = pos + 1;
else
end = pos-1;
}
return -1;

}
int main()
{
int n,i,e;
cout<<"enter number of elements\n";
cin>>n;
int A[n];
cout<<"enter elements\n";
for(i=0;i<n;i++)
cin>>A[i];
cout<<"Enter element to be searched\n";
cin>>e;

//interpolation search function call
int index = interpolationSearch(A, n, e);
if(index != -1)
cout<<"found at index:"<<index;
else