Cairn
algorithms · searching · O(log log n) average (uniform data), O(n) worst case

↩ back to Searching

Interpolation Search

Binary search always checks the middle of the remaining range, no matter what the values look like. Interpolation search makes a smarter guess: if the range holds sorted numbers spread out roughly evenly, a target near the top of the value range is probably near the top of the index range too. Instead of always probing the midpoint, it probes wherever straight-line interpolation between arr[lo] and arr[hi] predicts the target should sit — the same idea as flipping straight to "S" in a phone book to look up "Smith" instead of opening to the middle first. On uniformly spread data this converges shockingly fast, in O(log log n) average probes. The catch — the whole reason this page exists — is that the guess is only as good as the uniform-spread assumption, and data that violates it can make interpolation search degrade to a full O(n) linear scan while binary search, indifferent to the values themselves, keeps its O(log n) guarantee regardless.

Try it

Enter a sorted, comma-separated list of numbers and a target, then step through the search. The array will be sorted automatically if it isn't already. The distribution preset loads two contrasting examples — evenly-spread values where interpolation search wins big, and a deliberately skewed array where it degrades toward a linear scan on the exact same data a binary search would still crack in a handful of probes.

Press Load, then Step through the search.

Why it works

Binary search's invariant is "the target, if present, is between lo and hi" — it says nothing about values, so the only unbiased place to look is the middle. Interpolation search keeps that same invariant but adds one more piece of information it's willing to trust: the values at the two ends, arr[lo] and arr[hi], plus the assumption that the values in between are roughly evenly spread across that range. Under that assumption, the fraction of the way the target sits between arr[lo] and arr[hi] by value should be close to the fraction of the way it sits between lo and hi by index — so probe there instead of the midpoint:

pos = lo + floor( (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]) )

Each probe still throws away one side entirely, exactly like binary search — the difference is only where it chooses to look. When the data really is close to uniform, this guess lands close to the answer almost immediately (the classic result is that the expected number of probes is O(log log n), doubly logarithmic — for a billion uniformly-spread elements, binary search needs about 30 probes and interpolation search needs about 5). When it isn't uniform, the guess can be badly wrong, and the range only shrinks by however far off the guess was — in the worst case, by one element per probe, same as a linear scan.

Reference implementation

function interpolationSearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    if (target < arr[lo] || target > arr[hi]) return -1; // out of range
    if (lo === hi || arr[hi] === arr[lo]) {
      return arr[lo] === target ? lo : -1; // single value left, or a flat run
    }
    const pos = lo + Math.floor((target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));
    if (arr[pos] === target) return pos;
    if (arr[pos] < target) lo = pos + 1;
    else hi = pos - 1;
  }
  return -1; // not found
}

Pitfalls

The uniform-spread assumption can fail badly, and nothing detects it. Load the skewed preset above: eleven consecutive integers 0..10 followed by one outlier a million higher, searching for 10. arr[lo] and arr[hi] are a million apart, so the formula's very first guess lands almost at the far end — and every probe after that only rules out one more index, because the rest of the range is still just as lopsided. This exact array and target take interpolation search 11 probes (effectively a full linear scan of the 12-element array) where binary search, run on the identical array and target, needs only 3. Interpolation search never notices anything went wrong; it just quietly does more work. Real-world data with this shape isn't exotic — timestamps with a burst of activity, IDs with a few far-future placeholders, measurements with an outlier — and there's no cheap way to tell in advance whether a given array is uniform enough to trust, short of already knowing its distribution.

Division by zero, guarded explicitly. If arr[hi] === arr[lo] (every value left in range is the same, a flat run of duplicates) the formula's denominator is zero. The reference implementation above checks for this before computing pos and falls back to a direct comparison — skip that check and a flat run of duplicates anywhere in the array produces NaN instead of an index, silently breaking the search rather than just running slower.

The formula assumes numeric, evenly-comparable values. Binary search only ever needs </>/= and works on any ordered type — strings, dates, custom comparators. Interpolation search's formula does arithmetic on the values themselves, so it only works directly on numbers (or something mapped to numbers first); there's no such thing as interpolating "how far between two strings" without inventing your own numeric encoding first.

Measuring the real gap

The Complexity section below says the gap between log log n and log n "is negligible for small n and only becomes dramatic at the sizes where every probe is expensive" — true in spirit, but written with no number behind it, and the demo above tops out at 11 elements. Measured directly here: this page's own shipped interpolationSearch above, instrumented to count real probes (not estimated from the formula), against binary search's own shipped function, same instrumentation, both run on arrays of n i.i.d. uniform random values, sorted — the textbook setting the O(log log n) average case assumes, not evenly-spaced indices (which the formula solves in a single probe every time, an idealized case this page's own demo doesn't represent either). Correctness cross-checked first: both functions agree on found/not-found and on the matching index, 1,600/1,600 trials across n from 1 to 5,000.

n             interpolation   binary   gap    interp/binary
10            1.9             2.9      1.0    0.66
100           2.5             5.8      3.3    0.44
1,000         3.6             9.0      5.4    0.40
10,000        3.5             12.4     8.9    0.28
100,000       4.2             15.7     11.5   0.27
1,000,000     4.3             19.0     14.7   0.23
100,000,000   4.9             25.7     20.8   0.19

Both curves track their asymptotic bound closely — interpolation search's 4.9 measured probes at n=100,000,000 against log₂log₂n's own 4.73, binary search's 25.7 against log₂n's own 26.58 — confirming the two bounds aren't just theory, they show up directly in the real shipped code's own probe counts. But the last column shows the page's "negligible for small n" framing undersells how early the relative win shows up: by n=100 — a genuinely small array, nowhere near a "disk seek or network round trip" scale — interpolation search is already using under half as many probes as binary search, and by n=1,000 it's already down to two fifths.

What actually stays small at small n is the absolute gap, not the ratio: about one probe at n=10, three at n=100, growing to 21 at n=100,000,000. That absolute gap is what the "expensive probe" framing is really pointing at, and it ties to the wrong variable: it isn't that n itself has to be huge for the saved probes to matter, it's that each probe's own cost has to be more than a few nanoseconds. A handful of saved probes is genuinely negligible at the cost of one in-memory comparison, at any n in the table above — but that same handful of probes, at the cost of one disk seek or network round trip, is already a perceptible latency win at n=100, long before the array needs to be "large."

Complexity

Average case O(log log n) probes on uniformly-distributed sorted data; worst case O(n) on adversarial or heavily-skewed data, same as a linear scan — the skewed example above is a small, concrete instance of that worst case, not a hypothetical one. Binary search is the safer default precisely because its O(log n) guarantee doesn't depend on the data's shape at all; interpolation search is worth reaching for only when the data is known (not just hoped) to be roughly uniform and each probe's own cost is high enough for the doubly-logarithmic win to matter — see measuring the real gap above for why that's a question about probe cost, not array size: the relative savings are already large by a few hundred elements, well short of "large." See Choosing a Search Algorithm for how it stacks up against the site's other eleven Searching entries.