Why can't binary search find a unimodal cost curve's minimum, and what does ternary search do instead?

## The precondition, stated precisely Binary search does not really require a sorted array — it requires a **monotone predicate** over the domain: some test that is false everywhere up to a crossover point and true everywhere after it. One probe evaluates that predicate and eliminates one side. Sortedness is just the most familiar way to get monotonicity. A **unimodal** function has no such predicate for its optimum. Take the curve you get from tuning a single knob — total runtime of a batched job as a function of batch size. Tiny batches pay fixed per-batch overhead thousands of times, so runtime is high on the left. Huge batches spill working memory and thrash, so runtime is high on the right. Somewhere in the middle sits one minimum. Formally, for a minimum, unimodal means: there is a point `x*` such that `f` is strictly decreasing on `[lo, x*]` and strictly increasing on `[x*, hi]`. (The mirror definition — rise then fall — gives a maximum; the algorithm is the same with the comparison flipped.) Now ask what one probe buys you. You measure runtime at some batch size and get 40 seconds. Is the minimum to the left or the right? Unanswerable: 40 seconds occurs once on the falling side and once on the rising side, and a single value cannot distinguish them. There is no monotone predicate to split on, so binary search over the *values* has nothing to bite on. ## The two-probe rule Ternary search restores a decidable test by taking **two** interior probes instead of one. Split the current interval `[lo, hi]` into thirds: - `m1 = lo + (hi - lo) / 3` - `m2 = hi - (hi - lo) / 3`, so `lo < m1 < m2 < hi` Compare `f(m1)` against `f(m2)`: - If `f(m1) > f(m2)`, the minimum lies strictly right of `m1`. Set `lo = m1`. - If `f(m1) < f(m2)`, the minimum lies strictly left of `m2`. Set `hi = m2`. - If they are equal *and* the function is strictly unimodal, the minimum lies strictly between them, so both outer thirds can go. The elimination is a contradiction argument, not a heuristic. Suppose `f(m1) > f(m2)` but the minimum sat at or left of `m1`. Then the whole span from `m1` to `m2` lies on the rising side, which forces `f(m1) < f(m2)` — contradicting what you measured. So the assumption is impossible and the left third is safe to drop. ## What it costs Each step discards one third and **keeps two-thirds**, at the price of two evaluations. The name misleads people here: ternary search does not cut the interval to a third. After `k` steps the interval is `(2/3)^k` of its original width, so reaching a target precision takes about `log(range/eps) / log(1.5)` steps — roughly 1.7 steps per halving, at two evaluations each. It is still logarithmic in the range, with a worse constant than binary search. ## Terminating On a continuous domain you cannot land exactly on the optimum; you shrink until the interval is smaller than a tolerance, or simply run a fixed number of iterations chosen so that `(2/3)^k` times the starting width is below what you care about, and return the interval's midpoint. On an integer domain — batch sizes are integers — the probes eventually collide or stop moving, so the usual practice is to loop while the window holds more than about three candidates and then evaluate those directly. ## Where it actually applies Ternary search is not a container-search technique; it is an optimisation technique over a domain you can evaluate a cost at. That domain can be real-valued (a threshold, a ratio, a physical position) or integral (a batch size, a worker count, a chunk width). What it always needs is that the cost genuinely has **one** turning point over the interval you search. If the cost curve has two local minima, the two-probe comparison can eliminate the third containing the global one and you will confidently return the wrong knob value with no error signal at all. ## The common mistakes Three misreadings dominate. First, thinking ternary search finds a *value* the way binary search finds a key — it finds an **extremum's location**, and there is no target to match. Second, thinking it converges faster because "three beats two" — it keeps more of the interval per step, not less. Third, applying it to any curve that looks bumpy: unimodality is a precondition you must justify from the shape of the cost model, not something the algorithm checks for you.