Binary Search and Interpolation Search

A search over an array asks whether a target value $x$ appears, and if so, at what index. Without structure, the only guarantee is $\Theta(n)$ linear scanning. Sortedness — the invariant that $A[1] \le A[2] \le \dots \le A[n]$ — is a global property that lets a single comparison at one index rule out an entire contiguous region. If $A[\text{mid}] < x$, then by transitivity every element at or before $\text{mid}$ is also less than $x$, so the target (if present) must lie strictly after $\text{mid}$. This single fact is the entire engine of binary search.

Binary search maintains a candidate window $[\text{lo}, \text{hi}]$ that is guaranteed to contain the target if it exists anywhere in the array, and shrinks this window by roughly half at each step by probing the midpoint. Because the window's size decreases geometrically, the number of iterations needed to shrink it to size zero is bounded by $\log_2 n$, giving the celebrated $\Theta(\log n)$ complexity — a program that finds one item among a billion in about 30 steps.

Interpolation search is a refinement that keeps the same window-shrinking philosophy but changes where it probes. Rather than always bisecting, it uses the numeric values at the endpoints to estimate, via linear interpolation, where $x$ "ought to be" if the data were evenly spread — analogous to opening a dictionary near the back when searching for a word starting with "T." When the underlying key distribution really is close to uniform, this guess is so good that the expected number of probes shrinks to $\Theta(\log \log n)$, a doubly-logarithmic bound that is asymptotically far smaller than $\log n$ (for $n = 2^{32}$, $\log n \approx 32$ but $\log \log n \approx 5$). The cost of this speed is fragility: on skewed, clustered, or adversarially chosen data the interpolation estimate can be consistently wrong, and the algorithm degenerates to linear-time, worst-case behavior.

Binary search operates on a half-open or closed integer index range and maintains two pointers, `lo` and `hi`, representing the current bounds of the search. The key invariant, which must be true before and after every loop iteration, is: > Invariant: if $x$ occurs in $A$, then it occurs at some index $i$ with $\text{lo} \le i \le \text{hi}$. Each iteration computes a midpoint, compares $A[\text{mid}]$ to $x$, and shrinks the window on the side that must still contain $x$ — crucially, it must never discard the midpoint itself without checking it, and it must never re-include an index already ruled out (the classic source of infinite loops or missed elements). ``` function BINARY-SEARCH(A, x): // A is sorted ascending, A[1..n] lo <- 1 hi <- n while lo <= hi: mid <- lo + floor((hi - lo) / 2) // avoids overflow of (lo+hi) if A[mid] == x: return mid // found else if A[mid] < x: lo <- mid + 1 // discard A[lo..mid], x is to the right else: hi <- mid - 1 // discard A[mid..hi], x is to the left return NOT-FOUND ``` Two implementation details matter a great deal in practice. First, `mid <- lo + floor((hi - lo) / 2)` is preferred over `floor((lo + hi) / 2)` because the latter can overflow fixed-width integers when `lo` and `hi` are both large — a real bug that shipped in production binary-search implementations for years. Second, the loop condition `lo <= hi` (not `lo < hi`) together with `mid + 1` and `mid - 1` (not `mid` and `mid`) guarantees the window strictly shrinks each iteration, which is what prevents infinite loops. A common variant, sometimes called lower-bound binary search, does not stop early on equality but instead narrows the window until `lo == hi`, returning the smallest index at which $x$ could be inserted while keeping the array sorted (useful for finding the first occurrence among duplicates, or for insertion points): ``` function LOWER-BOUND(A, x): lo <- 1 hi <- n + 1 // hi is one past the end; open interval [lo, hi) while lo < hi: mid <- lo + floor((hi - lo) / 2) if A[mid] < x: lo <- mid + 1 else: hi <- mid return lo // first index with A[lo] >= x ```

Interpolation search keeps the same two-pointer skeleton but replaces the blind midpoint with a value-weighted estimate. If the keys were perfectly linear between $A[\text{lo}]$ and $A[\text{hi}]$, the target's position would satisfy

