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 http://iq.opengenus.org/interpolation-search-algorithm/