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
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
More options
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 |
Scroll the table sideways for the rest of the columns.
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, so 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.
Implementation
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.