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/