Ternary Search — Finding Extrema in Unimodal Functions

Binary search is one of the most elegant and powerful algorithms in computer science. It transforms O(n) linear searches into O(log n) operations by repeatedly halving the search space. You've likely used it countless times—finding elements in sorted arrays, locating insertion points, or searching for boundary conditions.

But here's a critical insight that many developers miss: binary search has strict preconditions. When those preconditions aren't met, binary search doesn't just perform poorly—it can produce completely incorrect results or fail to find valid answers altogether.

Understanding when binary search doesn't apply is just as important as knowing how to implement it. This understanding opens the door to alternative algorithms designed for different problem structures, and ternary search is one of the most important among them.

Before exploring what binary search can't do, let's crystallize what it requires. Binary search operates on a deceptively simple principle: given a structured search space, eliminate half of the remaining candidates with each comparison. But this simple principle demands rigorous structural properties.

The Monotonicity Requirement

Binary search requires monotonicity in some form. The classic application is a sorted array where elements monotonically increase (or decrease). But more generally, binary search works whenever you can formulate your problem as finding a boundary in a sequence of boolean predicates:

• Let P(x) be a predicate that is false for all x < boundary and true for all x ≥ boundary
• Or equivalently, P(x) transitions from false to true exactly once

This is the essence of binary search: there must be a single transition point in your search space.

The Decision Property

At each step of binary search, you must be able to make a decisive choice about which half of the search space to eliminate. This decision must be:

1. Correct — Never eliminate the portion containing the answer
2. Substantive — Always eliminate at least one element (or a constant fraction)
3. Deterministic — Given the same state, always make the same choice

If you can look at a middle element and definitively say "the answer is in the left half" or "the answer is in the right half," binary search applies. If you sometimes can't make this determination—or if you must explore both halves—binary search breaks down.

Consider a seemingly straightforward problem: you're given an array of integers that first increases, then decreases—like a mountain profile. Your task is to find the peak (the maximum value). At first glance, this looks like a search problem. Can we use binary search?

Let's think carefully. In a mountain array:

• Elements to the left of the peak are ascending
• Elements to the right of the peak are descending
• The peak itself is greater than both its neighbors

The Monotonicity Violation

Here's where it gets interesting. A mountain array is not monotonic—it increases, then decreases. But there's a hidden monotonic property we can exploit:

• If arr[mid] < arr[mid + 1], the peak is to the right
• If arr[mid] > arr[mid + 1], the peak is at mid or to the left

This is a form of monotonicity! The predicate "is mid part of the descending region?" transitions from false to true exactly once. So binary search does work for finding the peak. Crisis averted—for this specific problem.

But What If We Want the Maximum Value Over a Continuous Domain?

The mountain peak problem worked because we had discrete elements and a hidden binary predicate. But consider a different scenario: you have a continuous function f(x) defined over the real interval [a, b]. The function first increases, reaches a maximum, then decreases. You want to find x* that maximizes f(x).

Now there's no discrete array. There's no "next element" to compare against. The function value at a point tells you the height at that point, but not directly whether you're left or right of the maximum. This is where binary search genuinely breaks down.

Let's formalize the class of problems where binary search fails but ternary search excels.

The Unimodal Function Optimization Problem

Given a function f: [a, b] → ℝ that is:

1. Unimodal — Has exactly one local maximum (or minimum) in [a, b]
2. Continuous — No jumps or gaps
3. Single-peaked — Strictly increasing before the peak, strictly decreasing after

Find x* such that f(x*) is maximized.

Why Binary Search Fails

With binary search, we'd pick a midpoint m and evaluate f(m). But what does f(m) tell us?

• If f(m) = 10, is the maximum to the left or right of m?
• We can't tell! The value 10 could be on the ascending side (maximum is to the right) or the descending side (maximum is to the left) or at the maximum.

Binary search requires comparing against something—a target value, a boundary, a neighbor. With a single function evaluation at a single point, we have no basis for eliminating either half.

The Two-Point Comparison Insight

