An improvement over Binary Search for instances where the values in a sorted array are uniformly distributed. It estimates the position of the target value rather than always checking the middle.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
{
"arr": "[10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]",
"target": 18,
"n": 15
}Overview
Interpolation Search improves on binary search when values are spread evenly. Instead of always probing the middle, it estimates where the target should be, in the same way you would open a phone book near the back to look for 'Williams'.
The estimate is pos = lo + ((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]), a straight-line interpolation between the two ends of the current range. On uniformly distributed data this lands very close to the target, giving O(log log n) probes on average.
In the default example the range is 10..47 and the target is 18. The first estimate is index 3 (value 16), just short of the target; the next estimate from the narrowed range lands exactly on index 4. Two probes instead of binary search's three or four.
Step by step
- Set
lo = 0andhi = n - 1. - While
lo <= hiand the target lies betweenarr[lo]andarr[hi], computeposwith the interpolation formula. - If
arr[pos]equals the target, returnpos. - If
arr[pos]is smaller, setlo = pos + 1; otherwise sethi = pos - 1. - If the loop ends, return -1.
Complexity
| Case | Cost | Why |
|---|---|---|
| Best case | O(1) | The first estimate is exact. |
| Average case | O(log log n) | For uniformly distributed keys. |
| Worst case | O(n) | Exponentially skewed data makes every estimate move by only one position. |
| Extra space | O(1) | Iterative implementation. |
When to use it
- Large sorted arrays of numbers that are close to uniformly distributed, such as sequential IDs with gaps or timestamps sampled at a steady rate.
- When each probe is expensive (for example a disk read), so fewer probes matter more than simple arithmetic.
Common mistakes
- Dividing by
arr[hi] - arr[lo]when they are equal causes division by zero; handle the all-equal range separately. - The range check
arr[lo] <= x <= arr[hi]is required, orposcan fall outside the array. - On skewed data it is slower than plain binary search; measure before choosing it.
A dry run is the best way to check your understanding of Interpolation Search: follow each row, predict the next one, and compare. The run below takes 11 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- 10,12,13,16,18,19,20,21,22,23,24,33,35,42,47
- Target
- 18
- Result
- return value = 4
| Step | Line | Array | What happens |
|---|---|---|---|
| 1 | 1 | [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] | target = 18, n = 15 |
| 3 | 3 | [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] | lo = 0, hi = 14, target = 18, condition = 0 <= 14 && 18 >= 10 && 18 <= 47 |
| 5 | 10 | [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] | pos = 3, condition = 16 == 18 |
| 6 | 13 | [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] | pos = 3, condition = 16 < 18 |
| 8 | 3 | [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] | lo = 4, hi = 14, target = 18, condition = 4 <= 14 && 18 >= 18 && 18 <= 47 |
| 10 | 10 | [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] | pos = 4, condition = 18 == 18 |
| 11 | 11 | [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] | return value = 4 |