Interpolation search is an algorithm for finding a given key in a sorted array. While binary search always chooses the middle element for comparison, discarding one half of the search space or the other, 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. This method will only work if calculations on difference between key values are sensible.
The estimated position of the key is calculated as follows:
Let the current search space be A[i…j] and we are looking for x, then by a linear interpolation of values, x should be found at position:
p = i + ((j - i) * (x - A[i])) / (A[j] - A[i])
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, 109.
Take a look at C++ implementation.