A Guide to Ternary Search for Unimodal Functions

Optimisation problems often ask for the input that produces the smallest or largest value of a function. When the function is unimodal, its values move consistently towards a single optimum and then consistently away from it. This shape allows ternary search to discard a substantial part of the search interval at every step, without checking every possible input.

The method is useful in algorithm competitions, numerical computing, simulation, and engineering. It is especially attractive when a function is expensive to evaluate but its domain is ordered. For readers exploring algorithms alongside Python and machine learning, the hello ML community offers related explanations of programming and problem-solving concepts.

Method	Main assumption	Search reduction	Typical use
Binary search	Monotonic predicate or sorted data	About half per step	Finding a boundary
Ternary search	Unimodal objective function	About one third per step	Continuous or discrete optimisation
Golden-section search	Unimodal continuous function	Reuses one function value	Efficient numerical optimisation
Grid search	No useful shape assumption	Fixed sampling pattern	Small or irregular domains

Understanding Unimodality

A function is unimodal over an interval if it has one dominant peak or one dominant valley. For a maximisation problem with peak at (x^*), values generally increase while (x < x^*), reach their maximum near (x^*), and decrease while (x > x^*). For minimisation, the pattern is reversed: values decrease towards the optimum and increase afterwards.

The word “single” needs care. A function may contain a flat plateau at its optimum rather than one unique point. Ternary search can still work when the optimum is an interval, provided the function remains non-decreasing before that interval and non-increasing after it for maximisation. Multiple local peaks break the assumption, because comparing two interior points may cause the algorithm to discard the interval containing the global optimum.

A simple example is the concave quadratic:

[ f(x) = -(x-4)^2 + 10 ]

Its maximum is at (x=4). Values rise as (x) approaches 4 from the left and fall after passing 4. A convex quadratic such as ((x-4)^2) has a single valley and can be handled by reversing the comparison used for maximisation.

This property appears in practical models. A retailer might model profit against a single price range, or an engineer might estimate performance against one tuning parameter. For instance, a Melbourne business could investigate whether a delivery fee has a peak profit point in Australian dollars before demand falls too sharply. The model must still be checked: real customer behaviour can create multiple peaks through discounts, seasonal events, or competitor pricing.

How the Search Narrows the Interval

Start with a closed interval ([left, right]). Divide it into three sections by calculating two interior points:

[ m_1 = left + \frac{right-left}{3} ]

[ m_2 = right - \frac{right-left}{3} ]

For a maximisation problem, evaluate (f(m_1)) and (f(m_2)). If (f(m_1) < f(m_2)), the function is improving as the interval moves towards the right, so the left third cannot contain the peak. Set (left = m_1). If (f(m_1) > f(m_2)), discard the right third by setting (right = m_2). When the values are equal, the safest update removes both outside thirds and keeps the middle interval.

For minimisation, reverse the relevant comparison. If (f(m_1) > f(m_2)), move the left boundary to (m_1), because the function is falling towards the right. If (f(m_1) < f(m_2)), move the right boundary to (m_2).

ternary_search(left, right, maximise):
    repeat until the interval is sufficiently small:
        first = left + (right - left) / 3
        second = right - (right - left) / 3

        if maximise:
            if f(first) < f(second):
                left = first
            else:
                right = second
        else:
            if f(first) > f(second):
                left = first
            else:
                right = second

    return the midpoint of left and right

The interval length is multiplied by roughly (2/3) at each iteration. After (k) iterations, its size is approximately ((2/3)^kL), where (L) is the original length. To reach precision (\varepsilon), the iteration count is (O(\log(L/\varepsilon))). Each iteration normally makes two function calls, so the number of calls is twice the iteration count, although later refinements can reuse values.

Continuous and Discrete Implementations

For a continuous domain, use a fixed number of iterations rather than waiting for exact equality between floating-point boundaries. Sixty to one hundred iterations is usually ample for ordinary double-precision calculations, but the appropriate number depends on the required accuracy and the size of the initial interval.

def ternary_maximise(function, left, right, iterations=80):
    for _ in range(iterations):
        first = left + (right - left) / 3.0
        second = right - (right - left) / 3.0

        if function(first) < function(second):
            left = first
        else:
            right = second

    position = (left + right) / 2.0
    return position, function(position)

