Ternary Search

Ternary search is binary search's three-way cousin. Instead of one midpoint that halves the search space, it uses two midpoints that cut the window into three equal thirds — and with two comparisons it throws away two of those thirds every iteration. On a sorted array it finds a value; on a unimodal function (one that rises then falls, or falls then rises) the very same split finds the peak or valley.

The classic use is searching a sorted array, but ternary search shines on unimodal extremum problems: maximizing a function that goes up then down (or minimizing one that goes down then up). There is no exact target there — you compare the two midpoints to each other and discard the third that cannot contain the extreme.

Intuition

Binary search asks one yes/no question — is the target left or right of the middle? — and halves what is left. Ternary search asks a slightly richer question by probing two points at once. Picture the window divided into three blocks. The probe mid1 sits a third of the way in, mid2 sits two-thirds in. Two comparisons place the target into exactly one block, so the other two blocks vanish in a single step.

Why not just keep using binary search? For plain array lookups, binary search is actually fewer comparisons per element removed — ternary does more work to delete the same fraction. The real payoff is the unimodal case: a function with a single peak has no notion of "less than the target," so you cannot binary search it. But you can compare the two midpoints to each other — whichever side is lower can be dropped — and that is exactly what the two-probe split gives you.

Walk through it

Step through the animation on the right. The array is sorted, lo and hi bracket the active window, and the window [lo, hi] label tracks it. Each iteration drops two pointers, mid1 and mid2, splitting the window into thirds.

First iteration: the window is [0, 8], so mid1 = 2 (value 8) and mid2 = 6 (value 38). The target 16 is bigger than 8 but smaller than 38, so it must live in the middle third — both outer thirds dim out and the window shrinks to [3, 5]. Second iteration: mid1 = 3 (value 12), mid2 = 5 (value 23). Again 16 is between them, so the window narrows to the single index [4, 4]. Third iteration: both midpoints collapse onto index 4, a[4] = 16 matches, and that cell turns green. Three iterations, and most of the array was discarded in two-thirds chunks.

The code, line by line

def ternary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid1 = lo + (hi - lo) // 3
        mid2 = hi - (hi - lo) // 3
        if x < a[mid1]:
            hi = mid1 - 1
        elif a[mid1] == x:
            return mid1
        elif x > a[mid2]:
            lo = mid2 + 1
        elif a[mid2] == x:
            return mid2
        else:
            lo, hi = mid1 + 1, mid2 - 1
    return -1

• Lines 4 and 5 compute the two cut points. Writing lo + (hi - lo) // 3 (rather than (lo + 2*hi) / 3) avoids overflow and keeps the index inside the window.
• Line 6 handles the left third: if x is smaller than a[mid1], everything from mid1 rightward is too big, so hi = mid1 - 1.
• Lines 8 and 12 are the two exact-match checks — ternary search has two probes, so it can finish at either one.
• Line 10 handles the right third: if x is bigger than a[mid2], everything up to mid2 is too small, so lo = mid2 + 1.
• Line 15 is the middle third: the target is between the two probes, so we keep only what is strictly between them with lo, hi = mid1 + 1, mid2 - 1.

Complexity

The number of iterations is log base 3 of n, which is fewer than binary search's log base 2 of n. But each iteration spends two comparisons instead of one, and 2 * log3(n) is actually more total comparisons than log2(n). So for plain sorted-array lookup, binary search wins on comparison count. Ternary search earns its keep on unimodal optimization, where binary search does not apply at all.

When to use / pitfalls

Practice