SearchingAlgorithmaka trisection, unimodal search

Ternary Search

Find the extremum of a unimodal function by discarding one third of the range per step.

▶ Visualize Pattern: Binary Search Practice (1)

Progress

Overview

Ternary search finds the maximum (or minimum) of a unimodal function — one that strictly increases then strictly decreases (or vice versa). It probes two interior points m1 < m2, compares f(m1) and f(m2), and discards the outer third that cannot contain the peak.

It is most useful on continuous domains (real-valued parameters) and on integer domains where the function is unimodal but not sorted, so Binary Search on values does not apply directly. On a sorted array, ternary search finds a target too, but it makes more comparisons per step than binary search and is never faster.

unimodalO(log n)optimizationcontinuous

Intuition

A mental model before the formal terms.

You are walking a single hill in fog and want the summit. Send two scouts, one a third of the way and one two thirds of the way across. If the first scout stands higher than the second, the summit cannot be in the last third past the second scout — cut it off. Repeat until the scouts stand almost on top of each other.

How it works

Maintain [lo, hi] known to contain the extremum.
Compute m1 = lo + (hi - lo) / 3 and m2 = hi - (hi - lo) / 3.
For a maximum: if f(m1) < f(m2), the peak is right of m1, so lo = m1 (or m1 + 1 for integers). Otherwise hi = m2 (or m2 - 1).
On reals, stop after a fixed number of iterations (e.g. 100–200) or when hi - lo < eps. On integers, stop when hi - lo <= 2 and check the remaining points directly.

Why it works

Unimodality means: left of the peak f is strictly increasing, right of it strictly decreasing. If f(m1) < f(m2), then m1 is on the increasing side (both points cannot be on the decreasing side, since there f(m1) > f(m2)), so the peak is at or right of m1.

Each step keeps 2/3 of the range, so the range shrinks by (2/3)^k after k steps — O(log n) steps with a larger constant than binary search (log base 3/2 vs log base 2).

Recognition

How to tell a problem wants this.

The problem asks to minimize/maximize a function of one parameter and the function is convex/concave or "increases then decreases".
Real-valued answers with a tolerance ("answer within 10^-6"), such as choosing a point on a line minimizing a max-distance.
You cannot compute a derivative or the domain is discrete, but the objective is unimodal.

“sorted array” → Binary Search “merge k sorted” → Divide and Conquer

Interactive visualization

Play, step, change the input. ← → and space work too.

Array | target — Numbers, then a pipe, then the target — e.g. "1, 4, 9, 16 | 9"

↑lo

↑hi

1/5Search for 23 in the sorted range [0, 9]. Ternary search probes two points per iteration and keeps one of three thirds.

Being compared with targetTarget foundEliminated

PseudocodeLearn Ternary Search →

1lo = 0, hi = n - 1
2while lo <= hi:
3  m1 = lo + (hi - lo) // 3; m2 = hi - (hi - lo) // 3
4  if a[m1] == target: return m1
5  if a[m2] == target: return m2
6  if target < a[m1]: hi = m1 - 1
7  elif target > a[m2]: lo = m2 + 1
8  else: lo = m1 + 1, hi = m2 - 1
9return -1

Variables

lo0

hi9

target23

Complexity

best O(log n)

avg O(log n)

worst O(log n)

space O(1)

Speed

Pseudocode

1lo, hi = domain bounds
2repeat until hi - lo is tiny:
3  m1 = lo + (hi - lo) / 3
4  m2 = hi - (hi - lo) / 3
5  if f(m1) < f(m2): lo = m1
6  else: hi = m2
7return (lo + hi) / 2

Implementations

1from typing import Callable, Sequence
2 
3 
41 · Discrete form: find the peak index of a strictly unimodal sequence
5def ternary_search_peak(a: Sequence[int]) -> int:
6    lo, hi = 0, len(a) - 1
7    while hi - lo > 2:
8        m1 = lo + (hi - lo) // 3
9        m2 = hi - (hi - lo) // 3
10        if a[m1] < a[m2]:
11            lo = m1 + 1  # peak is strictly right of m1
12        else:
13            hi = m2 - 1  # peak is at or left of m2
142 · Finish the tiny window by brute force, which avoids the tie traps
15    best = lo
16    for i in range(lo + 1, hi + 1):
17        if a[i] > a[best]:
18            best = i
19    return best
20 
21 
223 · Continuous form: maximise a unimodal f over [lo, hi] to a tolerance
23def ternary_search_max(lo: float, hi: float, f: Callable[[float], float], eps: float = 1e-9) -> float:
24    for _ in range(200):
25        if hi - lo <= eps:
26            break
27        m1 = lo + (hi - lo) / 3
28        m2 = hi - (hi - lo) / 3
29        if f(m1) < f(m2):
30            lo = m1
31        else:
32            hi = m2
33    return (lo + hi) / 2
34 
35 
364 · Binary search on the slope does the same job with one probe per step
37def peak_by_binary_search(a: Sequence[int]) -> int:
38    lo, hi = 0, len(a) - 1
39    while lo < hi:
40        mid = (lo + hi) // 2
41        if a[mid] < a[mid + 1]:
42            lo = mid + 1  # still climbing
43        else:
44            hi = mid  # at or past the peak
45    return lo

