Does ternary search need a differentiable function?

No. The relevant requirement is the unimodal shape and reliable comparisons, not availability of derivatives.

Is it always faster than binary search?

No. They commonly solve different problems, and evaluation cost matters; a derivative-sign or other monotone predicate may support a different search.

Can the optimum be at an endpoint?

Yes, for an appropriately monotone special case; the interval updates must retain that boundary and the implementation should evaluate the final candidates appropriately.

AI Glossary / Mathematics and optimization / Intermediate

Ternary search

Definition

Ternary search is an interval-reduction method for finding the minimum or maximum of a one-dimensional unimodal function. In its standard continuous form, it evaluates two interior points that divide the current interval into thirds. Their function values identify a portion that can be discarded while retaining an optimum, provided the required shape and comparison assumptions hold.

What it means

For minimization, imagine a function that strictly decreases toward its minimum and strictly increases afterward. Comparing two points then tells you which direction cannot contain the bottom. Ternary search uses function values rather than derivatives. This entry concerns optimization over a unimodal interval; the name can also appear in discussions of three-way lookup in sorted data. A function with several valleys does not meet the assumption merely because one valley looks promising in a plot.

How it works

Start with an interval [a, b] containing a minimizer. Set m1 = a + (b − a)/3 and m2 = b − (b − a)/3. If f(m1) < f(m2), replace b with m2. If f(m1) > f(m2), replace a with m1. For a strictly decreasing-then-increasing function, equality allows retaining [m1, m2]. Repeat until the interval is sufficiently narrow. Maximization reverses the comparisons. For integer inputs, use suitable integer probe positions and finish by checking every remaining candidate once the range is small; otherwise rounding can prevent progress or skip the answer.

Three practical examples

A deterministic cost model with a proven single valley can be searched for its best setting without calculating a derivative.
A geometry exercise can minimize a one-dimensional distance expression over a bounded interval after establishing the necessary shape.
A discrete scheduling model can compare allowable integer settings when its objective is known to decrease and then increase, with an exhaustive check of the final few settings.

Think of it this way

Think of finding the lowest point along a valley floor by comparing elevations at two marked locations. If the profile has one bottom and rises consistently away from it, the comparison rules out one side. The analogy fails when the landscape contains multiple valleys, hidden plateaus or measurement noise that reverses a comparison. Ternary search requires evidence for its shape assumption, not simply confidence that the terrain is smooth.

Worked example

Minimize f(x) = (x − 2)² + 1 over [0, 9]. The first probes are m1 = 3 and m2 = 6, with values 2 and 17. Because 2 < 17, retain [0, 6]. The next probes are 2 and 4, with values 1 and 5, so retain [0, 4]. The next probes are 4/3 and 8/3. Both values equal 13/9. The function has a strict single valley, so retain [4/3, 8/3]. The true minimizer x = 2 remains inside every interval. The midpoint of this last interval happens to equal it, but that convenient symmetry is not guaranteed in other problems. In the ordinary unequal-value step, interval width falls to two-thirds of its previous value. Starting with width W, after k such steps the width is W(2/3)^k; equality reductions can be even stronger. Stopping at width at most ε gives a midpoint within ε/2 of an enclosed minimizer. That is a location-error statement, not automatically an ε/2 bound on objective-value error.

Illustrative case study

In a fictional project, Juniper Packaging studies a simplified, deterministic formula for setup time as a function of one adjustable setting. An analyst proves that the formula has one minimum within the permitted interval, applies ternary search and checks the returned neighborhood directly. Before using the result operationally, the team compares the formula with observed behavior. The case illustrates optimization of a declared model; it does not claim that real production measurements are noise-free or that the selected setting delivers invented savings.

Common misconceptions and mistakes

Ternary search does not normally retain just one of three equal parts: an unequal comparison retains two-thirds of the interval. It is not a general global optimizer for multimodal functions. Smoothness alone does not establish unimodality. Equality handling also deserves care: under only weak monotonicity, a flat shoulder away from the optimum can produce equal probe values without bracketing the minimum between them. Floating-point rounding and noisy evaluations can imitate equality or reverse the comparison. A sampled graph can suggest a shape but cannot prove it throughout an unsampled interval.

Business use

Before adopting the method, define the variable, feasible interval and deterministic objective. Establish the required unimodal shape analytically or choose a method that tolerates weaker assumptions. Select a stopping rule in the variable's units and account for the cost of evaluating the function. Golden-section search can reuse an earlier evaluation and may be preferable when each evaluation is expensive. Record the final bracket as well as the chosen point. If observations are noisy, use an approach designed for that uncertainty rather than treating unreliable comparisons as exact instructions to discard regions.

Check your understanding

If f(m1) < f(m2) while minimizing a strictly unimodal function, should the algorithm discard the left third?

Answer: No. It discards the right third beyond m2 and retains [a, m2]. Reversing that rule can remove the minimizer.

Related terms

Learn next

repeat the worked search for (x − 2.3)² + 1 and keep the final bracket instead of expecting an exact midpoint. Then construct a function with two valleys and see why the elimination argument fails. Compare function-evaluation counts with golden-section search on the same valid unimodal example.

Golden-section search

Sources

Sources: University of Waterloo, CS 240E Tutorial 6, https://student.cs.uwaterloo.ca/~cs240e/s25/tutorials/t06/t06.pdf ; Alex Li, Ternary and Golden Section Search, author-maintained algorithm implementation and explanation, https://algorithms.alexli.ca/ternary-and-golden-section-search/ . The quadratic trace, width calculation and fictional packaging example are original. The strict-shape qualification is retained explicitly for equality handling.

Previous: Terminology model Next: Ternary search tree