A teammate proposes interpolation search over heavily skewed transaction amounts — how do you respond?

## What is actually being proposed The pitch is always the same shape: a bound comparison. "Binary search is log n, interpolation search is log log n, so on a large array the second is obviously better." The response is not to dispute the arithmetic — log log n really is dramatically smaller — but to attack the condition attached to it. That bound is an *expectation over a distribution*. Change the distribution and the algorithm does not degrade gracefully; it degrades to linear. ## Why this particular data is the wrong data Transaction amounts are heavy-tailed: an enormous mass of small values and a thin tail of very large ones. Sorted, such an array is almost entirely packed into the bottom sliver of its value range. Now run the probe rule. The endpoints of the full range are the smallest amount and the largest. The denominator `a[hi] - a[lo]` is set by that rare huge amount. A search for a typical small amount computes `(key - a[lo]) / (a[hi] - a[lo])` as a fraction near zero, so the probe lands at or beside `lo`. The comparison advances `lo` by one. The next round's endpoints are essentially unchanged, the fraction is still near zero, and the probe advances by one again. The recurrence has quietly changed from `T(m) = T(sqrt(m)) + O(1)` to `T(m) = T(m - 1) + O(1)`. The proposal that promised about four probes instead of twenty delivers something proportional to the array length — for the *most common* queries, since small amounts are the bulk of the traffic. That is the shape of the argument to make: not "there exists a bad case" but "the modal query is the bad case". ## The rubric: verified uniformity versus hoped-for uniformity The useful generalisation, and the thing worth saying out loud in an interview, is that the assumption must be *guaranteed by how the data is produced*, not observed once and assumed to persist. **Uniformity you can verify by construction:** - Timestamps emitted by a fixed-rate sampler — the value is a linear function of the index up to small jitter, by the design of the sampler. - Densely allocated sequential identifiers with few gaps — spacing is fixed by the allocator. - Quantised measurements taken on a regular schedule. In these cases the uniformity is a property of an upstream mechanism you control, and you can state the condition under which it would stop holding (the sampler changes rate; the allocator starts leaving large gaps). **Uniformity you merely hope for:** - Any user-supplied magnitude — amounts, quantities, scores, durations. - Anything with a natural heavy tail — sizes, counts, populations, latencies. - Anything whose distribution can shift without your code changing, which includes essentially all product data. The asymmetry is the point. Binary search's O(log n) is a property of the *algorithm*; interpolation search's O(log log n) is a property of the *data*, borrowed. When data ownership sits outside your team, you are underwriting a latency guarantee with someone else's input distribution — and it can change on a Tuesday with no deploy on your side. ## If the team still wants it There are legitimate ways to take a bounded version of the bet: 1. **Cap and fall back.** Count consecutive probes that failed to shrink the range by a meaningful factor; after a small constant, switch to plain midpoint probing for the rest of the search. This preserves an O(log n) ceiling while keeping most of the upside on data that behaves — the same hybrid instinct behind adaptive sorts that switch strategies when one is going badly. 2. **Guard the arithmetic.** Equal endpoint values must be handled before the division, the multiplication must not overflow a fixed-width integer, and the probe should be clamped into the range. 3. **Measure on production key distributions.** A synthetic benchmark of evenly spaced keys will reproduce the paper's numbers and tell you nothing. Replay real keys and look at the tail of the probe count, not the mean. 4. **Compare against the real alternative.** Often the honest comparison is not against binary search at all. If lookups are the bottleneck, the bigger win may be a different access structure entirely, and the search-variant debate is a distraction from that conversation. ## The organisational half of the answer There is also a cost that never appears in the bound: a hand-rolled search variant with subtle guards is code the team must maintain and that new joiners have not seen. A widely understood logarithmic search that everyone can read is worth several probes of theoretical advantage on a code path that is not the bottleneck. The right first question is usually "how much total latency is this search responsible for?" — and if the answer is "a fraction of a percent", the correct response to the proposal is that the change does not pay for its own risk, regardless of which bound wins on paper.