Walkthrough

(hi - lo) // 3 uses floor division to get the one-third offset, keeping both probes integral.
for i in range(lo + 1, hi + 1) walks the final window inclusively — hi + 1 because range is half-open.
The continuous version writes the iteration cap as for _ in range(200) with an internal break, which reads more naturally in Python than a compound while condition.
peak_by_binary_search is the one to reach for on lists: one comparison per step against a[mid + 1], half the probes of the ternary form.
Python floats are C doubles, so 1e-9 is a reasonable tolerance and (lo + hi) / 2 returns a float even for integer inputs.

Complexity (this implementation)

time O(log_{3/2} n) iterations, 2 calls to f each · space O(1)

Python-level function calls are expensive, so on the continuous form the f calls dominate everything else by a wide margin.

Language notes

/ is always float division and // is floor division; the discrete search needs // and the continuous one needs /, and mixing them is silent.
scipy.optimize.minimize_scalar with method="bounded" is the production answer for continuous unimodal optimisation and converges far faster.
max(range(len(a)), key=a.__getitem__) finds the peak in O(n) and is often the honest choice for lists small enough that log n does not matter.
math.isclose is the right float comparison for convergence tests; == on floats is almost never what you want.

Common mistakes in this language

Using / instead of // for the probe offsets, which produces float indices and raises TypeError on the list access.
Running the discrete loop down to hi - lo > 0, which oscillates on adjacent indices instead of terminating.
Applying it to a list with equal adjacent values, violating strict unimodality and getting a wrong index with no error.

Language differences that matter here

Integer division: Python needs // (and / silently yields floats), C++ / on ints truncates, and JS/TS have no integer division at all, so Math.floor is mandatory.
Passing the objective function: C++ pays an indirect call through std::function (or inlines it via a template parameter), while JS/TS/Python pass closures with a real call per probe.
Float precision is identical across all four (IEEE-754 double), so the same eps and the same 200-iteration cap behave the same everywhere.
Library support for continuous optimisation exists only in the Python (scipy.optimize) and C++ (Boost) ecosystems; JS/TS have neither, which is why the hand-rolled loop is the whole answer there.

Complexity

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(1)

Two function evaluations per step; about log_{1.5}(n) ≈ 1.7·log₂(n) steps. On reals: O(log((hi-lo)/eps)).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Optimizing a unimodal (convex or concave) function of a single real or integer parameter.
Geometry problems: closest point on a segment, minimizing maximum distance, best angle.
When the objective is expensive to evaluate but unimodal, and there is no closed form for its extremum.

Avoid it when

Searching for a target value in a sorted array — Binary Search uses fewer comparisons.
Functions with plateaus (equal values around the peak): ternary search may discard the wrong third; use binary search on the sign of f(x+1) - f(x) instead.
Multimodal functions — it converges to some local extremum, not necessarily the global one.

Alternatives

Binary Search Linear Search

Common mistakes

Applying it to a function that is monotonic or has flat regions, where the f(m1) < f(m2) test does not identify the correct side.
On integer domains, using lo = m1 / hi = m2 without ±1 — the loop may never shrink when hi - lo is small.
Using a fixed epsilon on very large ranges where floating-point spacing exceeds the epsilon, causing an infinite loop; iterate a fixed count instead.
Confusing minimum vs maximum and flipping the comparison the wrong way.

Interview patterns

Minimize the maximum distance from a point on a line to a set of points (the max of convex functions is convex).
Choose a real-valued time t minimizing distance between two moving objects.
Replace with binary search on f(mid) < f(mid+1) for integer unimodal functions — fewer evaluations and plateau-safe.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Where does O(n log n) come from?Beginner
Average case versus worst caseIntermediate

Mock interviews

Minimum Size Subarray SumIntermediate
Kth Largest Element in an ArrayIntermediate
Search in Rotated Sorted ArrayIntermediate

Example problems

Koko Eating Bananasmedium

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related