This is exactly linear interpolation between two known points, hence the name. ``` function INTERPOLATION-SEARCH(A, x): lo <- 1 hi <- n while lo <= hi and x >= A[lo] and x <= A[hi]: if A[hi] == A[lo]: // avoid divide-by-zero if A[lo] == x: return lo else: return NOT-FOUND pos <- lo + floor( (x - A[lo]) * (hi - lo) / (A[hi] - A[lo]) ) if A[pos] == x: return pos else if A[pos] < x: lo <- pos + 1 else: hi <- pos - 1 return NOT-FOUND ``` Note the guard `x >= A[lo] and x <= A[hi]`: since the estimate assumes $x$ lies between the endpoint values, the loop must terminate (reporting failure) the moment $x$ falls outside the currently bracketed value range, not just the index range. The degenerate case $A[\text{hi}] = A[\text{lo}]$ (all remaining keys equal) is handled separately to avoid division by zero.

Binary search — correctness. The proof is a direct application of the loop invariant stated above. Initialization: before the first iteration, $\text{lo} = 1$ and $\text{hi} = n$, so the invariant "if $x$ is present it lies in $[\text{lo}, \text{hi}]$" holds trivially since $[\text{lo}, \text{hi}]$ is the whole array. Maintenance: suppose the invariant holds at the start of an iteration and $x$ is present at index $i \in [\text{lo}, \text{hi}]$. If $A[\text{mid}] = x$, the algorithm returns the correct index immediately. If $A[\text{mid}] < x$, sortedness implies $A[j] < x$ for all $j \le \text{mid}$, so $i > \text{mid}$, meaning $i \in [\text{mid}+1, \text{hi}]$ — exactly the new window. Symmetrically, if $A[\text{mid}] > x$, then $i < \text{mid}$, so $i \in [\text{lo}, \text{mid}-1]$. In either branch the invariant is preserved for the shrunk window. Termination: the loop runs while $\text{lo} \le \text{hi}$. If it exits because $\text{lo} > \text{hi}$, the window is empty, and by the invariant $x$ cannot be present anywhere, so `NOT-FOUND` is correct. Since $\text{hi} - \text{lo}$ strictly decreases every iteration (either $\text{lo}$ increases past mid or $\text{hi}$ decreases below mid), the loop is guaranteed to terminate.

Binary search — complexity. Let $T(n)$ be the number of comparisons on a window of size $n$. Each iteration inspects one element and recurses on a window of size at most $\lfloor n/2 \rfloor$ (the larger of the two halves), giving the recurrence

By the Master Theorem (or direct unrolling: after $k$ halvings the window has size $n/2^k$, which reaches $1$ when $k = \log_2 n$), this solves to $T(n) = \Theta(\log n)$. This holds in the best case (target found immediately, $O(1)$), average case, and worst case — the $\log n$ bound is essentially tight in all regimes because the window size determines progress deterministically, regardless of where $x$ actually is. Space complexity is $O(1)$ for the iterative version (two pointers), or $O(\log n)$ for a naive recursive version due to call-stack depth — a good reason to prefer the iterative form in production code.

Interpolation search — correctness. The same invariant argument used for binary search applies verbatim: at every iteration, if $x$ is present, it lies in $[\text{lo}, \text{hi}]$, because the branch taken only discards a region proven (by sortedness) not to contain $x$. Interpolation search is binary search's invariant with a different probe rule — changing where you look inside a range that is known to bracket the answer never breaks correctness, as long as every discarded region is provably excluded. The extra guard checking $x$ against $A[\text{lo}]$ and $A[\text{hi}]$ ensures the algorithm reports failure rather than computing a nonsensical or out-of-range `pos` when $x$ cannot possibly be present.

Interpolation search — complexity. The worst case is $\Theta(n)$: consider an array where $A[1..n-1]$ are all $0$ and $A[n] = 10^9$, searching for a value near the low end can force the interpolation estimate to repeatedly land near `hi`, shrinking the window by only one element per probe (much like a bad pivot choice in quicksort). This is the fundamental tradeoff — interpolation search trades a worst-case guarantee for potentially much better average-case performance. Under the assumption that keys are drawn i.i.d. from a distribution close to uniform on a real interval, a classical analysis (Yao & Yao, and independently Perl, Itai, and Avni, 1978) shows the expected number of probes is

