Beating Binary Search: The Interpolation Search

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.

Continue reading