In interpolation search, what breaks when the range's endpoint values a[lo] and a[hi] are equal?

## The fragment and the fault The canonical loop looks harmless: ``` while lo <= hi and key >= a[lo] and key <= a[hi]: pos = lo + ((key - a[lo]) * (hi - lo)) / (a[hi] - a[lo]) ... ``` The entry condition checks three things: the range is non-empty, and the key lies between the endpoint values. What it never checks is that the endpoint values *differ*. The formula divides by `a[hi] - a[lo]`, so when they are equal the division is by zero. ## Two ways to reach it, one of them on clean data **The plateau.** A run of identical values can swallow the whole surviving range. In a buffer of quantised readings where a sensor reported the same value for a long stretch, `a[lo]` and `a[hi]` can easily coincide while `hi - lo` is still large. The loop condition is satisfied — the key equals both endpoints — and the division blows up. **The single element.** This is the one people miss. The loop is written with `lo <= hi`, so it legitimately runs one final time with `lo == hi`. Then `a[lo]` and `a[hi]` are literally the same element, and the difference is zero *no matter how distinct the array's values are*. So an implementation of this fragment can fault on a perfectly uniform, duplicate-free array — precisely on the successful-lookup path, when the range narrows to the element holding the key. The bug is not exotic; it is on the happy path. A subtlety worth noticing: whether you get a crash, a silently wrong value, or something else depends entirely on how the surrounding arithmetic behaves on a zero divisor. Integer division by zero typically raises; floating-point division by zero typically yields an infinity or a not-a-number, which then converts to some arbitrary index and probes out of bounds or loops. "Sometimes it works" is the worst possible failure mode, and it is a realistic one here. ## The guards Two correct fixes, both placed *before* the division. **Resolve the range directly.** ``` if a[hi] == a[lo]: if key == a[lo]: return lo return NOT_FOUND ``` This is exact. If the endpoints are equal, every value between them is equal too (the range is sorted), so the range is a constant plateau: either the key is that constant — and any index in the range is a valid answer — or it is not present in the range at all. No probing required. **Fall back to a midpoint.** ``` if a[hi] == a[lo]: pos = lo + (hi - lo) / 2 else: pos = lo + ((key - a[lo]) * (hi - lo)) / (a[hi] - a[lo]) ``` This keeps the loop shape uniform and degrades gracefully into binary search's rule exactly where interpolation has nothing to say. It is slightly less direct on a plateau but composes well with a general hybrid that also caps consecutive bad estimates. ## The neighbouring boundary hazards While you are looking at this line, three more deserve a check. **Overflow.** `(key - a[lo]) * (hi - lo)` multiplies a value difference by an index difference. On a large array of large values that product can exceed a fixed-width integer's range, producing a negative or wrapped result and an out-of-bounds probe. Reorder, widen the accumulator, or compute the fraction in floating point before scaling. **Clamping.** Even without overflow, arithmetic truncation and rounding should not be trusted to keep `pos` inside `[lo, hi]`. A defensive clamp costs two comparisons and removes an entire class of out-of-bounds reads. **Progress.** Because the probe is not guaranteed to be strictly inside the range the way a midpoint is, an implementation must ensure each iteration actually moves `lo` or `hi`. Writing the updates as `lo = pos + 1` and `hi = pos - 1` — never `lo = pos` — is what makes termination safe. ## Why interviewers like this It separates people who have recited the formula from people who have run it. The formula is memorable and the guard is not, so the plateau question is a compact way to ask "did you ever implement this?" The strong answer names both triggers — the duplicate run and the single-element range — states the guard, and adds that a zero-denominator fault is a correctness bug, not the performance degradation that skewed data causes. Those are two independent failure modes of the same algorithm, and mixing them up is the giveaway.