This returns an approximate location and value of the maximum. If the function is costly, avoid evaluating it again at the end when the application can retain the best known value. Also consider numerical stability. Large values of (x), subtractive cancellation, noisy measurements, and functions with extremely flat peaks may make the final position less reliable than the objective value itself.

A discrete domain requires a different stopping rule. For an integer interval, repeatedly compare two integer points, then finish by directly checking the small remaining range. One implementation is:

def ternary_maximise_integer(function, left, right):
    while right - left > 3:
        first = left + (right - left) // 3
        second = right - (right - left) // 3

        if function(first) < function(second):
            left = first + 1
        else:
            right = second - 1

    best_x = left
    for x in range(left + 1, right + 1):
        if function(x) > function(best_x):
            best_x = x

    return best_x, function(best_x)

The + 1 and - 1 updates prevent the loop from getting stuck when the two interior points coincide or when only a few integers remain. This pattern is common in coding challenges; the problem-solving resources provide useful context for analysing boundary conditions and complexity.

Complexity and Algorithm Selection

If one function evaluation takes (O(1)), ternary search takes (O(\log n)) time over a discrete range of (n) values and uses (O(1)) extra space. More generally, if evaluating (f(x)) costs (T_f), the total work is (O(T_f\log(L/\varepsilon))) for a continuous interval. In many scientific applications, the function evaluation dominates the arithmetic used to choose the next interval.

Binary search is usually the better choice when the problem can be expressed as a monotonic yes-or-no question, such as “is this capacity sufficient?” Ternary search is designed for comparing objective values, not for locating a threshold. Golden-section search is often preferable for continuous optimisation because it reduces the interval using a ratio related to the golden ratio and reuses one of the previous function evaluations. That lowers the number of expensive calls.

A brute-force scan can still win when the integer range is tiny, the function is extremely cheap, or the unimodality assumption is uncertain. Randomised and derivative-based methods may be more appropriate for noisy, high-dimensional, or non-convex functions. In machine learning, for example, a one-dimensional line search may fit ternary search, but training a model with many parameters generally needs a different optimisation strategy. A useful contrast is the expectation-maximisation discussion, where the objective and parameter landscape have different algorithmic requirements.

Australian applications illustrate the distinction. A solar installer in Adelaide might optimise panel tilt over one continuous seasonal range if predicted output has a single peak. An online retailer serving Sydney and Brisbane could optimise a shipping price only if its profit curve is demonstrably single-peaked. If public-holiday demand, postcode bands, and competitor discounts create several peaks, a global scan or segmented search is safer.

Testing, Assumptions, and Practical Recommendations

The greatest risk is usually not an arithmetic error; it is applying ternary search to a function that is not unimodal. Plot sample values before trusting the result, especially when the function comes from measured data. For a discrete objective, inspect successive differences or simply sample a coarse grid. A function affected by random demand, sensor noise, or simulation variance may appear to have several peaks even when its expected value is smooth.

Test both maximisation and minimisation, narrow intervals, equal interior values, integer ranges with fewer than four candidates, and optima located at either boundary. Include realistic units in test cases: Australian dollars for pricing, kilometres for delivery distance, or minutes for travel time. If code is intended to run across Australia, keep the optimisation model separate from time-zone and daylight-saving logic; Sydney and Melbourne commonly follow daylight-saving changes while Brisbane does not.

Useful habits for a reliable implementation include:

• Verify unimodality with a plot, sample scan, or mathematical argument before searching.
• Decide whether the domain is continuous, integer-valued, or a finite set of permitted choices.
• Use fixed floating-point iterations and a direct final scan for small integer intervals.
• Handle equal midpoint values conservatively so a flat optimum is not discarded.
• Compare the answer with brute force on small random test cases during development.
• Record the required precision and units, especially for Australian-dollar prices or physical measurements.

For a contest problem, read the wording carefully: some statements guarantee a mountain-shaped or valley-shaped sequence, while others merely imply that an answer exists. In production software, document the assumption beside the function and monitor the shape of incoming data. Ternary search is elegant because it uses structure efficiently, but that efficiency is valid only when the structure has been established.