Home/Searching/Ternary search
Search algorithmsCTRL K

Ternary search

· two probes, three thirds
/searching/ternary-search
COMPARISONS
0
probes so far
RANGE
32/ 32
elements still possible
PROBES
—
the two cut points
TARGET
33
value we look for
RESULT
—
index once found
discardedprobetargetfound
n = 32 · target 33 · seed 7 · two probes per round · 8 steps
step 0 / 7
Size32
ternary_search.ts
1
function ternarySearch(array: number[], target: number) {
2
  let low = 0, high = array.length - 1;
3
  while (low <= high) {
4
    const third = Math.floor((high - low) / 3);
5
    const first = low + third, second = high - third;
6
    if (array[first] === target) return first;
7
    if (array[second] === target) return second;
8
    if (target < array[first]) high = first - 1;
9
    else if (target > array[second]) low = second + 1;
10
    else { low = first + 1; high = second - 1; }
11
  }
12
  return -1;
13
}
CURRENT STEP
line 2

Look for 33. Two probes per round split the range into three thirds.

// how it works

Understanding Ternary search

ternary search · fewer rounds than binary, more comparisons in total
01

The idea

Ternary search cuts the range at two points, a third and two thirds of the way in, and compares the target with both. That tells which of the three thirds holds the target, so the range shrinks by a factor of three per round instead of two: log₃ n rounds instead of log₂ n.

Each round costs two comparisons, though, and 2 log₃ n is larger than log₂ n. On a sorted array ternary search does more work than binary search. Its real use is different: finding the maximum of a unimodal function, where two probes are needed to know which side is climbing.

02

The four stages

1
probe twiceat low + third and high − third
2
hiteither probe is the target
3
pick a thirdleft, middle or right
4
repeatuntil the range empties
03

Complexity

best
O(1)a probe hits at once
average
O(log₃ n)rounds; comparisons are 2 log₃ n ≈ 1.26 log₂ n
worst
O(log n)the target is in the last third every time
space
O(1)two indices
04

Versus its siblings

COMPARISONS AT N = 1 000 · TARGET PRESENT
linear
500
jump
63
binary
10
ternary
13
interpolation
4
average over random targets · sorted, uniform values
05

Pseudocode

TERNARYSEARCH(array, target)
  low ← 0; high ← n − 1
  while low ≤ high
    first ← low + ⌊(high − low) / 3⌋; second ← high − ⌊(high − low) / 3⌋
    if array[first] = target or array[second] = target: return it
    if target < array[first]: high ← first − 1; else if target > array[second]: low ← second + 1; else: low ← first + 1, high ← second − 1
  return −1
06

When to use

Maximising a unimodal function over a range: the peak of a curve, the best price, the optimal parameter.
Never for plain lookup in a sorted array; binary search wins.
07

Pitfalls

More comparisons than binary search, always; the fewer rounds do not pay for the second probe.
On a unimodal function with plateaus the two probes can be equal and the search loses its direction.
Off-by-one on the two cut points is easy; the middle third must exclude both probes.
08

History

Ternary search on functions is a classic of numerical optimisation, a cousin of golden-section search, which reuses one of the two probes per round and needs only 1.44 log n evaluations. As an array search it survives mostly as an interview question about why it is not better than binary search.

Back to Searching