Improved Binary Search | Distribution-Sensitive | O(log log n) avg
Looking up "Zebra" in a paper dictionary, you don't open to the exact middle -- you flip almost to the back, because you already know Z lives near the end. Interpolation search teaches a computer that same trick: use the value you are hunting to guess where it probably sits, instead of blindly splitting the list in half.
A plain binary search always probes the midpoint. Interpolation search instead asks: if the values climb smoothly from the smallest $A[lo]$ up to the largest $A[hi]$, what fraction of the way up is my target? That fraction, times the width of the live window, points to the next probe:
Worked number: suppose a window holds the values $0$ to $1000$ spread evenly across indices $0$ to $100$, and we want $800$. The fraction is $800/1000 = 0.8$, so $pos = 0 + 0.8 \times 100 = 80$ -- a single jump straight to index $80$, where binary search's first guess would have been the midpoint $50$.
Why is this so fast? On uniformly spaced data each good probe does not just halve the window -- it shrinks it by a square-root factor, leaving about $\sqrt{n}$ candidates. After $k$ probes roughly $n^{1/2^k}$ elements remain; once that reaches a small constant, $2^k \approx \log_2 n$, so $k \approx \log_2 \log_2 n$. That is the celebrated $O(\log\log n)$: for a billion uniformly distributed integers, about $5$ probes versus binary search's $\sim 30$. The catch is the assumption of even spacing -- if the values are clustered or grow exponentially, the straight-line estimate misses badly and the cost can degrade all the way to $O(n)$, no better than scanning one by one.
Try this with the controls above: (1) Open the preset menu and choose Sorted so the values become evenly spaced ($5, 10, 15, \ldots$) -- the best case, where the formula's straight-line guess is almost exact. (2) Type a clustered list such as 1,2,3,4,5,500 into the custom box and press Apply: a single huge value warps the spacing, the exact situation where interpolation search misfires. (3) Drag the $n$ slider higher and picture the probe count -- binary search needs about $\log_2 n$ steps, while interpolation needs only about $\log_2 \log_2 n$ when the data is evenly spaced, so it barely grows at all.
| Symbol | Meaning |
|---|---|
| n | Input size |
| T(n) | Time complexity function |
| h | Height or depth of structure |
| k | Key or rank parameter |
| W(n) | Worst-case complexity |
| A(n) | Average-case complexity |
X Interpolation Search is always faster than Binary Search.
O Only for large, uniformly distributed numeric data. For strings, skewed data, or small arrays, Binary Search wins.
X O(log log n) is the guaranteed time complexity.
O Only expected time for uniform distribution. Worst case is O(n).
X It works directly on any data type.
O Formula requires arithmetic on values. Strings need lexicographic comparison. Only use for numeric keys.
X Forgetting to check A[hi]==A[lo] before computing pos.
O Division by zero if A[hi]==A[lo]. Always guard: if A[hi]==A[lo]: check target==A[lo].
X Using int arithmetic -- overflow risk.
O Use 64-bit: (long)(target-A[lo])*(hi-lo)/(A[hi]-A[lo]). 32-bit overflows for large values.
X Not checking target in [A[lo],A[hi]] in loop condition.
O Without bounds check, pos can be outside [lo,hi] causing out-of-bounds access.