How Interpolation Search Works
Interpolation search estimates the target's position from its value, the way you open a phone book near S for Smith. Nearly instant on evenly spread data, linear when the spread is skewed.
- Ruled out
- Still possible
- Checked now
- Found
Step 1 of 3
Looking for 158 in 16 sorted values, from 4 to 196.
Counters
- Steps
- 0
- Result
- -
- Still possible
- 16
- of 16
- Worst case
- 16
- steps for this size
Settings
Two to 64 numbers. Sorted ascending before the search runs.
Interpolation search
- 1
while a[lo] <= target <= a[hi]: - 2
// guess where the value should sit - 3
pos = lo + (target - a[lo]) - 4
* (hi - lo) / (a[hi] - a[lo]) - 5
if a[pos] == target: return pos - 6
if a[pos] < target: lo = pos + 1 - 7
else: hi = pos - 1 - 8
return NOT_FOUND
The same array, every algorithm
Probes on the values above, cheapest first. One probe is one value actually looked at.
- Interpolation1
- Ternary3
- Binary4
- Jump5
- Exponential8
- Linear13
How the six compare
| Algorithm | Best | Average | Worst | Needs a sorted array |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | No |
| Binary | O(1) | O(log n) | O(log n) | Yes |
| Ternary | O(1) | O(log n) | O(log n) | Yes |
| Jump | O(1) | O(√n) | O(√n) | Yes |
| Exponential | O(1) | O(log n) | O(log n) | Yes |
| Interpolation | O(1) | O(log log n)* | O(n) | Yes |
Interpolation search only reaches that average when the gaps between the values are even.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(1) | O(log log n) | O(n) | O(1) |
The O(log log n) average holds only for uniformly distributed values. Clustered data degrades it to a linear scan, which is worse than binary search's guarantee.
How interpolation search works
Instead of probing the middle, interpolation search assumes values are spread evenly and computes where the target ought to sit: a value near the low end of the range gets probed near the low end of the array. On uniform data this lands close enough that the number of probes grows as log log n — effectively three or four probes for a million elements. On skewed data the estimate is repeatedly wrong in the same direction and the range shrinks by one element at a time.
- Take the low and high ends of the range and the values there.
- Estimate the position by linear interpolation: how far along the value range the target sits, applied to the index range.
- Probe that index. Equal means done; smaller means search above it, larger means below.
- Repeat until the range is empty or the target falls outside the range's value bounds — in which case it cannot be present.
Implementation
The same algorithm the visualiser is running, written to be read.
def interpolation_search(values, target):
low, high = 0, len(values) - 1
while low <= high and values[low] <= target <= values[high]:
if values[low] == values[high]:
return low if values[low] == target else -1
# Where the value "should" be, if values are evenly spread.
span = values[high] - values[low]
guess = low + (high - low) * (target - values[low]) // span
if values[guess] == target:
return guess
if values[guess] < target:
low = guess + 1
else:
high = guess - 1
return -1When to use it
- Use it on large, uniformly distributed, sorted numeric data — sensor readings, timestamps at a steady rate, dense sequential ids.
- Use it as a first probe and then fall back to binary search, which is what interpolation-binary hybrids do to keep the guarantee.
- Avoid it on skewed or clustered data, and on anything an adversary controls: the worst case is a full scan.
Check yourself
If the animation made sense, these should too.
Why can interpolation search degrade to O(n)?
Because its estimate assumes values are spread evenly. On clustered data the guess is repeatedly wrong in the same direction, so the range shrinks by a constant number of elements per probe instead of a fraction - a linear scan with extra arithmetic.
What has to be true of the data for the O(log log n) average to hold?
The values must be roughly uniformly distributed, and numeric enough to interpolate between. Dense sequential ids, timestamps at a steady rate and sensor readings qualify; anything skewed, or anything an adversary chooses, does not.