Overview
Interpolation Search improves on Binary Search for sorted, uniformly distributed data. Instead of always probing the middle, it estimates where the target likely lies based on its value relative to the range endpoints — much like guessing a name's page in a phone book.
When values are spread evenly, this value-aware probe lands very close to the target, so the algorithm can outpace Binary Search. On skewed data, however, the estimates are poor and performance degrades sharply.
How Interpolation Search works
- Set low and high to the bounds of the sorted array.
- Estimate a probe position by interpolating the target's value between the values at low and high.
- Compare the element at that probe with the target.
- If the target is larger, move low past the probe; if smaller, move high before it.
- Repeat until the value is found or the range becomes empty.
When to use it
- Large sorted arrays of numeric keys that are uniformly distributed.
- Lookups where values grow smoothly, such as sequential IDs or evenly spaced measurements.
- Avoid it on clustered or skewed data, where Binary Search's guarantees are safer.
Complexity analysis
On sorted, uniformly distributed data Interpolation Search averages O(log log n) time — faster than Binary Search — because each probe narrows the range aggressively. But on skewed or clustered data the estimates are unreliable and it can degrade to O(n) in the worst case. It uses O(1) extra space.
Frequently asked questions
How is Interpolation Search different from Binary Search?
Binary Search always probes the midpoint; Interpolation Search probes where the target's value suggests it should be. That guess is excellent on uniform data but unreliable when values are unevenly spaced.
When does Interpolation Search perform badly?
On skewed or clustered distributions the interpolation formula repeatedly guesses far from the target, so the range shrinks slowly and the cost can approach the O(n) of a linear scan.