Interpolation Search [EXPLAINED]

In this article, we have explained the concept of Interpolation Search and analyzed the performance of interpolation search in terms of time and space complexity.

What is Interpolation Search?

Interpolation search is basically an improvement over binary search. In interpolation search we check at different postitions based on the value of element being searched using a formula , that is :

pos= start + (((double) (end-start) / (a[end]-a[start])) * (key-a[start]))

where,

pos = position of eleme...