What is an example of Interpolation Search being slower than Binary Search?

Technology CommunityCategory: SearchingWhat is an example of Interpolation Search being slower than Binary Search?
VietMX Staff asked 3 years ago
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).