Interpolation Search

Interpolation search, also called as extrapolation search. Interpolation searching algorithm is only used when the elements in an array is sorted and evenly distributed. Interpolation search algorithm is the combination of both binary search algorithm and linear search algorithm. The working of interpolation search algorithm is very much similar to our brain on look for the name Manish in the telephone directory, we know that it will be near the extreme left, So if we tend to apply binary search algorithm to dividing the list in two halves each time will lead to worst case. Thus we need to divide the telephone directory into two half for the first time (binary search algorithm) and start search from the first occurance of letter M using linear search algorithm.

Advantages - Interpolation Search

• When all elements in the list are sorted and evenly distributed, then executing time of Interpolation search algorithm is log(log n) i.e) Best case.

Disadvantages - Interpolation Search

• However, When the elements in the list are increased exponentially, then executing time of Interpolation search algorithm is 0(n) i.e) Worst case.

C program - Interpolation Search

Here is the program to demonstrate Interpolation Search.

#include <stdio.h>
#define MAX 30
int interpolation_search(int a[], int low, int high, int val)
{
int mid;
while(low <= high)
{
mid=low + (high-low) * ((val - a[low]) / (a[high] - a[low]));
if(val == a[mid])
return mid;
if(val < a[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main()
{
int arry[MAX], i, n, val, pos;
printf("\n Enter the size of the array : ");
scanf("%d", &n);
printf("\n Enter %d elements in the array : \n",n);
for(i = 0; i<n; i++)
scanf("%d", &arry[i]);
printf("\n Enter the key element that has to be search : ");
scanf("%d", &val);
pos = interpolation_search(arry, 0, n-1, val);
if(pos == -1)
printf("\n %d is not found in the array", val);
else
printf("\n %d is found in the array at position arry [%d]", val, pos);
return 0;
}

Enter the size of the array : 5 
Enter 5 elements in the array :
1 2 3 4 5 
Enter the key element that has to be search : 3
3 is found in the array at position arry [2]

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report

Error Line Corrected Line Send