Seven of the site's other eleven Searching entries solve the same
problem — find a target value, whether that requires the array to be sorted first (six of them
do) or not (Linear Search doesn't). An eighth, Saddleback Search, solves the same find-a-target-value
problem too, just over a matrix instead of an array. Two more are different-question entries in
their own right: Quickselect
finds a given rank rather than a target value, and Binary Search on Answer doesn't search an
array at all, only the space of candidate answers to a feasibility check. Ternary search solves
yet another one: find the
peak of a unimodal sequence, one that strictly rises to a single
maximum and then strictly falls, without evaluating every point. There's no "target" to compare
against, only the shape of the values themselves. Instead of one midpoint, it picks two — m1
and m2, splitting the current range into thirds — and compares f(m1)
against f(m2). Because the sequence is unimodal, whichever side is still climbing
toward the other must contain the peak, so the range can be narrowed by a third every step, the
same divide-and-discard shape as binary search, aimed at a different question. This site's twelfth
Searching entry, Golden-Section Search,
answers this exact same peak-finding question, not a different one — see its own page for how
splitting at the golden ratio instead of thirds lets it reuse one of the two probes every
iteration, instead of always paying for two fresh ones.
The array represents a unimodal sequence's values, not sorted keys — index is the input, the number in each cell is the output. peak near center and peak near edge both use a 31-element tent-shaped sequence; step through either one and watch how many iterations it takes to corner the peak. You can also edit the array by hand — see Pitfalls for what happens if what you type isn't actually unimodal.
Each step keeps the invariant binary search keeps too — if the peak exists, it's between
lo and hi — just narrowed by a third instead of a half. Given
m1 = lo + (hi-lo)/3 and m2 = hi - (hi-lo)/3:
if f(m1) < f(m2):
# peak can't be left of m1 — a unimodal sequence rising into m1
# would need f(m1) to be the larger of the two, not the smaller
lo = m1
else:
# symmetric argument: peak can't be right of m2
hi = m2
Note that the range shrinks to [m1, hi] or [lo, m2] — keeping
m1 and m2 themselves as candidates, not excluding them the way binary
search's mid ± 1 excludes its midpoint once checked. That's deliberate: binary search
can exclude mid because it already knows the exact answer isn't there (a direct
equality check). Ternary search never gets that certainty from a single comparison — f(m1) <
f(m2) only rules out one *side*, and either point can still turn out to be the peak itself,
so both stay in play until the range is too small to split further.
function ternaryMax(arr) {
let lo = 0, hi = arr.length - 1;
while (hi - lo > 2) {
const third = Math.floor((hi - lo) / 3);
const m1 = lo + third, m2 = hi - third;
if (arr[m1] < arr[m2]) lo = m1;
else hi = m2;
}
// range is down to at most 3 candidates — finish with a direct scan
let best = lo;
for (let i = lo; i <= hi; i++) {
if (arr[i] > arr[best]) best = i;
}
return best;
}
It silently gives up the wrong answer on a non-unimodal input — checked, not just asserted. Ternary search never verifies its own precondition; it just trusts the sequence has exactly one peak. Feed it this 31-element sequence with two humps, a taller one at index 1 (value 150) and a shorter one at index 18 (value 140):
144, 150, 144, 138, 132, 126, 120, 114, 108, 102, 96,
98, 104, 110, 116, 122, 128, 134, 140, 134, 128, 122,
116, 110, 104, 98, 92, 86, 80, 74, 68
The true maximum is 150 at index 1. Run the reference implementation above on
it and it returns index 18, value 140 — a real local peak, but not the global one
— in the same 8 iterations the well-behaved presets above take. The first split lands
m1=10 in the saddle between the two humps (value 96 — past the tall peak's descent,
short of the short one) and m2=20 just past the short peak's own crest at index 18
(value 128, already descending). Since f(m1)=96 < f(m2)=128, that reads as "still
climbing to the right," so lo jumps to 10 and indices 0–9 — including the true,
taller peak at index 1 — are discarded on the very first step and never reconsidered. No error, no
crash, no signal anything went wrong — just a wrong number returned with full confidence.
Using it for sorted-array exact-match search — the problem six of the other eleven
Searching pages solve — costs more comparisons than binary search, not fewer. It's a natural
instinct: if splitting a range in half is good, splitting it in thirds should be better. Checked
against exponential search's own 64-element
array (0, 3, 6, …, 189), searching every one of its 64 values for itself: binary
search needs 328 total comparisons across all 64 targets (average 5.13), a
three-way ternary version needs 400 (average 6.25) — worse on 43 of the 64
targets, tied on 10, and better on only 11 (the cases where a lucky m1 or
m2 happens to land exactly on the target early). Searching for the middle value,
96, alone: 6 comparisons for binary search, 8 for
ternary. The
reason is the same three-way split that helps with unimodal peaks costs two comparisons
(arr[m1] and arr[m2]) per level instead of binary search's one, while
only cutting the range to a third instead of a half — 2 · log₃(n) is
mathematically larger than log₂(n) for every n > 1, so the
extra comparison per level is never paid back by the extra split.
O(log n) either way — finding a unimodal peak takes log₃(n)
narrowing steps, each a constant number of comparisons, so it's the same asymptotic order as
binary search's log₂(n), just with a larger constant, as the checked example
above shows concretely. The two algorithms aren't really competing, though: reach for
binary search when the question is "does this exact
value exist, and where," reach for ternary search when the question is "where does this sequence
peak" — a shape binary search's equality check has no way to answer, since a unimodal sequence
has no target to compare against, only a direction to climb. See Choosing a Search Algorithm for how all twelve
Searching entries stack up side by side.