On an integer domain, what does a plateau where f(m1) equals f(m2) break in ternary search?

## The hypothesis that was doing the work The discard rule for a minimum reads: if `f(m1) > f(m2)`, drop `[lo, m1]`. Its proof supposes the optimum is at or left of `m1`, concludes both probes are then on the rising side, and derives `f(m1) < f(m2)` — a contradiction. That derivation used **strict** increase. Replace "strictly increasing after the optimum" with "non-decreasing" and the derivation only yields `f(m1) <= f(m2)`, which no longer contradicts anything when the values are equal. So the failure is not a coding slip. It is the algorithm's precondition quietly not holding. ## A concrete integer failure Tuning an integer knob — say the number of records per batch, mapped to candidates 0 through 5 — you measure costs `5, 5, 5, 5, 5, 3`. This sequence is weakly unimodal (non-increasing, then trivially non-decreasing) with its minimum at candidate 5. Run the standard step with `lo = 0`, `hi = 5`: - `m1 = 0 + (5-0)/3 = 1`, `m2 = 5 - (5-0)/3 = 4` - `f(1) = 5`, `f(4) = 5` — equal A "strictly unimodal" implementation now discards **both** outer parts, leaving `[1, 4]`. A single-branch implementation takes the `else` and sets `hi = 4`, leaving `[0, 4]`. Both have thrown away candidate 5, the only optimum. The loop finishes, returns a plausible-looking knob value, and reports nothing wrong. ## Why no logarithmic method saves you The instinct is to switch to bisecting on the forward difference `f(k+1) - f(k)`, since that is the standard equivalence for a unimodal optimum. But across the flat run the difference is exactly zero — the predicate "difference >= 0" is neither reliably false before nor reliably true after, and a probe inside the plateau gives no direction. The deeper statement is an adversary argument. If a plateau of unknown length may sit at any level, then after any `o(n)` probes an adversary still has freedom to place the optimum in an unprobed region consistent with everything measured so far. Searching for an optimum hidden behind arbitrary flats is therefore linear in the worst case; no amount of cleverness in the probe placement changes that. This is the honest answer to "can't you just handle the tie specially?" — you cannot, in general. ## What actually fixes it Three families of fix, in the order you should reach for them: 1. **Establish strictness from the cost model.** Often the flats are an artefact of rounding rather than the real curve — costs quantised to whole milliseconds, or a measurement resolution coarser than the differences you care about. Measuring more precisely, or in a unit where ties are essentially impossible, restores the precondition you needed all along. 2. **Break ties by a secondary key.** If the primary cost genuinely ties, compare `(cost, knob)` lexicographically so no two candidates are equal. This makes the function strictly unimodal *by construction*, though only if the tie-break direction is consistent with the shape you want — it moves the answer to one edge of the plateau, which must be an acceptable answer. 3. **Bound the flats, or sweep.** If plateaus are short and their maximum length is known, a hybrid works: search logarithmically until the window is small, then scan. If they are unbounded, a coarse sweep followed by a local search over a region you have argued is strictly unimodal is the honest design. ## The integer termination trap next door Even with a strictly unimodal integer curve, the loop needs a different stopping rule from the continuous case. On reals you shrink until the width is under a tolerance, or run a fixed iteration count sized so that `(2/3)^k` times the starting width is small enough. On integers, `(hi - lo)/3` eventually rounds to zero, so `m1` can equal `lo` or `m1` can equal `m2` — and a branch that assigns `lo = m1` then makes no progress, looping forever. The standard remedy is to loop only while the window holds more than about three candidates and then evaluate those directly, taking the best. That is a cheap, correct ending and it also absorbs the last off-by-one worries about which endpoint is inclusive. ## What the interviewer is testing Not whether you can recite the discard rule, but whether you notice that its proof carries a hypothesis and can say what happens when the hypothesis fails. The signature of this whole family — ternary, golden-section, slope bisection — is **silent wrongness**: no exception, no assertion, no infinite loop, just a confident, incorrect knob value shipped to production. Candidates who name that, and who put a check outside the loop rather than inside it, are the ones who have run this against real measured data.