What is Ternary Search?
Learn how ternary search finds the peak of a unimodal function, its unimodality requirement, and how to explain it in interviews.
Expected Interview Answer
Ternary search finds the extremum (minimum or maximum) of a strictly unimodal function by evaluating the function at two interior points that split the range into thirds, then discarding whichever third cannot contain the extremum, running in O(log₃ n) evaluations — it does not find a target value, it finds a peak or valley.
Given a range [lo, hi] and a function that strictly increases then strictly decreases (or vice versa), ternary search picks m1 and m2 at roughly one-third and two-thirds of the range. If f(m1) < f(m2), the maximum cannot lie in [lo, m1], so lo moves to m1; if f(m1) > f(m2), the maximum cannot lie in [m2, hi], so hi moves to m2. Each iteration shrinks the range by two-thirds instead of one-half, but because it needs two function evaluations per iteration instead of one, it is actually less efficient in practice than binary-search-on-the-answer variants like golden-section search or gradient-based methods when the function is differentiable. It strictly requires unimodality — if the function has multiple local peaks, ternary search can converge to the wrong one.
- Finds a maximum or minimum without needing derivatives
- Works on any strictly unimodal function over a continuous or discrete range
- Simple to implement with two function evaluations per step
- Useful when the objective function is a black box (e.g. simulation output)
AI Mentor Explanation
A bowling coach is tuning run-up length to maximize ball speed, knowing that speed increases with run-up length up to a point then decreases as the bowler tires before release — a single peak. Instead of testing every run-up length, the coach tests two candidate lengths splitting the range into thirds and compares ball speed at each; the slower of the two rules out the third of the range beyond it. Repeating this shrinks the search range by two-thirds each round until the peak run-up length is found. This only works because ball speed truly rises then falls once — if it wiggled up and down twice, the coach could lock onto the wrong peak.
Step-by-Step Explanation
Step 1
Confirm unimodality
Verify the function strictly increases then strictly decreases (or the reverse) over the search range.
Step 2
Pick two interior points
Compute m1 and m2 splitting [lo, hi] into three roughly equal parts.
Step 3
Compare and discard a third
Evaluate f(m1) and f(m2); the comparison tells you which outer third cannot contain the extremum, so move lo or hi.
Step 4
Repeat until converged
Continue narrowing until hi - lo is below a tolerance (continuous) or the range is trivially small (discrete).
What Interviewer Expects
- State the unimodality precondition explicitly
- Correctly explain which third gets discarded based on the f(m1) vs f(m2) comparison
- Give the complexity as O(log₃ n) evaluations, noting two evaluations per round
- Distinguish this from binary search: finds an extremum, not a target value
Common Mistakes
- Applying ternary search to a non-unimodal or noisy function and getting a wrong extremum
- Confusing ternary search with searching for a value (that is binary search)
- Getting the discard direction backwards when comparing f(m1) and f(m2)
- Not handling discrete domains correctly, where m1 == m2 can cause infinite loops
Best Answer (HR Friendly)
“Ternary search finds the peak or valley of a function that only rises then falls once, by testing two points that split the range into thirds and throwing away whichever third can't contain the extremum. It is different from binary search, which looks for a specific value — ternary search is about finding the best point on a curve.”
Code Example
def ternary_search_max(f, lo, hi, iterations=100):
for _ in range(iterations):
m1 = lo + (hi - lo) / 3
m2 = hi - (hi - lo) / 3
if f(m1) < f(m2):
lo = m1
else:
hi = m2
return (lo + hi) / 2
# Example: f(x) = -(x - 3) ** 2 + 10 peaks at x = 3
peak_x = ternary_search_max(lambda x: -(x - 3) ** 2 + 10, 0, 10)Follow-up Questions
- What happens if you apply ternary search to a function with two local maxima?
- How would you adapt ternary search to work on a discrete integer array?
- How does ternary search complexity compare to binary search complexity?
- When would golden-section search be preferred over ternary search?
MCQ Practice
1. What precondition must hold for ternary search to correctly find the maximum?
Ternary search only works correctly on strictly unimodal functions — strictly increasing then strictly decreasing (or vice versa).
2. How many function evaluations does each round of ternary search require?
Each round evaluates the function at two interior points, m1 and m2, to decide which third to discard.
3. What does ternary search find, as opposed to binary search?
Binary search locates a target value in sorted data; ternary search locates the peak or valley of a unimodal function.
Flash Cards
What kind of function does ternary search require? — A strictly unimodal function — rises then falls, or falls then rises, exactly once.
How many points does ternary search evaluate per round? — Two interior points, splitting the range into thirds.
What does ternary search output? — The location of the maximum or minimum of the function, not a target value.
Why can two evaluations per round make ternary search less efficient than expected? — It does more work per shrink step than binary search, despite shrinking by two-thirds instead of one-half.