Interpolation search

Given a sorted array of integers and a target, find out if a target exists in the array or not. If target exists in the array, print index of it.


For example,
 
Input:

arr[] = [2, 3, 5, 7, 9]
target = 7

Output: Element found at index 3

 
Input:

arr[] = [1, 4, 5, 8, 9]
target = 2

Output: Element not found
 


Interpolation search is an algorithm similar to binary search for searching for a given target value in an sorted array. It parallels how humans search through a telephone book for a particular name, the target value by which the book’s entries are ordered.
 

We know that binary search always chooses the middle of the remaining search space, discarding one half or the other depending on the comparison result between the mid value & the target value and the remaining search space is reduced to the part before or after the mid position.

By comparison Interpolation search, at each search step, calculates where in the remaining search space the target might be present, based on the low and high values of the search space and the value of the target. The value actually found at this estimated position is then compared to the target value. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between target values are sensible.

Interpolation search use below formula to calculate the mid position –

    mid = low + ((x – A[low]) * (high – low) / (A[high] – A[low]));

Here, A[low..high] is our search space and x is the given target.
 

Below is the C++ implementation of interpolation search. At each iteration, it computes a mid position and then as with the binary search, moves either the upper or lower bound in to define a smaller interval containing the target value. Unlike the binary search which guarantees half search space size with each iteration, a poor interpolation may reduce/increase the mid index by only one, thus resulting in a worst-case efficiency of O(n).

 
C++ implementation –
 

Download   Run Code

Output:

Element found at index 1

 

Performance

Each iteration of the above code requires between five and six comparisons. On average the interpolation search makes about log(log(n)) comparisons if the elements are uniformly distributed, where n is the number of elements to be searched. In the worst case it can make up to O(n) comparisons. Worst case might happen when the numerical values of the targets increase exponentially.

Note – This article doesn’t not provide in-depth analysis of how interpolation search works but aims at providing just an overview of achieving better performance than binary search algorithm for a sorted array.
 

References:
https://en.wikipedia.org/wiki/Interpolation_search

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