Seven of the site's other ten 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.
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 = m2Note 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, 68The 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 ten
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 eleven
Searching entries stack up side by side.