Interpolation Search
Instead of always probing the middle, estimate where the target should be from its value — O(log log n) on uniformly distributed keys.
Hands on Interactive visualization
Implementation Code
export function interpolationSearch(a: number[], target: number): number {
let lo = 0;
let hi = a.length - 1;
while (lo <= hi && target >= a[lo] && target <= a[hi]) {
if (a[lo] === a[hi]) {
// One distinct value left: avoid division by zero.
return a[lo] === target ? lo : -1;
}
// Linear estimate: how far along the value range is the target?
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;
}Big-O Complexity
O(log log n) average holds only for uniformly distributed keys; skewed or clustered data (exponential gaps, duplicates) degrades every probe estimate, all the way to O(n).
In production When to use
Auto-increment IDs, evenly spaced timestamps, sensor readings at fixed intervals — when position is nearly a linear function of value, the interpolated guess lands almost exactly on target.
Finding a timestamp in a large append-only log with roughly constant event rate: the proportional guess (elapsed fraction × length) is usually within a few entries of the answer.
Locating percentile boundaries or value ranges in large sorted numeric columns where the distribution is known to be close to uniform after transformation.
Modern learned indexes generalize the same bet: model the key-to-position function (interpolation uses a straight line, learned indexes fit better models) and correct locally around the prediction.
Practical systems interpolate for the first probe or two to get close fast, then fall back to binary search for guaranteed convergence — capturing the average-case win without the O(n) tail.
Trade-offs Strengths & weaknesses
- O(log log n) average on uniform data — 5 probes where binary search needs 30, at n = 10⁹.
- O(1) extra space, same as binary search.
- First probe is often within a handful of elements of the target on well-behaved data.
- The conceptual basis of learned indexes and interpolation-based B-tree node search.
- Combines cleanly with binary search as a guarded hybrid.
- Degrades to O(n) on skewed, clustered, or exponentially spaced keys.
- Requires numeric keys (or an order-preserving numeric mapping) — no plain comparators.
- The probe formula invites division-by-zero and overflow bugs.
- Each probe costs arithmetic (multiply, divide) on top of a comparison.
- Worse worst case than binary search makes it risky as an unguarded default.
Intuition Mental model
Opening the phone book proportionally
Looking up a name starting with W, nobody opens a phone book in the middle — you open it near the back, because you know roughly where W lives in the alphabet. Interpolation search turns that instinct into a formula.
- Estimate the fraction: W is about 85% through the alphabet, so open 85% of the way through the book.
- Land, read the page, and see how far off you are — usually only a few pages.
- Re-estimate proportionally within the smaller range and open again.
- Each guess shrinks the range from n toward √n — far faster than halving.
- The trick fails on a phone book where half the town is named Smith: proportional guessing needs evenly spread names.
Prep Interview questions
Derive the interpolation probe formula. What assumption makes it work?
Why is the average O(log log n), intuitively?
Construct an input that forces interpolation search to O(n).
How do you make interpolation search safe in production?
How does this relate to learned indexes?
Watch out Common bugs
A window of equal keys zeroes the denominator. Handle it explicitly: if a[lo] == a[hi], the answer is a single equality check, not a formula.
The numerator multiplies a value gap by an index gap — comfortably past 32-bit range on large inputs. Compute in 64-bit (or arbitrary precision) before dividing.
If the target lies outside [a[lo], a[hi]], the formula extrapolates an index outside [lo, hi] and indexes out of bounds. Check the range first or clamp pos into the window.
On adversarial distributions the window shrinks by one per iteration; combined with a subtle boundary bug this becomes an infinite loop. Cap iterations or verify the window strictly shrinks.
One screen Cheat sheet
Binary search that guesses proportionally to the value gap instead of always picking the middle.
- pos = lo + (target - a[lo]) · (hi - lo) / (a[hi] - a[lo]) — a linear estimate of position.
- O(log log n) average requires uniformly distributed numeric keys.
- Worst case O(n) on skewed data — always guard or hybridize with binary search.
- Guard a[hi] == a[lo] (division by zero) and do the multiply in a wide integer type.
- Each probe shrinks n toward √n on uniform data — squaring-down, not halving.
- Ancestor of learned indexes: model position from value, correct locally.