Although pros and cons go hand in hand, with some restrictions in datasets to be searched Interpolation search gives better performance than traditional Binary Search.

Undoubtedly binary search is a great algorithm for searching with average running time complexity of log(n). Binary search always looks for the middle of the dataset and chooses the first or the second half depending on the value of middle and the key being looked for.

The interpolation search differs from Binary in the fact that it resembles how humans search for any key in an ordered set like a word in dictionary. Suppose a person wants to find word “Algorithm” in dictionary, he already knows that he has to look in the beginning of the dictionary. The same way this algorithm keeps narrowing the search space where the searched key might be. A constant is found using the formula

C = (x – min)/(max – min), where
x is the key being looked for
max is the maximum value in the dataset
min is the minimum value in the dataset

This constant C is used to narrow down the search space.
For binary search, this constant C is (min + max)/2.

The average case running time of Interpolation search is log(log n). For this algorithm to give
best results, the dataset should be ordered and uniformly distributed.

////////////// Interpolation Search /////////

int interpolationSearch(int items[], int searchItem)
{
int low = 0;
int high = sizeof(items) – 1;
int mid;

while (items[low] = searchItem) {
mid = low +
(((searchItem – items[low]) * (high – low)) /
(items[high] – items[low]));

if (items[mid] searchItem)
high = mid – 1;
else
return mid;
}

if (items[low] == searchItem)
return low;
else
return -1;
}

void main()
{
// sorted array
int List[20] = {1,2,3,4,5,6,7,8,9,10};
int item = 0;
// returns the index of searched item or -1
item = interpolationSearch(List, 2);
if(item >= 0)
{
printf(“Searched item is: %d”, List[item]);
}
else
{
printf(“Item not found”);
}
getch();
}

References:
https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Interpolation_search.html
http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf
http://programmers.stackexchange.com/questions/119703/interpolation-search-vs-binary-search
http://www.stoimen.com/blog/2012/01/02/computer-algorithms-interpolation-search/