What is the time complexity of interpolation search?

Best case O(1). Average case O(log log n). Worst case O(n). Space complexity is O(1). The average assumes uniformly distributed values; skew destroys it.

Interpolation search

medium

If the target is 90% of the way through the value range, probe 90% of the way through the array. Astonishingly fast on uniform data, and linear when the guess is wrong.

Best O(1)Average O(log log n)Worst O(n)Space O(1)

Loading the interpolation search engine…

Where to go next

Binary search

easy

Halve the search space with every comparison.

Jump search

easy

Skip in blocks of √n, then scan backwards.

Exponential search

medium

Double the reach until you overshoot, then binary search.