Interpolation Search and What Uniform Key Distribution Buys

Binary search treats a sorted array as an ordered set and nothing more. It learns one bit per comparison: the key is on this side or that side. If the array holds numbers drawn from a known range, each probe carries more information than a bit — the values at the two ends of the interval tell roughly where in the interval a given key should sit. Interpolation search uses that estimate to jump directly to a probable position. On keys drawn uniformly at random, it needs about log log n probes instead of log₂ n; on keys that are clustered, it degrades to a linear scan.

Probing by rank estimate

The rule is linear interpolation on the key axis. Given a search interval with endpoints lo and hi holding values a[lo] and a[hi], the estimated position of key is the fraction of the value range it occupies, mapped onto the index range:

$$ p = lo + \left\lfloor \frac{(key - a[lo]) \cdot (hi - lo)}{a[hi] - a[lo]} \right\rfloor $$

If the array were exactly linear in the key — a[i] = i — this formula lands on the answer in one step. The more nearly linear the key-to-index mapping, the fewer steps are needed. Binary search is the special case that always guesses the midpoint regardless of the values.

/* Interpolation search over a[0..n). Returns an index of key, or -1. */
long interp_search(const long *a, long n, long key)
{
    long lo = 0, hi = n - 1;
    while (lo <= hi && key >= a[lo] && key <= a[hi]) {
        if (a[hi] == a[lo])                 /* all remaining values equal */
            return a[lo] == key ? lo : -1;
        long span = a[hi] - a[lo];
        long p = lo + (long)(((double)(key - a[lo]) * (hi - lo)) / span);
        if (p < lo) p = lo;                 /* clamp against rounding */
        if (p > hi) p = hi;
        if (a[p] == key) return p;
        if (a[p] < key) lo = p + 1;
        else hi = p - 1;
    }
    return -1;
}

Two conditions in the loop header are load-bearing. The key >= a[lo] && key <= a[hi] test exits early when the key lies outside the value range spanned by the interval, which is the usual way an absent key is detected before the interval collapses. The a[hi] == a[lo] guard prevents a division by zero; it also handles the case of a long run of equal values, which would otherwise make the estimate meaningless.

Why the expected probe count is log log n

Model the keys as n independent samples from a uniform distribution over a fixed range. Each probe lands at an estimated position, and the interval that remains is the side the key falls on. The estimate’s error is measured in value space, and a uniform sample of size m has gaps between order statistics that average range/m. Locating a key within an interval of m elements leaves an error of about √m positions, because the deviation of the empirical order statistics from the ideal line grows as the square root of the sample size.

That square root is the whole effect. A probe over m candidates leaves roughly √m still unresolved, so the recurrence T(m) = T(√m) + 1 unwinds in about log log m steps. For a billion keys, binary search needs 30 probes and interpolation search needs about 5. The gain is real but bounded: the logarithm of the logarithm grows so slowly that the advantage at realistic sizes stays in the single digits, never an asymptotic revolution in practice.

The analysis depends entirely on the sampling assumption. It is not merely that the keys are dense in a range; it is that they are distributed in proportion to the index, so that rank and value are approximately affine.

The adversarial case is not exotic

Interpolation search has a worst case of Θ(n) probes. The construction is simple: place keys so that every probe lands at one end of the remaining interval. An exponential key distribution does this without any adversarial intent. Keys 1, 2, 4, 8, … or keys clustered in a few narrow bands both break the affine assumption: the first probe, computed from the interval endpoints, lands near lo every time, and the interval shrinks by one element per probe.

Three families of input cause this in ordinary data:

• Skewed numeric ranges. Account balances, file sizes, and response times are heavy-tailed. A linear estimate over a range from 1 to 10⁹ with most values under 10⁴ puts nearly every probe in the wrong region.
• Concatenated blocks. An array built by appending several separately sorted ranges has discontinuities in the key-to-index slope at the block boundaries. Probes land badly near them.
• Duplicates in long runs. With a thousand copies of one value, the estimate can sit at the edge of the run repeatedly, and the early-exit test does not fire because the key is inside the value range.

The standard remedy is to bound the damage: keep the interpolation step, but fall back to a bisection step whenever the probe does not reduce the interval by a sufficient factor. A common rule accepts the interpolation probe only when it lands in the middle band of the interval — within roughly the square root of the interval length of its centre — and switches to the midpoint otherwise. The resulting algorithm keeps O(log log n) expected behaviour on uniform data and O(log n) worst-case behaviour on anything else. This hybrid is what makes the technique safe enough to use outside a controlled setting.

Arithmetic is the second failure mode

The probe formula multiplies two quantities that are each bounded by the key range and the array length. In 64-bit integers with keys near 2⁶³ and an array of 2³⁰ entries, the product needs about 93 bits. Computed in 64-bit arithmetic it wraps, producing a negative or wildly out-of-range index. The consequences are worse than a slow search: a wrapped index is a read outside the array.

Three ways to compute the probe without overflow:

• Scale first. Divide one factor by the other before multiplying, accepting a small loss of precision: p = lo + (key - a[lo]) / span * (hi - lo). Precision loss matters for small intervals, where it can push the estimate off by one.
• Floating point. Use double, which has 53 bits of mantissa. This is exact enough for the estimate to be within a few positions, which the subsequent probes correct, but it introduces rounding that can make the estimate land one slot off in a way that depends on the platform’s rounding mode.
• Widen. Use a 128-bit intermediate type where the language offers one. GCC and Clang expose __int128 on 64-bit targets; the C standard does not require it.

Whichever route is taken, the estimate must be clamped into [lo, hi] before indexing. Floating-point division of a tiny negative difference by a large span, or of a huge difference by a span of one, both produce values outside the interval, and both occur with valid input.

Where interpolation is worth its risk

Interpolation search pays off when three conditions hold at once: keys are numeric, the distribution is close to uniform or can be made so, and lookups vastly outnumber updates. The classic examples are lookups in dense identifier spaces — timestamps within a known window, sequential record numbers, evenly spaced measurements.

A transformation can create the uniformity. Searching over a log-transformed key turns a heavy-tailed distribution into a roughly uniform one; the array must be sorted by the transformed key, which is a different order than the natural one and therefore a different index. This is the same reasoning that motivates distribution-aware bucketing: instead of estimating a position from the key, compute a bucket from it, which is a one-step version of the same idea.

When the distribution is unknown or changes, the safer structure is not a smarter probe but a tree that adapts. That is the argument for self-adjusting search trees, which reorganise themselves toward the observed access pattern, and it is also the argument for the layouts discussed in the cache-behaviour comparison of search layouts: a probe sequence whose memory traffic dominates its comparison count cannot be improved much by reducing the count. Interpolation reduces probes; it does not reduce the cost of a cache miss, so its advantage shrinks on large arrays where each probe is a DRAM access and grows on arrays small enough to stay in cache.

The honest summary is that interpolation search is a constant-factor improvement with a catastrophic failure mode, and the failure mode is determined by data the algorithm cannot see. Deployed as a hybrid with a bisection fallback it is a reasonable default for numeric keys. Deployed bare it is a trap, and the trap is invisible in testing on random data — the same distribution that makes it look excellent.