Interpolation Search

Interpolation search is binary search's sharper cousin. Binary search always splits the remaining window in half. Interpolation search instead guesses where the value should be — assuming the data rises at a roughly even rate — and probes that spot directly. On uniformly-spaced data the guess lands right on the answer, so the average cost drops to a remarkable O(log log n).

The example array is [10, 12, 15, 20, 30, 45, 65, 80, 90] and we search for x = 65. Watch how the first probe almost nails it and the second finishes the job.

Intuition

Open a phone book to find a name starting with B. You do not flip to the exact middle — you open near the front, because B is near the front of the alphabet. That instinct is interpolation search: you use the value of the key, not just the count of remaining pages, to decide where to look.

Binary search ignores values entirely; every step it halves the window, giving O(log n). Interpolation search reads the actual numbers at lo and hi, draws a straight line between them, and reads off where the target would fall on that line. When the data really is evenly spaced, that line is almost exact, so each probe eliminates far more than half the window — and the number of probes collapses to O(log log n).

Walk through it

Step through the animation on the right. The lo and hi pointers (below the cells) bracket the live window; pos (above the cells) is the interpolated probe.

The first probe computes pos = 0 + (65 - 10) * (8 - 0) // (90 - 10) = 55 * 8 // 80 = 5. The pointer jumps to index 5, where a[5] = 45. That is smaller than 65, so the target must be further right — we move lo to 6 and shrink the window.

The second probe runs on the window [6 .. 8]: pos = 6 + (65 - 65) * (8 - 6) // (90 - 65) = 6. The pointer lands on index 6, where a[6] = 65 — the target. Found in two probes for a nine-element array, versus the three or four a midpoint split would have taken.

The code, line by line

def interpolation_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= x <= a[hi]:
        if a[lo] == a[hi]:
            return lo if a[lo] == x else -1
        pos = lo + (x - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[pos] == x:
            return pos
        if a[pos] < x:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1

• Line 3 is the loop guard. Besides lo <= hi, it also checks a[lo] <= x <= a[hi]: if the target falls outside the current value range, it cannot be in the window, so we stop. This guard also keeps pos from ever going out of bounds.
• Lines 4-5 guard against division by zero. If a[lo] == a[hi] the values are flat, the formula would divide by 0, so we just test that single value directly.
• Line 6 is the heart: the interpolation formula. (x - a[lo]) is how far the target is above the low value; dividing by (a[hi] - a[lo]) turns that into a fraction of the value range; multiplying by (hi - lo) scales it into an index offset from lo.
• Lines 7-8 return the moment a probe hits the target.
• Lines 9-12 narrow the window exactly like binary search: if the probe undershot, push lo past it; if it overshot, pull hi below it.
• Line 13 returns -1 when the window collapses without a hit.

Complexity

The headline O(log log n) only holds when the keys are close to uniformly distributed. On adversarial or exponentially-spaced data the linear guess is consistently wrong, the window barely shrinks, and the cost balloons toward O(n) — worse than binary search. The space cost is O(1): just the lo, hi, and pos integers.

When to use / pitfalls

Practice