Interpolation search is an algorithm to search given key in a uniformly distributed sorted array. It is an improvement over Binary Search when the keys are uniformly distributed in a sorted array.
Binary search always chooses the middle element for comparison, discarding one half of the search space or the other. However, Interpolation search tries to predict where the key would lie in the search space via a linear interpolation, reducing the search space to the part before or after the estimated position if the key is not found there.
A linear interpolation of values, 'key' should be found at position:
It works same as Binary search except above interpolation logic.
1. Calculate the value of "pos" using the linear interpolation formula.
2. if it is a match, return the position of the item, and exit.
3. if the key < array[pos]
3.a. Calculate the linear interpolation of the left sub-array.
3.b. Calculate the linear interpolation in the right sub-array.
4. Repeat until a match is found or the sub-array reduces to zero.
This approach works faster than Binary search when the keys are uniformly distributed. Average case complexity of interpolation search is O(log log N) if the keys are uniformly distributed, where N is the number of keys.
However, the worst case complexity is O(N) e.g., searching for 1000 in 1, 2, 3, …, 999, 1000, 10^9.