Why does ternary search cost more function evaluations than binary search on the slope sign?

## The arithmetic nobody does Count **evaluations of the cost function**, not iterations. Iterations are free; evaluations are what you pay for, especially when one evaluation means running a job at a candidate batch size and timing it. Ternary search: each step keeps `2/3` of the interval and spends `2` evaluations. Steps needed to halve the interval: `ln 2 / ln 1.5` = `0.693 / 0.405` ≈ `1.71`. At two evaluations each, that is about **3.4 evaluations per halving**. Bisecting on the slope sign: each step keeps `1/2` and spends one slope probe. That is **1 evaluation per halving** if the slope is directly available, or **2** if you form it from a finite difference — two cost measurements a small step apart, or on an integer knob the pair `f(k)` and `f(k+1)`. So the ratio is between 1.7x and 3.4x in favour of slope bisection. Both remain `Theta(log(range/precision))` evaluations: this is a **constant factor, not a complexity class**. Anyone who says ternary search is "asymptotically worse" has overstated it, and anyone who says the difference does not matter has never paid for an evaluation that takes twenty minutes. ## Why the slope is a monotone predicate This is the conceptual half of the answer. Strict unimodality with a minimum at `x*` says the curve falls before `x*` and rises after. In slope terms: the slope is negative on `[lo, x*)` and positive on `(x*, hi]`. The predicate "slope >= 0 here" is therefore **false, false, ..., false, true, true, ..., true** across the interval — a single crossover. That is precisely the structure plain binary search consumes, and the crossover point is the minimum. So a unimodal optimisation search is not a different algorithm family at all; it is ordinary bisection applied to the derivative rather than to the values. On a discrete knob the same trick uses the forward difference `f(k+1) - f(k)`, which is negative below the optimum and positive above it under strict unimodality. ## Where the misconception comes from Two confusions compound. The first is the name: "ternary" suggests a three-way cut, so people write `log3` and conclude it beats `log2`. The interval is cut *into* three parts but only one is removed, so the surviving fraction is `2/3` and the effective base is `1.5` — worse per step than binary search, not better. The second is counting steps instead of probes: even at equal shrink rates, two evaluations per step would double the bill. ## The refinement worth naming Golden-section search fixes the wasteful half of ternary search. Place the probes at the golden ratio points rather than the thirds, and after each discard **one of the two probes is still interior to the new interval at exactly the right position**, so it can be reused: one *new* evaluation per step, with the interval shrinking by a factor of about `0.618`. That is `ln 2 / ln(1/0.618)` ≈ `1.44` steps per halving at one new evaluation each — about **1.44 evaluations per halving**, comfortably better than ternary search's 3.4 and competitive with a finite-difference bisection. Knowing this is the usual signal that a candidate has thought about the cost model rather than memorised a template. ## When ternary search is still the right call The accounting is not a verdict against it. Slope bisection needs a slope you can trust. Reasons you may not have one: - The cost is only available as a measurement, and two nearby measurements differ by less than the measurement noise — the finite difference is then dominated by noise and the predicate flips randomly near the optimum. - The domain is coarse: adjacent integer knob values may not be evaluable independently, or `f(k+1)` may be as expensive as any other probe with no locality benefit. - The curve is not smooth, so a local difference reflects a kink rather than the global trend, while two well-separated probes still compare meaningfully. Ternary and golden-section searches only ever compare two *separated* values, which makes them robust to exactly the local wobble that ruins a finite difference. That robustness — not the shrink rate — is the honest argument for using them. ## How to present this in an interview Lead with the correction (`2/3`, not `1/3`), give the per-halving evaluation counts on both sides, name that both are logarithmic so the difference is a constant, then say when you would still choose the more expensive method. The failure mode to avoid is arguing rate without arguing cost per step: an algorithm that halves the interval using ten probes loses to one that keeps two-thirds using one.