In ternary search for a minimum, why is discarding the left third safe when f(m1) is greater than f(m2)?
answer
- Name the loop invariant first
- Assume the opposite and look for a contradiction
- Where would the curve be rising?
- If the minimum sat left of m1...
- then f would climb from m1 to m2
basics
~20 sThe alternative is impossible: if the minimum sat at or left of m1, the curve would rise from m1 to m2, forcing f(m1) below f(m2) — the opposite of what was measured. So the minimum lies strictly right of m1.
solid answer
~40 sIt is a proof by contradiction on the unimodality assumption, not a heuristic guess. Strict unimodality for a minimum says the curve falls to a single point `x*` and rises after it. Assume `f(m1) > f(m2)` with `m1 < m2`, and suppose `x*` were at or left of `m1`. Then the whole span `[m1, m2]` lies on the rising side, so `f(m1) < f(m2)` — contradicting the measurement. Hence `x* > m1` and `[lo, m1]` cannot contain it. The mirror case is the same argument: `f(m1) < f(m2)` puts `x*` strictly left of `m2`. Note what the comparison does *not* prove — it never tells you the minimum is near the smaller probe, only which outer third is provably empty.
code
pseudocode · 10 lines// f is strictly unimodal on [lo, hi]: falls to one minimum, then rises
// invariant: the minimum always stays inside [lo, hi]
while hi - lo > eps:
m1 = lo + (hi - lo) / 3
m2 = hi - (hi - lo) / 3
if f(m1) > f(m2):
lo = m1 // minimum cannot lie in [lo, m1]
else:
hi = m2 // minimum cannot lie in [m2, hi]
return (lo + hi) / 2go deeper
Memorise the direction and be able to say it out loud: for a minimum, a larger value at the left probe means the minimum is to the right, so the left third goes. Getting the direction backwards is the most common slip.
Give the argument, not the rule. State the invariant, assume the minimum sits in the third you want to drop, and derive the contradiction from where the curve is rising or falling. Mention what equality between the probes buys you.
Show how you would review such a loop: name the invariant, check each branch against it, and point out that a swapped comparison fails silently rather than crashing. Explain why strict unimodality is load-bearing for the proof.
Own the verification story. Silent wrongness means the safeguard has to come from outside the loop — an assertion on the returned point, a coarse sanity sweep, or a cost model you can argue is single-turning-point before anyone ships the tuner.
## What is being claimed The loop keeps one invariant: **the minimum is always inside `[lo, hi]`**. Every step must preserve it, so each branch needs a proof that the part being thrown away is provably empty. That proof — not the arithmetic of thirds — is the whole content of ternary search. ## The setup Strict unimodality for a minimum: there is a point `x*` in `[lo, hi]` with `f` strictly decreasing on `[lo, x*]` and strictly increasing on `[x*, hi]`. "Strictly" matters and will come back later. The probes satisfy `lo < m1 < m2 < hi`. ## Case one: f(m1) > f(m2) Claim: `x* > m1`, so `[lo, m1]` can be dropped. Suppose not — suppose `x* <= m1`. Then both probes sit on the rising side, because `m1 >= x*` and `m2 > m1 >= x*`. On the rising side `f` is strictly increasing, and `m1 < m2`, so `f(m1) < f(m2)`. That contradicts the measured `f(m1) > f(m2)`. The supposition is impossible, so `x* > m1`, and setting `lo = m1` preserves the invariant. ## Case two: f(m1) < f(m2) Mirror image. Suppose `x* >= m2`. Then both probes sit on the falling side, so `f(m1) > f(m2)` — again contradicting the measurement. Hence `x* < m2` and setting `hi = m2` is safe. ## Case three: f(m1) == f(m2) Under *strict* unimodality, equality is the most informative outcome of all. If `x*` were at or left of `m1`, both probes would be on the rising side and the values would differ; if it were at or right of `m2`, both would be on the falling side and again differ. The only survivor is `m1 < x* < m2`, so **both** outer thirds can be discarded in one step. A single-branch implementation that writes `else: hi = m2` folds the equality case into case two, which is still correct — it just discards less than it could. ## What the comparison does not prove The frequent misreading is to treat the smaller probe as "closer to the minimum" and to keep a window centred on it. The comparison is strictly an **exclusion** statement about one outer third. It does not order `|m1 - x*|` against `|m2 - x*|`, and it certainly does not say the minimum is in the middle third — after `f(m1) > f(m2)` the minimum can be anywhere in `(m1, hi]`, including very close to `hi`. Everything the algorithm knows is captured by the interval; there is no extra proximity information hiding in the values. A second misreading is to conclude that a smaller value means a steeper descent or a nearer optimum. Two curves can produce identical probe values with their minima in very different places. Only the comparison's *sign* is used, never the magnitude of the gap. ## Why the interval is two-thirds, not one-third Each branch removes one of the three parts, so the surviving interval spans from a one-third point to an endpoint: two-thirds of the previous width. After `k` steps the width is `(2/3)^k` of the original. This is where the name misleads: "ternary" describes the *split into three*, not the *shrink factor*. Ternary search converges slower per step than binary search, and pays two evaluations per step rather than one. ## Where the argument breaks Every case above leaned on "strictly". If the curve has a flat run — a plateau where several inputs share the best-so-far value — the contradiction arguments collapse: two probes can both land on the same flat level while the true optimum sits outside the window you decide to keep. Strict unimodality is not a technicality in the definition; it is the load-bearing hypothesis of the proof, and the reason integer-domain cost curves with ties need a different treatment. ## Reading the loop as an invariant When an interviewer hands you a ternary-search fragment, the productive move is to name the invariant first ("the minimum stays in `[lo, hi]`"), then check each branch against it. A swapped comparison, `if f(m1) < f(m2): lo = m1`, breaks the invariant on the very first step against a curve whose minimum is on the left, and the loop converges confidently to the wrong endpoint — no crash, no assertion, just a bad answer. Boundary bugs here are silent, which is exactly why the elimination argument is what gets asked.
- If the two probe values come out equal, how much can you discard?Under strict unimodality, both outer thirds. Equality rules out the optimum being at or left of `m1` (both probes would then be on the rising side, giving different values) and at or right of `m2` (both on the falling side, again different). So it sits strictly between them, and you can set `lo = m1` and `hi = m2` in the same step. Folding equality into one branch is still correct, just less aggressive.
- Someone swaps the comparison to `if f(m1) < f(m2): lo = m1`. What do you observe?No crash and no error — the loop still terminates, and returns a confidently wrong answer. The swapped branch discards the third that contains the minimum, so the invariant is broken on the first step and the interval converges toward whichever endpoint the bad rule keeps chasing. Silent wrongness is the signature failure of this family; it is why the invariant, not the output, is what you check.
- Does the comparison tell you which probe is closer to the minimum?No. It is purely an exclusion statement about one outer third. After `f(m1) > f(m2)` the minimum lies somewhere in `(m1, hi]` — possibly right next to `m1`, possibly right at `hi`. Only the sign of the comparison is used, never the size of the gap, and no proximity information is carried between steps beyond the interval itself.
saying these in an interview costs you the question
- Says the minimum must be near the probe with the smaller value
- Claims the comparison proves the minimum is in the middle third
- Reasons from the size of the gap rather than its sign
- Cannot state the loop invariant being preserved
- Treats the discard rule as a convention rather than a proof
- Forgets that the argument needs strict, not merely weak, unimodality