The key insight is that we need two evaluation points to determine direction. If we query f(m1) and f(m2) where m1 < m2, then:

• If f(m1) < f(m2): The peak must be to the right of m1 (we're still ascending at m1)
• If f(m1) > f(m2): The peak must be to the left of m2 (we're already descending at m2)
• If f(m1) = f(m2): The peak is between m1 and m2 (both points are equidistant from peak in value)

This gives us a decision rule—but it can only eliminate roughly one-third of the search space per iteration, not half. This is the fundamental trade-off that defines ternary search: we trade logarithmic base for applicability to a broader class of problems.

Understanding when binary search doesn't apply isn't just academic—these situations arise constantly in practice. Here are real-world optimization problems that demand ternary search (or similar techniques):

1. Machine Learning Hyperparameter Tuning

You're training a neural network and sweeping the learning rate from 0.0001 to 1.0. Too low and training is slow. Too high and training diverges. The validation accuracy as a function of learning rate is unimodal—there's a sweet spot, and performance drops on either side.

2. Economics — Optimal Pricing

The profit function for a product often looks like an inverted parabola: price too low means high volume but low margins; price too high means low volume. Somewhere in between is the revenue-maximizing price.

3. Physics — Projectile Range

The distance a projectile travels as a function of launch angle (with fixed velocity) is unimodal. At 0° or 90°, the projectile goes nowhere. Maximum range occurs at 45° (in a vacuum). You might need to find this optimal angle numerically.

4. Competitive Programming — Resource Allocation

Many problems involve allocating resources where too little or too much allocation is suboptimal. For instance, minimizing the time to complete tasks when adding workers helps initially but eventually causes coordination overhead.

Let's build geometric intuition for why ternary search works where binary search fails.

Binary Search Geometry

In binary search, the search space is a line segment. Each comparison divides this segment in half. The answer lies somewhere on the segment, and each query tells you definitively which half contains it.

[====|====]      After querying midpoint:
[====]           "Answer is in left half"
     [====]      or "Answer is in right half"

Ternary Search Geometry

In ternary search, we also have a line segment, but we divide it into thirds using two points. Each pair of queries tells us which third to eliminate:

[===|===|===]    After querying two points:
[===|===]        "Eliminate right third" if f(m1) > f(m2)
    [===|===]    "Eliminate left third" if f(m1) < f(m2)

The key difference: binary search gets definitive information from one query; ternary search needs two queries to get definitive information. But ternary search can handle problems where single-point queries are insufficient.

Why Thirds and Not Halves?

A natural question: if we need two query points, why not divide into halves with points at 1/3 and 2/3? Actually, there's flexibility here! The key constraint is:

1. We need two distinct points m1 < m2 to compare
2. The points should be positioned so that each comparison eliminates a substantial portion
3. We want to minimize the number of function evaluations

Positioning m1 at 1/3 and m2 at 2/3 gives us:

• If eliminating left third: new interval is 2/3 the size
• If eliminating right third: new interval is 2/3 the size

This gives us a logarithmic convergence rate with base 3/2, which corresponds to O(log n) complexity but with a larger constant factor than binary search.

The Golden Section Alternative

Interestingly, there's an optimization called golden section search that places points using the golden ratio (≈ 0.618). This allows reusing one of the function evaluations in the next iteration, reducing the amortized cost from 2 evaluations per iteration to just over 1. We'll explore this in a later page.

Let's compare approaches on a concrete problem to solidify understanding.

Problem: Find the x-value that maximizes f(x) = -(x - 5)² + 25 over the interval [0, 10].

This is an inverted parabola with maximum at x = 5 where f(5) = 25.

We've explored the boundaries of binary search and the class of problems that require a different approach. Here are the key takeaways:

What's Next:

Now that we understand when binary search fails, we'll dive deep into the structure that makes ternary search possible: unimodal functions. The next page explores what makes a function unimodal, how to recognize this property in problems, and why unimodality is both necessary and sufficient for ternary search to work correctly.