An algorithm for searching in a sorted array that estimates the position of the target element based on the values at the current bounds, similar to how a human searches a dictionary.
Overview
Searching the way a person uses a phone book
Looking up “Zhang” in a phone book, nobody opens it at the exact middle. You open near the back, because you know where Z falls. Interpolation search formalises that: instead of probing the midpoint, it estimates the target’s position from its value relative to the values at the two ends.
If the low element is 10, the high element is 1000, and you are looking for 100, the target sits about 9% of the way through the range — so probe about 9% of the way into the array, not 50%.
Parameters
15
Visualization
Step: 0
Enter a target and click Step or Auto-Run.
Algorithm Insight
Predicts the location of the target mathematically:
3.If target is larger, low = pos + 1. If smaller, high = pos - 1.
Efficiency
Time (Avg)O(log log N)
Time (Worst)O(N)
Interpolation Search: A Practical Guide
Guess where the value should be rather than always splitting in the middle. On uniformly distributed data it finds a target in about log log n steps - but the wrong distribution turns it back into a linear scan.
The probe formula
The position estimate is a straight-line interpolation between the endpoints:
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:
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.
example_01.pyPython
def binary(a, target):
lo, hi, probes = 0, len(a) - 1, 0
while lo <= hi:
probes += 1
mid = (lo + hi) // 2
if a[mid] == target:
return probes
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return probes
def interpolation(a, target, cap=10 ** 6):
lo, hi, probes = 0, len(a) - 1, 0
while lo <= hi and a[lo] <= target <= a[hi] and probes < cap:
probes += 1
if a[hi] == a[lo]:
pos = lo
else:
# where the value SHOULD be if the data were evenly spread
pos = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])
if a[pos] == target:
return probes
if a[pos] < target:
lo = pos + 1
else:
hi = pos - 1
return probes
import math
import random
n = 100000
uniform = list(range(n)) # perfectly evenly spaced
rng = random.Random(9)
# uniformly distributed but NOT perfectly spaced -- the realistic case
spread = sorted(rng.sample(range(10 * n), n))
clustered = sorted(int(rng.random() ** 8 * n) for _ in range(n))
exponential = sorted(2 ** (i // 3) for i in range(n))
print("%-16s %14s %14s %12s" % ("data", "binary probes", "interp probes",
"log2(log2 n)"))
for name, data in (("evenly spaced", uniform), ("random uniform", spread),
("clustered", clustered), ("exponential", exponential)):
targets = [data[rng.randrange(n)] for _ in range(50)]
b = sum(binary(data, t) for t in targets) / 50
i = sum(interpolation(data, t) for t in targets) / 50
print("%-16s %14.1f %14.1f %12.1f" % (
name, b, i, math.log2(math.log2(n))))
# The first row is the ideal: values exactly one apart, so the formula
# computes the position rather than estimating it and lands on the target
# in a single probe. Real data is never that tidy, which is what the
# second row is for -- uniformly distributed but randomly spaced, where
# the count settles near log2(log2(n)), about 4. Binary search needs
# sixteen or seventeen on the same data.
#
# On the clustered data the guess is systematically wrong: most values sit
# near the bottom of the range, so the formula points near the bottom
# every time and the window shrinks by a little instead of by half.
#
# The exponential data is the worst case in a clean form. Each value is
# roughly double the last, so a linear interpolation between the endpoints
# is off by orders of magnitude on every probe.
#
# Binary search does not care -- its column barely moves, because halving
# is a fact about the INDEX range and makes no assumption about the
# values. That is the trade: interpolation search buys speed by assuming a
# distribution, and pays for the assumption when it is wrong.
print()
print("worst case if the guess is always off by one position:")
print(" interpolation: O(n) -- %d probes on %d items" % (n, n))
print(" binary: O(log n) -- %d probes on %d items" % (
int(math.log2(n)) + 1, n))
# In practice the safe version is a hybrid: interpolate, but if the window
# is not shrinking fast enough, fall back to bisection. That is exactly
# what numerical root-finders do with Brent's method, for the same reason
# -- keep the fast guess, keep the guaranteed bound.
Output
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.
The related search algorithms
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.
Run it in Python
The same list searched twice: once evenly spaced, where guessing the position beats halving it, and once with a single outlier, where the same code degenerates to a linear scan.
interpolation_search.pyPython 3
# Interpolation search: estimate WHERE the target should be, instead of
# always probing the middle. Needs sorted AND roughly uniform data.
def interpolation_search(a, target, label):
print(label)
lo, hi, step = 0, len(a) - 1, 0
while lo <= hi and a[lo] <= target <= a[hi]:
step += 1
if a[hi] == a[lo]: # flat span: no slope to follow
pos = lo
else:
fraction = (target - a[lo]) / (a[hi] - a[lo])
pos = lo + int(fraction * (hi - lo))
print(f" step {step:>2}: lo={lo:>2} hi={hi:>2} probe={pos:>2} a[probe]={a[pos]}")
if a[pos] == target:
return pos, step
if a[pos] < target:
lo = pos + 1
else:
hi = pos - 1
return -1, step
uniform = list(range(0, 200, 10)) # 0, 10, 20, ... perfectly even
i, steps = interpolation_search(uniform, 170, "uniform data, target 170")
print(f" -> index {i} in {steps} step(s)")
print()
skewed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 5000] # one huge outlier
i, steps = interpolation_search(skewed, 9, "skewed data, target 9")
print(f" -> index {i} in {steps} step(s)")
print()
print("Same code, same length, same sortedness. Only the spacing changed.")
Output
How the code works
while lo <= hi and a[lo] <= target <= a[hi]:The second half of the condition is an early exit binary search does not have: if the target is outside the current window's value range, no probe inside it can succeed.
fraction = (target - a[lo]) / (a[hi] - a[lo])How far along the window the target's value sits, between 0 and 1. Binary search always uses 0.5 here; this is the one line that makes the two algorithms different.
pos = lo + int(fraction * (hi - lo))Turns that value fraction into an index, on the assumption that value and position rise together at a steady rate. When they do, the probe lands on or beside the answer immediately.
if a[hi] == a[lo]: pos = loGuards a division by zero when every value in the window is equal. Reaching for a fraction of a zero-width value range is the crash this algorithm is famous for.
skewed = [1, 2, ..., 5000]The outlier drags a[hi] so high that the computed fraction is nearly zero every time, so the probe advances one index per step. Interpolation search is O(log log n) on uniform data and O(n) on data like this.
Change one thing
Change the uniform target to 0 and to 190. Both ends are found in a step or two, where binary search needs its full log n.
Replace uniform with [i * i for i in range(20)] — sorted, but quadratically spaced. Watch the probe consistently undershoot.
Set fraction = 0.5 unconditionally. You have just written binary search, and on the skewed list it beats the clever version.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Interpolation search improves on binary search by:
It interpolates a position from the value's distance between the endpoints, instead of always probing the middle. That one line is the whole difference.
The program runs it on [1,2,3,4,5,6,7,8,9,5000] looking for 9. Why does it take so many steps?
The computed fraction is nearly zero because 5000 dominates the value range, so each probe lands next to the previous one and the search degenerates to O(n).
Its O(log log n) figure assumes the data is:
Sortedness alone is not enough - the estimate is a straight-line guess, so it needs the values to rise at a roughly steady rate.
Cheat sheet
Interpolation Search
An algorithm for searching in a sorted array that estimates the position of the target element based on the values at the current bounds, similar to how a human searches a dictionary.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.