# Ternary Search, Explained Step by Step

> Split a sorted array into thirds with two midpoints and keep one third.

Searching algorithm. Interactive version, with a step-by-step visualizer of a real recorded run: https://www.tmread.me/algorithms/ternary-search

## Complexity

| | Big-O | Why |
|---|---|---|
| Best time | O(1) | The key sits at the first midpoint. |
| Average time | O(log n) | Each round keeps a third of the range. |
| Worst time | O(log n) | About log₃ n rounds, but two checks per round. |
| Extra space | O(1) | A few pointers, no recursion. |

## 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.

## Code

### Python

```python
def ternary_search(a, key):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        m1, m2 = lo+(hi-lo)//3, hi-(hi-lo)//3
        if a[m1] == key: return m1
        if m2 != m1 and a[m2] == key: return m2
        if key < a[m1]: hi = m1 - 1
        elif m2 == m1: return -1
        elif key > a[m2]: lo = m2 + 1
        else: lo, hi = m1 + 1, m2 - 1
    return -1
```

### TypeScript

```ts
function ternarySearch(a: number[], key: number) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const third = Math.floor((hi - lo) / 3);
    const m1 = lo + third, m2 = hi - third;
    if (a[m1] === key) return m1;
    if (m2 !== m1 && a[m2] === key) return m2;
    if (key < a[m1]) hi = m1 - 1;
    else if (m2 === m1) return -1;
    else if (key > a[m2]) lo = m2 + 1;
    else [lo, hi] = [m1 + 1, m2 - 1];
  }
  return -1;
}
```

### Go

```go
func ternarySearch(a []int, key int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        third := (hi - lo) / 3
        m1, m2 := lo+third, hi-third
        if a[m1] == key {
            return m1
        }
        if m2 != m1 && a[m2] == key {
            return m2
        }
        if key < a[m1] {
            hi = m1 - 1
        } else if m2 == m1 {
            return -1
        } else if key > a[m2] {
            lo = m2 + 1
        } else {
            lo, hi = m1+1, m2-1
        }
    }
    return -1
}
```

## 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.

## Related algorithms

- [Binary Search](https://www.tmread.me/algorithms/binary-search.md): Check the middle of a sorted array and throw away the half that can’t hold the key.
- [Exponential Search](https://www.tmread.me/algorithms/exponential-search.md): Double a bound until it passes the key, then binary search that range.
- [Interpolation Search](https://www.tmread.me/algorithms/interpolation-search.md): Guess where the key should be from its value, like opening a dictionary near the right letter.

---

From The Missing README (computer science, made visible). Want to run your own code and watch every step? Join Cohort 0, the early-access group: https://www.tmread.me/#cohort