Interpolation Search Algorithm

Interpolation Search Algorithm is a potential fast search algorithm to search within a uniformly distributed and sorted search space.

It has been inspired by the way humans search through a telephone book for a particular name, the key value by which the book's entries are ordered. It is an improvement above binary search. In binary search, we always move to the middle element whereas interpolation search moves to a different element in order to reduce the search space further.

The average case time complexity is O(log log N) and the auxiliary space complexity is O(1).

Refer the article for more details and implementations.

Share your thoughts or ask any questions below.
This is a companion discussion topic for the original entry at