How does interpolation search choose its next probe index, and what must the data satisfy?
answer
- Binary search knows only order; this knows values
- Ask where the key ought to sit
- Two ratios: value fraction equals index fraction
- Subtraction and division, not just comparison
- Estimate affects probe count, never correctness
basics
~20 sInterpolation search guesses the probe index by linearly interpolating the sought key between the two endpoint values, instead of always taking the midpoint. It needs sorted, randomly accessible keys you can do arithmetic on, and it only pays off when values are spaced near-uniformly.
solid answer
~40 sBinary search probes the middle index because ordering is all it knows. Interpolation search assumes the values themselves are informative, so it probes where the key *should* be: `pos = lo + (key - a[lo]) * (hi - lo) / (a[hi] - a[lo])`. If the key sits 90% of the way between the endpoint values, it probes about 90% of the way along the index range. That demands more than binary search does: keys must be sorted, randomly accessible, and support subtraction and division (not just `<`), and the key must lie inside `[a[lo], a[hi]]` or the estimate is meaningless. The payoff only materialises when spacing is roughly uniform; the estimate is a hypothesis about the data, not a property of the algorithm.
go deeper
Be ready to write down the probe formula and say in one sentence what it estimates: where the key falls in the value range, mapped onto the index range. Also state the requirements: sorted, random access, arithmetic keys.
Explain why binary search cannot do this — it only has comparisons — and that interpolation buys speed with a distribution assumption. Note the extra per-probe arithmetic and the multiplication that can overflow fixed-width integers.
Show you can name real data where the assumption genuinely holds, such as fixed-rate sampled timestamps or densely allocated identifiers, and separate that from data where uniformity is merely hoped for.
Own the framing that this technique trades a guarantee for an expectation. Be able to say when a team should not take that trade at all, and why a rarely-used search variant carries a maintenance cost of its own.
## The one idea Binary search treats a sorted array as an ordered sequence and nothing more. It can ask "is this element less than my key?" and nothing else, so the only defensible probe is the middle: whatever the answer, half the range disappears. Interpolation search adds one assumption — that the *values* carry positional information — and spends it on a smarter guess. ## The probe rule Working on a sorted range `a[lo..hi]` and looking for `key`: ``` pos = lo + (key - a[lo]) * (hi - lo) / (a[hi] - a[lo]) ``` Read it as two ratios set equal. `(key - a[lo]) / (a[hi] - a[lo])` is how far along the *value* range the key sits — a fraction between 0 and 1. `(pos - lo) / (hi - lo)` is how far along the *index* range the probe sits. Interpolation search asserts the two fractions are the same, which is exactly the claim that values grow linearly with index. If a range holds the readings 1000 through 2000 across 100 slots and you want 1900, the formula lands you near slot 90, not slot 50. After probing, the loop behaves exactly like binary search: hit and return; probed value too small, move `lo` past it; too large, move `hi` below it. Only the choice of probe differs. ## What the data must satisfy 1. **Sorted.** Same as binary search — without order, neither the comparison nor the interpolation means anything. 2. **Random access.** The probe index is computed, not walked to, so index lookup must be cheap. A structure you can only traverse link by link defeats the whole point. 3. **Arithmetic on keys.** This is the extra requirement. Binary search needs only a total order — it can search over anything comparable. Interpolation search subtracts keys and divides by a key difference, so keys must be numeric or embeddable in numbers. Ordered-but-not-arithmetic keys (arbitrary tokens with a comparison rule) can only be interpolated by first mapping them to numbers, and that mapping's quality becomes the estimate's quality. 4. **The key inside the endpoint values.** Standard formulations guard the loop with `key >= a[lo] and key <= a[hi]`, which both terminates early for absent keys outside the range and keeps the computed fraction in `[0, 1]`. 5. **Near-uniform spacing — for speed only, never for correctness.** This is the point worth being precise about. A bad estimate does not produce a wrong answer; the probe is still followed by a real comparison and the range still shrinks monotonically. A bad estimate costs *probes*. Correctness rests on sortedness; performance rests on the distribution. ## What it costs per probe A midpoint is an addition and a shift. An interpolated probe is a subtraction, a multiplication, and a division — and the multiplication `(key - a[lo]) * (hi - lo)` is the classic place a fixed-width integer overflows on large ranges with large values. So each probe is meaningfully more expensive than binary search's. On small arrays that already sit in fast cache, interpolation search can lose on wall-clock even while winning on probe count, which is the standard reason it stays a curiosity rather than a default. ## Where it actually shines The honest use case is data whose spacing is fixed by construction rather than hoped for: timestamps from a fixed-rate sampler, densely allocated sequential identifiers, quantised measurements taken on a regular schedule. In a buffer of readings taken every 10 milliseconds, the timestamp *is* a linear function of the index up to a little jitter, and the first probe typically lands within a step or two of the answer. ## The misconception to avoid "It is binary search with a better midpoint, so it is strictly better" is the wrong summary. It is binary search with a *bet* substituted for the midpoint. When the bet is right, probe counts drop dramatically; when the data is skewed, the same rule steers the probe to one end again and again and the search degenerates. The rule is the same either way — what changes is the data it was aimed at.
- Can interpolation search be used on keys that are ordered but not numeric?Only by first mapping them onto numbers, because the formula subtracts and divides keys. A common trick is to treat a fixed-length prefix of an ordered token as a base-N number. That works, but the search is then only as uniform as the mapping — and text-like data is famously clumpy, so the estimate is usually poor.
- Roughly how many probes would it take on a million perfectly uniform keys, versus binary search?Binary search needs about 20 probes, since log2 of a million is roughly 20. Interpolation search on near-uniform data expects about log log n — around four or five probes. That gap is the entire attraction. It evaporates the moment the uniformity assumption fails, so quote it as an expected figure, never a guarantee.
- Does a poor estimate ever make the search return a wrong result?No. Every probe is followed by an actual comparison, and the range is narrowed only on the basis of that comparison, so the invariant that the key lies in the current range is preserved regardless of where the probe landed. A poor estimate costs iterations, not correctness — assuming the guard against a zero denominator is present.
Hunting for the 90-kilometre marker on a 100-kilometre road, you drive most of the way rather than stopping at the halfway point — provided the markers really are evenly spaced.
saying these in an interview costs you the question
- Calls it binary search with a better midpoint, strictly faster
- Thinks a bad estimate can return a wrong index
- Forgets it needs arithmetic on keys, not just ordering
- Believes it works on sequentially traversed structures
- Omits the sortedness requirement because values are used