Problem
I understand that interpolation search not only requires a sorted list but also uniformly distributed. Provide an understandable situation where Interpolation search is slower than binary search.
If we assume uniform distribution of the values so we’ll use simple linear interpolation. So if the values are:
1,2,3,4,5,6,7,8,9,10000000
And we search for number 9
, searching using linear interpolation will go through all (excluding the first and last) the indices before finding the correct one. In such cases interpolation search will be O(n)
.