Ternary Search Visualization for Coding Interviews
Unimodal-function peak finding with two probes per step.
Concept
Ternary search is the tool you reach for when binary search does not apply — when the answer is not the minimum index satisfying a monotonic predicate but the maximum of a unimodal function. Unimodal means the function strictly increases to some peak and then strictly decreases (or strictly decreases then increases, for finding a minimum). Ternary search works by splitting the interval into thirds with two probe points and eliminating one third per step based on which probe is higher. Its log-base-1.5 step count is slightly worse than binary search's log2, but it solves a fundamentally different shape of problem: optimizing a smooth concave or convex function over an interval. You will see ternary search in physics simulations, geometric optimization, hyperparameter tuning, and convex optimization problems where derivatives are unavailable or noisy.
How it works
Given an interval [lo, hi] and a unimodal function f, pick two interior points m1 = lo + (hi - lo) / 3 and m2 = hi - (hi - lo) / 3. Evaluate f(m1) and f(m2). Because f has a single peak, comparing these values reveals which side the peak cannot be on. If f(m1) < f(m2), the peak is to the right of m1, so set lo = m1. Otherwise the peak is to the left of m2, so set hi = m2. Repeat until the interval is smaller than some epsilon (for doubles) or until hi - lo <= 2 (for integers). At termination the peak lies within the final tiny window — report either endpoint or the best-seen sample. The invariant is that after each iteration the peak is still within [lo, hi], which holds because unimodality guarantees one of the two thirds cannot contain the peak. For noisy or non-smooth functions ternary search breaks down because the sampled ordering no longer reflects which side contains the true maximum, which is why it is reserved for mathematically unimodal objectives.
Implementation
import java.util.function.DoubleUnaryOperator;
public final class TernarySearch {
private static final double EPS = 1e-9;
private static final int MAX_ITERS = 300;
private TernarySearch() {}
public static double ternarySearchMax(DoubleUnaryOperator f, double lo, double hi) {
if (lo > hi) throw new IllegalArgumentException("lo must be <= hi");
for (int i = 0; i < MAX_ITERS && hi - lo > EPS; i++) {
double m1 = lo + (hi - lo) / 3.0;
double m2 = hi - (hi - lo) / 3.0;
double f1 = f.applyAsDouble(m1);
double f2 = f.applyAsDouble(m2);
if (f1 < f2) lo = m1;
else hi = m2;
}
return (lo + hi) / 2.0;
}
public static int ternarySearchMaxInt(java.util.function.IntUnaryOperator f, int lo, int hi) {
while (hi - lo > 2) {
int m1 = lo + (hi - lo) / 3;
int m2 = hi - (hi - lo) / 3;
if (f.applyAsInt(m1) < f.applyAsInt(m2)) lo = m1;
else hi = m2;
}
int best = lo, bestVal = f.applyAsInt(lo);
for (int i = lo + 1; i <= hi; i++) {
int v = f.applyAsInt(i);
if (v > bestVal) { bestVal = v; best = i; }
}
return best;
}
}
Complexity
- Time (doubles):
O(log((hi - lo) / eps)) - Time (ints):
O(log n) - Space:
O(1) - Requires:
Strict unimodality
Common pitfalls
- Applying ternary search to a non-unimodal function — it silently returns a wrong local peak.
- Using == on doubles for the termination check; use hi - lo > eps instead.
- Integer version with only two midpoints can cycle when hi - lo <= 2 — finish with linear scan.
- Floating-point functions with flat regions break the strict inequality assumption.
- Forgetting to cap MAX_ITERS — some epsilon / range combos never converge numerically.
Key design decisions & trade-offs
- Ternary vs golden-section search — Chosen: Golden section when evaluations are expensive. Golden section reuses one probe each step; ternary evaluates twice per iteration.
- Ternary vs gradient ascent — Chosen: Ternary when derivative is unavailable. No gradient needed, but only for 1D unimodal; gradients scale to high dimensions.
- Float vs int variant — Chosen: Int version ends with linear scan. Avoids infinite loops on small intervals where integer midpoints collide.
Practice problems
Interview follow-ups
- Implement golden-section search and compare sample counts.
- Use ternary search to find the minimum of a convex function by negating f.
- Build a 2D ternary search by nesting two 1D searches — note the unimodality caveat.
- Apply ternary search to 'minimum radius to cover all points' problems.
Why it matters
Ternary Search is a core part of the Searching toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".