Ternary Search

What is ternary search?

Ternary search is like binary search, but it splits the sorted list into three parts instead of two. It picks two midpoints, m1 and m2, a third and two thirds of the way through the range. Comparing the key with both tells it which third the key must be in, and it throws the other two thirds away.

Keeping one third sounds better than keeping half. It isn’t, and working out why is a great lesson in counting what an algorithm really does.

How it works, step by step

Press play above. lo and hi mark the range that can still hold the key, and everything outside fades out. The blue bars are the midpoints being compared with the key.

1. Set lo = 0 and hi to the last index.
2. Find the midpoints: m1 = lo + (hi − lo) // 3 and m2 = hi − (hi − lo) // 3.
3. If a[m1] or a[m2] is the key, return that position.
4. If the key is smaller than a[m1], keep the left third: hi = m1 − 1.
5. If the key is bigger than a[m2], keep the right third: lo = m2 + 1.
6. Otherwise it is in the middle third: lo = m1 + 1, hi = m2 − 1.
7. Repeat until you find the key or the range is empty.

Switch between “present” and “absent” and watch the comparison count. Then try binary search on a list of the same size and compare the counts.

Time and space complexity

Each round keeps a third of the range, so it takes about log₃ n rounds. That is O(log n), the same class as binary search.

Now count comparisons. Each round can make two comparisons with the key, so the worst case is about 2 × log₃ n. Binary search makes about log₂ n. Since 2 × log₃ n ≈ 1.26 × log₂ n, ternary search does around 26% more comparisons in the worst case. Fewer rounds, but more work per round.

Best case, O(1): the key is at a midpoint. Average and worst case, O(log n).

Space is O(1) for the loop version.

Where ternary search really shines

Searching a sorted list is not where ternary search is useful. Its real job is finding the highest (or lowest) point of a function that goes up and then down, called a unimodal function.

Check the function at the two midpoints. If the left one is lower, the peak can’t be in the left third, so drop it. If the right one is lower, drop the right third. Binary search can’t do this with one point, because one value alone doesn’t tell you which side of the peak you are on. This is common in math, graphics and competitive programming.

Common mistakes

• Computing the midpoints as n / 3 and 2n / 3 instead of offsets from lo. They must stay inside the current range.
• Forgetting the case where m1 == m2 on tiny ranges. The code checks it so the same value isn’t compared twice.
• Using <= and >= loosely between the thirds and dropping the key by accident. Check equality first, then use strict comparisons.
• Choosing it over binary search for sorted arrays because “three is more than two”.

When to use it

To find the peak or valley of a unimodal function, use ternary search. To find a key in a sorted list, use binary search. It is simpler and does fewer comparisons.

Questions

Is ternary search faster than binary search?

No. It takes fewer rounds but makes about 26% more comparisons in the worst case.

What is ternary search used for?

Mostly for finding the maximum or minimum of a function that rises then falls (or falls then rises).

What is the time complexity of ternary search?

O(log n): about log₃ n rounds of up to two comparisons each.