The position estimate is a straight-line interpolation between the endpoints:
pos = lo + ((target − a[lo]) × (hi − lo)) / (a[hi] − a[lo])
Take [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] and search for 70. With lo=0, hi=9, a[lo]=10, a[hi]=100:
pos = 0 + ((70 − 10) × 9) / (100 − 10) = 540 / 90 = 6
Index 6 holds exactly 70. One probe. Binary search would have needed three or four. On perfectly uniform data the first guess is often exact, and that is where the method’s reputation comes from.
Why log log n, and when it collapses
On uniformly distributed data each probe does not merely halve the remaining range — it reduces it to roughly its square root. That gives an average of O(log log n) comparisons, which for a million elements is about 4 rather than binary search’s 20.
But the estimate assumes values grow linearly with index. When they do not, the guess is bad, and consistently bad guesses walk the array one element at a time. On exponentially distributed data such as [1, 2, 4, 8, 16, …, 2n] the interpolation lands near the start every single time and the worst case degrades to O(n) — worse than the binary search it was meant to improve on.
Guessing where the value should be
Binary search always probes the middle. Interpolation search probes where the value ought to be, assuming the data is evenly spread.
Looking for 70 in [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]: binary search checks index 4 (value 50). Interpolation search reasons that 70 is 67% of the way from 10 to 100, so it probes index 6 — and finds it immediately.
The probe position comes from linear interpolation:
pos = lo + (target − arr[lo]) × (hi − lo) / (arr[hi] − arr[lo])
def interpolation_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi and arr[lo] <= target <= arr[hi]:
if arr[lo] == arr[hi]: # avoid division by zero
return lo if arr[lo] == target else -1
pos = lo + (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
Two guards matter. The arr[lo] == arr[hi] check prevents division by zero on a uniform range. And the loop condition includes arr[lo] <= target <= arr[hi], which exits immediately when the target is outside the current range — binary search does not need this because it never extrapolates.
O(log log n), and the condition attached
For uniformly distributed numeric data, interpolation search runs in O(log log n).
That is remarkably small. For a million elements, binary search takes 20 probes; interpolation search takes about 4.
| n | Binary search | Interpolation search (uniform) |
|---|
| 1,000 | 10 | ~3 |
| 1,000,000 | 20 | ~4 |
| 1,000,000,000 | 30 | ~5 |
The condition is doing all the work in that table. On non-uniform data the interpolation misleads, and the worst case is O(n) — worse than binary search's guaranteed O(log n).
The classic bad case is exponentially distributed values: [1, 2, 4, 8, 16, ..., 2⁶⁴]. Searching for a small value, interpolation assumes it is near the start of a range whose upper end is astronomically large, so it probes almost at the beginning and advances one position at a time.
| | Binary | Interpolation |
|---|
| Uniform data | O(log n) | O(log log n) |
| Any data | O(log n) guaranteed | O(n) worst case |
| Requires | Sorted | Sorted and numeric and roughly uniform |
| Arithmetic per probe | One shift | Multiply and divide |
Whether it is worth using
Honestly: rarely, and it is worth understanding why.
The requirements are strict. The keys must be numeric (you cannot interpolate between strings meaningfully), sorted, and reasonably uniformly distributed. Real data frequently fails the third condition.
The arithmetic is more expensive. Binary search's midpoint is an addition and a shift. Interpolation requires a multiplication and a division per probe, and division is slow. With only 20 probes to save, the per-probe cost matters.
The worst case is worse. Trading a guaranteed O(log n) for an average O(log log n) with an O(n) tail is a poor trade for most systems, where predictability matters.
Cache effects dominate at scale. On a large array, each probe is likely a cache miss regardless of the algorithm, so the number of probes matters less than it appears — and fewer, more scattered probes do not help as much as the complexity suggests.
Where it does earn its place: large, static, genuinely uniform numeric datasets. Searching a sorted array of timestamps evenly spaced in time, or of uniformly distributed identifiers, is a legitimate case.
The guess that beats halving, and the distribution it depends on
Interpolation search estimates where a value should be instead of always looking in the middle, the way you open a phone book near the back for "Wilson". On the right data it is dramatically faster than binary search; on the wrong data it degrades to a linear scan, and both are worth measuring rather than accepting.
Things to try
- Watch a one-probe hit. Set Array Size to 30 and press Reset Array until the values look evenly spread, then set Search Target to a middling value and press Next Step once. The first probe often lands on or beside the answer.
- Compare against a midpoint split. Note where the first probe lands for a small target such as the second-smallest value. Interpolation goes straight to the left edge; binary search would still have started dead centre.
- Make it work hard. Set Search Target to a value near one extreme and press Auto-Run. Watch the probes cluster at that end — the algorithm homes in from the correct side immediately rather than converging symmetrically.
- Scale it up. Step through a search at Array Size 5, then at 30. The probe count barely moves. That flatness is log log n: it grows so slowly that at these sizes it looks like a constant.
Common mistakes
- Dividing by zero. When a[hi] == a[lo] — every remaining element is equal — the denominator is zero. Guard that case explicitly before computing the probe.
- Using it on non-uniform data. This is the real trap. Interpolation search is only a win when values are close to uniformly distributed. On skewed, clustered, or exponential data it is slower than binary search, and the failure is a quiet performance collapse rather than a crash.
- Overflow in the numerator. (target − a[lo]) × (hi − lo) multiplies two potentially large numbers. Use a wide enough type, or reorder to divide first.
- Skipping the bounds check. A computed position must still be clamped to [lo, hi]; with unsorted or corrupted input the formula can point outside the array entirely.
The short version
Interpolation search replaces binary search’s fixed midpoint with an estimate of where the value ought to live, and on uniformly distributed data that estimate is good enough to cut the cost from log n to log log n. The catch is that it is an assumption about the data, not a property of the algorithm: when the distribution is skewed the same formula degrades all the way to O(n). Use it when you know the distribution, and use binary search when you do not.
The safe hybrid
The practical answer, and what production code should do if interpolation is used at all: combine the two.
Use interpolation to choose the probe, and fall back to binary search if progress is too slow. That keeps the average-case speed-up and restores the O(log n) guarantee.
def hybrid_search(arr, target, max_probes=None):
lo, hi = 0, len(arr) - 1
if max_probes is None:
max_probes = 3 * max(1, (len(arr).bit_length())) # ~3 log n
probes = 0
while lo <= hi and arr[lo] <= target <= arr[hi]:
probes += 1
if probes > max_probes:
return binary_search(arr, target, lo, hi) # give up, be safe
if arr[lo] == arr[hi]:
return lo if arr[lo] == target else -1
pos = lo + (target - arr[lo]) * (hi - lo) // (arr[hi] - arr[lo])
if arr[pos] == target:
return pos
lo, hi = (pos + 1, hi) if arr[pos] < target else (lo, pos - 1)
return -1
That is the same pattern as introsort: use the fast method, detect the pathological case, and switch to the one with a guarantee. It is a good general design principle for algorithms whose average and worst cases diverge sharply.
| Algorithm | Probe position | Requires |
|---|
| Linear | Next element | Nothing |
| Binary | Midpoint | Sorted |
| Interpolation | Estimated from value | Sorted, numeric, uniform |
| Fibonacci | Fibonacci-ratio split | Sorted; addition only |
| Exponential | Double until overshoot, then binary | Sorted, unbounded or unknown size |
| Ternary | Two points, thirds | Unimodal functions |
Exponential search deserves a mention because it solves a real problem: searching an array of unknown or unbounded size. Probe indices 1, 2, 4, 8, … until the value at the probe exceeds the target, then binary search the last interval. O(log i) where i is the target's position, which is better than O(log n) when the target is near the front.
Fibonacci search splits by Fibonacci ratios and uses only addition and subtraction — no division. That mattered on hardware without a divide instruction, and it also touches fewer distinct cache lines than binary search on some access patterns.
Where the idea genuinely appears
Interpolation search itself is niche. The idea — using the distribution of the data to predict where something is — is not.
Database index lookups use histograms and statistics about value distribution to estimate where records lie, which informs query planning and page selection.
Learned index structures are a research direction that replaces the index with a model predicting a key's position — effectively interpolation search with a learned function instead of a linear one.
Interpolation in numerical methods. Root-finding by the secant method or the false-position method is interpolation search applied to continuous functions, and it converges considerably faster than bisection.
So the algorithm is a small instance of a broadly useful principle: if you know something about the distribution, use it.
Questions people ask
When is it faster than binary search? On large, uniformly distributed numeric arrays — roughly O(log log n) against O(log n).
What is its worst case? O(n), on skewed distributions such as exponentially spaced values.
Can it search strings? Not meaningfully — interpolation needs numeric keys to compute a position between two values.
Should I use it in production? Rarely. Binary search's guarantee and simpler arithmetic usually win. Use a hybrid if you do.
Does it need sorted data? Yes, like binary search — and it additionally assumes the values are roughly evenly spread.
What is exponential search for? Arrays of unknown size, or where the target is likely near the start: probe doubling positions, then binary search the final interval.
Recap in one screen
- Probe where the value should be, given the range's endpoints, rather than always at the midpoint.
- O(log log n) on uniformly distributed numeric data — about 4 probes for a million elements.
- O(n) worst case on skewed data, and it needs numeric keys and more arithmetic per probe.
- Binary search's guarantee usually wins; a probe-limited hybrid gets both.
- The underlying idea — exploit the known distribution — appears in database statistics and learned indexes.