1. One-Liner
Interpolation search estimates the next index proportionally between low and high using the target and endpoint values, instead of always picking the middle.
2. The Problem It Solves
On sorted numeric arrays where values are roughly evenly spread, jumping straight toward the likely position can beat binary search’s fixed halving—often O(log log n) average case vs O(log n).
3. The Core Idea
If keys look like a straight line from arr[lo] to arr[hi], the target’s rank should land in proportion along the index range—like predicting where 50 falls between 0 and 100 on a ruler.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | If target out of [arr[lo], arr[hi]] range, stop. |
| 2 | Compute pos = lo + (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]). |
| 3 | Compare arr[pos] with target; adjust lo or hi. |
| 4 | Repeat until found or interval invalid. |
| 5 | Guard division by zero when arr[lo] == arr[hi]. |
5. Dry Run Example
Array: [10, 20, 30, 40, 50], target: 40, start lo=0, hi=4.
| Step | lo | hi | pos | arr[pos] |
|---|---|---|---|---|
| 1 | 0 | 4 | 0 + (40-10)*4/40 = 3 | 40 → found |
Another: Array: [1,2,3,100], target: 2 — interpolation quickly moves toward the sparse gap; still needs careful bounds.
6. Key Properties
| Property | Detail |
|---|---|
| Best case | O(log log n) when distribution is uniform. |
| Worst case | Can degrade to O(n) if values cluster badly. |
| Requires | Sorted, numeric, random-access. |
7. Where It Is Used
| Company / domain | Use |
|---|---|
| Storage / DB | Approximate leaf location in evenly split key ranges. |
| Scientific | Lookup in gridded or sampled monotone tables. |
8. Interview Tips
Know when it fails (duplicates, skew). Compare to binary and exponential. Implement clamp pos to [lo+1, hi-1] in practice to avoid infinite loops.
9. Comparison with Other Algorithms
| Algorithm | Trade-off |
|---|---|
| Binary search | Always O(log n), no distribution assumption. |
| Interpolation | Faster average on uniform data; fragile if not. |
| Jump | Uses √n steps; different model. |
10. Complexity
| Average | Worst | |
|---|---|---|
| Time | O(log log n) (uniform) | O(n) |
| Space | O(1) | O(1) |
Implementation Example (PYTHON)
def interpolation_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi and target >= arr[lo] and target <= arr[hi]:
if lo == hi:
return lo if arr[lo] == target else -1
if arr[hi] == arr[lo]:
return lo if arr[lo] == target else -1
pos = lo + (target - arr[lo]) * (hi - lo) // (arr[hi] - arr[lo])
pos = max(lo, min(hi, pos))
if arr[pos] == target:
return pos
if arr[pos] < target:
lo = pos + 1
else:
hi = pos - 1
return -1