The intuition: interpolation search's estimate error shrinks quadratically relative to the window size at each step under uniformity, rather than merely halving. Concretely, if $N_k$ denotes the expected window size after $k$ probes, one can show heuristically that $N_{k+1} \approx \sqrt{N_k}$ rather than $N_{k+1} \approx N_k / 2$. Since squaring the exponent of a logarithm each round, $\log N_{k+1} \approx \frac{1}{2}\log N_k$, repeated squaring of the window size itself means the number of rounds needed to shrink $\log N_k$ down to a constant is only $\Theta(\log \log n)$, versus $\Theta(\log n)$ rounds needed when the window merely halves each time. This doubly-exponential shrinkage is the entire reason interpolation search can dramatically outperform binary search on well-behaved numeric data — but it is precisely this reliance on the "linear-interpolation-is-a-good-guess" assumption that makes it fragile on non-uniform inputs.

Consider a sorted array of examination scores (values, 1-indexed):

Binary search for $x = 47$ (traced in the figure above):

Three comparisons versus a hypothetical linear scan that would need ten.

Interpolation search for the same $x = 47$, same array, $\text{lo}=1$ ($A[\text{lo}]=2$), $\text{hi}=15$ ($A[\text{hi}]=80$):

$A[9] = 40 < 47$, so $\text{lo} \leftarrow 10$. Recompute with $\text{lo}=10$ ($A[\text{lo}]=47$), $\text{hi}=15$ ($A[\text{hi}]=80$):

$A[10] = 47$ — found in 2 probes, one fewer than binary search, because the values happen to be nearly evenly spaced and interpolation's linear guess landed close to the true position immediately.

Contrast on skewed data. Suppose instead the array is

Interpolation search computes, with $\text{lo}=1$ ($B[\text{lo}]=1$), $\text{hi}=15$ ($B[\text{hi}]=10^9$):

$B[1] = 1 < 7$, so $\text{lo} \leftarrow 2$. The next estimate barely moves either, because the enormous outlier at index 15 flattens the interpolation slope, forcing the window to shrink by roughly one index per probe — degrading toward the $\Theta(n)$ worst case despite the array being perfectly sorted. Binary search, unaffected by magnitude, still finds $x=7$ in $\lceil \log_2 15 \rceil = 4$ probes regardless of this skew.

Binary search's core idea — bisecting an ordered range — predates modern computing, but its rigorous algorithmic treatment and the notorious subtlety of implementing it correctly were documented in depth by Donald Knuth, who famously noted that although the basic idea was published as early as 1946, the first fully correct published version did not appear until 1962, and many "textbook" implementations in between contained bugs. Interpolation search was formalized and analyzed rigorously in the late 1970s, with the expected $O(\log \log n)$ bound established through independent probabilistic analyses.

Binary search underlies `std::lower_bound`/`std::upper_bound` in C++, the `bisect` module in Python, `Arrays.binarySearch` in Java, and countless database B-tree node lookups where sorted keys within a node are searched before descending. Version control systems expose `git bisect`, a direct application of the binary-search invariant to find the commit that introduced a regression by testing the "midpoint" commit and discarding half the history each round. Compilers and interpreters use sorted symbol tables searched via binary search for fast identifier resolution. Interpolation search finds use in specialized settings — indexing large numeric datasets with roughly uniform key distributions, such as certain database indexes on auto-incrementing IDs or timestamps — though many production systems favor binary search or hybrid schemes (falling back to binary search when interpolation estimates misbehave) precisely because of interpolation search's brittle worst case. The same divide-and-shrink philosophy that powers binary search reappears, transformed, in Linear-Time Selection, where a clever pivot-choosing strategy achieves worst-case linear time on unsorted arrays by discarding a guaranteed fraction of elements each round — an idea deeply related to, yet fundamentally different from, the sorted-array assumption that makes binary search possible. Both algorithms also rely on Array Indexing providing $O(1)$ random access — a precondition that fails for linked lists, where binary search's advantage disappears entirely.

Ask the tutor: How does the choice between binary search's guaranteed Θ(log n) and interpolation search's expected Θ(log log n) change if the keys are integers with many repeated values rather than continuous real numbers?