Interpolation search
mediumIf 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.
O(1)Average O(log log n)Worst O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How interpolation search works
Nobody looks up 'Zhang' by opening the phone book in the middle - you estimate: near the back. Interpolation search does that arithmetic on a sorted array. The target's fractional position between a[lo] and a[hi] becomes the probe index: pos = lo + (target - a[lo]) × (hi - lo) / (a[hi] - a[lo]).
On uniformly spread values the estimate lands almost exactly, and the range collapses faster than halving ever could: O(log log n) probes on average - about 4 for a million elements, against binary search's 20. This module's default array, 10 through 160 in even steps, finds most targets in one or two probes.
The speed is borrowed from an assumption. On skewed data - exponentially growing values, tight clusters - the proportional guess lands far from the target and the worst case is O(n), worse than binary search's guaranteed O(log n). It also needs keys you can subtract and divide, not merely compare. A specialist, not a default.
Step by step
- Search for 120 in [10, 20, 30, ..., 160] - 16 sorted, evenly spaced values. lo = 0, hi = 15.
- Check the brackets first: 10 <= 120 <= 160, so the target lies inside the value range and probing makes sense.
- Compute the fraction: 120 is (120 - 10) / (160 - 10), about 73% of the way through the values.
- pos = 0 + floor(110 × 15 / 150) = 11. Probe index 11, not the midpoint 7 that binary search would pick.
- a[11] = 120 - found in a single probe. Binary search's first probe would have landed on a[7] = 80, nowhere near.
- If the bracket check ever fails - the target outside a[lo]..a[hi] - the loop exits immediately and reports absence.
Complexity
| Best case time | O(1) |
|---|---|
| Average time | O(log log n) |
| Worst case time | O(n) |
| Space | O(1) |
The average assumes uniformly distributed values; skew destroys it.
Reference implementation
Python
def interpolation_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi and a[lo] <= target <= a[hi]:
if a[hi] == a[lo]: # flat range - avoid dividing by 0
return lo if a[lo] == target else -1
pos = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])
if a[pos] == target:
return pos
if a[pos] < target:
lo = pos + 1
else:
hi = pos - 1
return -1JavaScript
function interpolationSearch(a, target) {
let lo = 0, hi = a.length - 1;
while (lo <= hi && target >= a[lo] && target <= a[hi]) {
if (a[hi] === a[lo]) return a[lo] === target ? lo : -1;
const pos = lo + Math.floor(((target - a[lo]) * (hi - lo)) / (a[hi] - a[lo]));
if (a[pos] === target) return pos;
if (a[pos] < target) lo = pos + 1; else hi = pos - 1;
}
return -1;
}Worth noticing
It guesses where the value should be, like using a phone book
Looking for 'Zhang', nobody opens the book in the middle. Interpolation search does the same arithmetic: if the target is 90% of the way through the value range, probe 90% of the way through the array.
O(log log n) on uniform data - and O(n) when it is wrong
On evenly spread values it converges astonishingly fast. Load the 'random' preset and watch the probe land badly: on skewed data the guess can be off by almost everything, and it degrades to linear.
Common pitfalls
- Dividing by zero when a[hi] equals a[lo]. A flat range must short-circuit - this implementation returns lo if it holds the target, -1 otherwise, before the formula runs.
- Probing without the bracket check. When the target lies outside a[lo]..a[hi], the formula happily produces an index outside the range - the guard a[lo] <= target <= a[hi] is load-bearing.
- Overflowing the numerator: (target - a[lo]) × (hi - lo) can exceed 32-bit range on large arrays with large values - compute it in 64-bit.
- Trusting O(log log n) on data that is merely sorted. The bound assumes near-uniform spacing; load the random preset here and watch the probes land badly and the rounds multiply.
- Using it on keys where subtraction is meaningless - strings, composite keys. Interpolation needs arithmetic on values; binary search only ever needs an ordering.
Where it is used
- Sorted numeric tables with near-uniform keys - auto-incremented IDs, evenly sampled timestamps - where probes drop to a handful.
- Disk-resident sorted files where every probe is a seek: cutting 20 probes to 4 or 5 is a real win.
- The phone book and dictionary lookup story - the canonical example of estimate-then-probe search.
- Interviews: the classic follow-up to binary search - state the O(log log n) average and exactly when it collapses to O(n).
Frequently asked questions
What is the time and space complexity of interpolation search?
Best case O(1) - a single perfect estimate. Average case O(log log n), but only on uniformly distributed values; for a million elements that is about 4 probes against binary search's 20. Worst case O(n) when the distribution defeats the estimate. Space is O(1).
Why is interpolation search O(log log n) on average?
A proportional probe does not merely halve the live range - on uniform data it shrinks a range of m candidates to about √m expected. Halving repeatedly takes log n rounds; square-rooting repeatedly takes log log n. The result holds only under the uniform-distribution assumption, which is why skew destroys it.
When is interpolation search worse than binary search?
Whenever values are far from evenly spread. On exponentially growing data like 1, 2, 4, 8, the proportional estimate keeps landing near one end, discards almost nothing per round, and the search degrades toward O(n) - while binary search stays at O(log n) regardless of distribution.
Does interpolation search need a sorted array?
Yes, and more: sorted order makes the bracketing logic valid, and a roughly uniform spread of values makes the position estimate accurate. Sorted-but-skewed data is legal input with poor performance. Unsorted data is simply wrong input - as with binary search, the result is meaningless.