Interpolation Search
Estimates the position of the target via linear interpolation, almost like laying a ruler.
- Comparisons 0
- Result still searching
- compare
- swap
- sorted
Pseudocode
1 lo = 0; hi = n - 1
2 while lo <= hi and a[lo] <= target <= a[hi]
3 pos = lo + ((target - a[lo]) * (hi - lo)) / (a[hi] - a[lo])
4 if a[pos] == target: return pos
5 if a[pos] < target: lo = pos + 1
6 else: hi = pos - 1
7 return -1
Step log
How it works, runtime and memory
Interpolation Search is an extension of binary search that does not just take the middle, but estimates the index of the target via linear interpolation. From the current range a[lo] to a[hi] and the target value: pos = lo + ((target − a[lo]) · (hi − lo)) / (a[hi] − a[lo]). On uniformly distributed data this lands very close to the hit and the range shrinks faster than mere halving. Runtime on uniform data is O(log log n) on average, almost unbeatable. In the worst case (strongly non-uniform values like geometrically growing numbers) it degrades to O(n). Requires a sorted array with uniform values; on non-numeric or skewed data binary search is the better choice.
Complexity
- Best case
O(1) - Average case
O(log log n) - Worst case
O(n) - Extra space
O(1)
When to use it
Optimal on large sorted data sets with uniformly distributed values, e.g. numeric indices or ID columns without gaps. Often risky on real data because the O(log log n) guarantee can flip to O(n); a classic technique in competitive programming.