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.
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.
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.
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
}
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.
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."
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.