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

There are a few cases where Interpolation Search can be slower than Binary Search:

1. When the data is not uniformly distributed, Interpolation Search can degenerate to a linear search and have a worst-case time complexity of O(n), which is slower than Binary Search's O(log n)[1][2][3]. For example, if the values in the array increase exponentially, Interpolation Search may need to make up to O(n) comparisons[2].

2. If the target value is not found in the array, Interpolation Search may need to check every element before determining the value is not present[3]. In this case, it will be slower than Binary Search which can exit the search earlier.

3. For small arrays, the overhead of the more complex calculations in Interpolation Search may outweigh the reduced number of probes compared to Binary Search[1][2]. The practical performance depends on the relative costs of the interpolation arithmetic vs the binary comparisons.

4. If the array contains many equal-valued runs, a naive implementation of Interpolation Search may...