# Interpolation Search

• 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:

  

  4. If A[pos] == e , element found at index pos.

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

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

  7. 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
 cout<<"Not Found.";

 return 0;
}

Time Complexity Favourable case: O(log log n), Worst Case: O(n)