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.
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 the
array is large enough for the doubly-logarithmic win to matter — 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 (e.g. a disk seek or a network
round trip). See Choosing a Search Algorithm
for how it stacks up against the site's other ten Searching entries.