What is Interpolation Search?
Learn how interpolation search estimates a target's position for O(log log n) average search, and its worst case on skewed data.
Expected Interview Answer
Interpolation search finds a target in a sorted, uniformly distributed numeric array by estimating the target's likely position using linear interpolation of its value, rather than always checking the midpoint like binary search — giving O(log log n) average time on uniform data but degrading to O(n) worst case on skewed distributions.
Instead of `mid = (lo + hi) // 2`, interpolation search computes `pos = lo + (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo])`, which estimates where the target should sit assuming values are roughly evenly spaced between arr[lo] and arr[hi] — like guessing a name's position in a phone book by how alphabetically close it is to the ends, not just splitting the book in half. If arr[pos] is less than the target, search continues in [pos+1, hi]; if greater, in [lo, pos-1]. On uniformly distributed data this converges far faster than binary search's fixed midpoint approach, achieving O(log log n) average comparisons. But on skewed or clustered data — e.g. mostly small values with one huge outlier — the formula's estimate can be badly wrong repeatedly, degrading to linear O(n) worst case, which is why it is used far less often than binary search in practice despite the better average case.
- O(log log n) average time on uniformly distributed sorted data
- Converges much faster than binary search when data is evenly spaced
- Uses value information, not just position, to guess the next probe
- Natural fit for numeric datasets like sorted sensor readings or ID ranges
AI Mentor Explanation
Looking up a player's career strike rate in a table sorted by strike rate, you would not open exactly to the middle page every time — if you're hunting for a strike rate of 145 and the table ranges from 60 to 200, you would flip roughly three-quarters of the way in, since 145 is proportionally close to the high end. This is interpolation search: it estimates position using the actual value, not just splitting the range in half like binary search would. It works beautifully when strike rates are evenly spread across the table, but if most players cluster around 80-90 with one freak outlier at 200, the value-based guess gets thrown off and you end up flipping almost page by page, degrading toward a linear scan.
Step-by-Step Explanation
Step 1
Check bounds and equal values
If lo > hi or arr[lo] == arr[hi], fall back to a direct check to avoid division by zero.
Step 2
Estimate the probe position
pos = lo + (target - arr[lo]) * (hi - lo) // (arr[hi] - arr[lo]), using linear interpolation of the value.
Step 3
Compare and narrow
If arr[pos] equals target, return it; if less, search [pos+1, hi]; if greater, search [lo, pos-1].
Step 4
Repeat or fall back
Continue interpolating on the narrowed range; on adversarial/skewed data this can approach O(n) comparisons.
What Interviewer Expects
- Correctly derive the interpolation formula and explain its intuition
- State O(log log n) average case on uniform data and O(n) worst case on skewed data
- Compare directly against binary search — same precondition (sorted) plus a uniformity assumption
- Mention numeric-only applicability, unlike binary search which works on any ordered type
Common Mistakes
- Forgetting to guard against arr[hi] == arr[lo], causing a division by zero
- Assuming interpolation search always beats binary search regardless of data distribution
- Applying it to non-numeric or non-uniformly-distributed data expecting log log n performance
- Confusing the formula direction — probing too far in the wrong direction relative to target value
Best Answer (HR Friendly)
“Interpolation search is like flipping to roughly where you expect a word to be in a phone book based on the letter, instead of always opening to the exact middle like binary search. It's much faster than binary search — close to O(log log n) — when values are evenly spread out, but it can degrade to a slow linear scan if the data is clustered or skewed.”
Code Example
def interpolation_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi and arr[lo] <= target <= arr[hi]:
if arr[hi] == arr[lo]:
return lo if arr[lo] == target else -1
pos = lo + (target - arr[lo]) * (hi - lo) // (arr[hi] - arr[lo])
if arr[pos] == target:
return pos
elif arr[pos] < target:
lo = pos + 1
else:
hi = pos - 1
return -1Follow-up Questions
- Why does interpolation search require the data to be roughly uniformly distributed?
- How would you prevent the O(n) worst case on skewed data in a production system?
- How does the interpolation formula differ conceptually from binary search's midpoint formula?
- Can interpolation search be applied to non-numeric sorted data, like strings?
MCQ Practice
1. What is the average-case time complexity of interpolation search on uniformly distributed data?
On uniformly distributed sorted data, interpolation search converges in O(log log n) average comparisons, faster than binary search.
2. What is the worst-case time complexity of interpolation search?
On skewed or clustered data, the interpolation estimate can repeatedly be wrong, degrading to O(n), a linear scan.
3. What must be guarded against in the interpolation formula?
If arr[hi] equals arr[lo], the formula divides by zero, so this case must be checked and handled separately.
Flash Cards
What does interpolation search use to estimate the probe position? — Linear interpolation of the target value relative to arr[lo] and arr[hi], not a fixed midpoint.
What is the average-case complexity on uniform data? — O(log log n), faster than binary search's O(log n).
What is the worst-case complexity, and when does it occur? — O(n), on skewed or non-uniformly distributed data.
What must be true of the data for interpolation search to apply? — It must be sorted and numeric, ideally roughly uniformly distributed.