Skip to content

level 2 · Searching

Ternary Search

Cut into thirds instead of halves — and discover it's actually slower.

8 min 65 XP

what is it

Start here

If cutting the list in half is good, cutting it into thirds must be better. Right? It's such a natural thought that this algorithm exists purely because people keep having it.

Ternary search picks two probe points instead of one, splitting the window into three. Each round it throws away two thirds instead of one half — so it needs fewer rounds. That much is true.

But count the *comparisons*, not the rounds. Each round now costs two looks instead of one. Binary search uses about log₂(n) ≈ 1.0 × log(n) comparisons; ternary uses about 2 × log₃(n) ≈ 1.26 × log(n). It does more work, not less. Run both on the same list and watch the counters.

Keep this one in your head as a warning: an idea can feel obviously faster and be measurably slower. In algorithms, intuition is a hypothesis — the count is the answer.

Ternary search does have a real use, just not this one: finding the peak of a curve that rises then falls, where there's no 'sorted' order to binary-search on at all.

real-life analogy

Picture it

Two people searching the dictionary at once

You open the dictionary at two places instead of one, hoping to narrow it down faster. And you do narrow it faster — but you had to read two pages instead of one to do it. Add up the pages read, not the times you opened the book, and the 'clever' method loses.

interactive visualization

Watch it run

Count the comparisons, then try the same list on Binary Search.

  1. 3
    0
  2. 7
    1
  3. 12
    2
  4. 18
    3
  5. 24
    4
  6. 31
    5
  7. 40
    6
  8. 55
    7
  9. 63
    8
  10. 77
    9
  11. 82
    10
  12. 91
    11

Binary search cuts the window in half. Ternary search cuts it into thirds — surely that's faster? Let's count and find out.

step 01/7

  • comparing
  • found it
  • ruled out
1function ternarySearch(a, target) {
2 let lo = 0, hi = a.length - 1;
3 while (lo <= hi) {
4 const third = Math.floor((hi - lo) / 3);
5 const m1 = lo + third;
6 const m2 = hi - third;
7 if (a[m1] === target) return m1;
8 if (a[m2] === target) return m2;
9 if (target < a[m1]) hi = m1 - 1;
10 else if (target > a[m2]) lo = m2 + 1;
11 else { lo = m1 + 1; hi = m2 - 1; }
12 }
13 return -1;
14}

variables right now

target
82
size
12
comparisons 0moves 0

the dry run · every step, in words

7 steps

complexity

What it costs

best case
O(1)
average
O(log n)
worst case
O(log n)
extra memory
O(1)

Still logarithmic — but with a worse constant than binary search. Roughly 2·log₃(n) ≈ 1.26·log₂(n) comparisons, against binary search's 1.0. Same complexity class, measurably more work.

  • O(1)
  • O(log n) · this one
  • O(n)
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Assuming more splits means fewer comparisons.

    Fewer rounds, but more comparisons per round. Ternary does about 26% more work than binary search. Count comparisons, not iterations.

  • Using it to search a sorted array in real code.

    Don't — binary search is strictly better. Ternary search's real home is finding the peak of a unimodal function, where sorted order doesn't exist.

  • Getting the three-way boundaries wrong.

    The middle third is (m1, m2) exclusive — you already checked both probes. Set lo = m1 + 1 and hi = m2 − 1, or you'll re-check them forever.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+65 XP

01Ternary search does fewer rounds than binary search. Is it faster?

02What is ternary search genuinely good for?

03What's the general lesson here?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.