Interpolation Search

What is interpolation search?

Interpolation search finds a key in a sorted list by guessing where it should be, based on its value. Binary search always checks the middle. Interpolation search checks where the key would sit if the values were spread out evenly.

You already do this. Looking up “Williams” in a phone book, you don’t open it in the middle. You open it near the end, because W is near the end of the alphabet. Looking up “Baker”, you open it near the front.

When values are spread evenly, this is incredibly fast. When they are not, it can be slow. The demo lets you see both sides of that.

How it works, step by step

Press play above. lo and hi mark the range that can still hold the key, and the bars outside it fade out. The blue bar is the probe: the position the formula guessed.

1. Set lo = 0 and hi to the last index.
2. Check that the key is between a[lo] and a[hi]. If it isn’t, it can’t be in the list.
3. Guess a position: probe = lo + (key − a[lo]) × (hi − lo) / (a[hi] − a[lo]). This asks: what fraction of the way from a[lo] to a[hi] is the key? Then go that fraction of the way from lo to hi.
4. If a[probe] is the key, return it.
5. If a[probe] is smaller, move lo to probe + 1. If bigger, move hi to probe - 1.
6. Repeat until you find the key or the range is empty.

Watch the first probe in the demo. It often lands right on the key, or very close, on the first try.

Time and space complexity

Best case, O(1): the first guess is right.

Average case, O(log log n), for values spread evenly (uniformly) over their range. That grows unbelievably slowly: for a billion values, log₂ log₂ n is about 5. Each good guess shrinks the range far more than a halving does.

Worst case, O(n): skewed values. Picture [1, 2, 3, 4, 5, 6, 7, 8, 9, 1000] and a search for 9. The huge last value makes every guess land near the start, and the search creeps forward one step at a time, like a linear search.

Space is O(1). Two bounds and a probe.

Common mistakes

• Dividing by zero. If a[hi] == a[lo], the formula breaks. Check for it and probe lo directly.
• Skipping the range check. If the key is below a[lo] or above a[hi], the formula gives a position outside the list.
• Doing the math with floats and rounding the wrong way. Use integer math, multiplying before dividing, so the probe stays inside [lo, hi].
• Using it on data you know nothing about. On skewed data it can be far slower than binary search.

When to use it

Use it when the data is sorted, large, and spread fairly evenly: sequential IDs, timestamps at a steady rate, or evenly distributed numbers. That is also the idea behind some database indexes that learn how the data is spread and jump straight to it.

When you don’t know how the data is spread, binary search is the safer choice. It guarantees O(log n) no matter what. A common compromise is to start with interpolation and switch to binary search if the guesses aren’t shrinking the range fast enough.

Questions

Is interpolation search faster than binary search?

On evenly spread data, yes: O(log log n) against O(log n). On skewed data it can drop to O(n), which is much worse.

Does interpolation search need sorted data?

Yes. The guess only makes sense if the values increase along the list.

What does interpolate mean here?

Estimating a position between two known points. Here, the two known points are the values at lo and hi.