Ternary search

Ternary search finds the top (the highest point) of an array or a function that rises and then falls, or the lowest point of one that falls and then rises, with two looks per round. If the question is where a sorted array or a yes/no check turns from "no" to "yes", use binary search instead.

Explanation

Here are ten numbers in an array: 8, 9, 11, 12, 14, 15, 17, 16, 6, 1, at indices 0 to 9. They strictly rise up to their top, 17 at index 6, and then strictly fall. A row like this is unimodal. Reading from the left until the next number is smaller finds the top, but with $n$ numbers that can take $n$ looks.

Fig. 1. Ten numbers that rise to 17 at index 6, then fall.

For a million numbers, or for a function of a real number with no list to read, we want to look at only a few places, the way binary search does in a sorted array. But these values are not sorted: they go up and then down. Binary search would look in the middle. Index 4 holds 14. Is the top to its left or to its right? The 14 alone can't say: the array 8, 15, 17, 16, 14, 11, 9, 6, 3, 1 also rises and then falls, and it also holds 14 at index 4, but its top is at index 2, to the left.

Fig. 2. Both arrays hold 14 in the middle (red), but their tops (blue) are on different sides.

So one look is not enough. Two looks next to each other, at 4 and 5, settle it: 14 < 15, so the array still rises there and the top is to the right. That is binary search on the yes/no check "is the next number bigger?", and on an array it is the fastest way. On a function of a real number there is no next place, and a tiny step would have to be chosen.

Ternary search spreads the two looks apart. Take two places, the left look and the right look, and suppose the left look holds the smaller number. If the top were at the left look or to its left, both looks would be on the falling side, so the left look would hold the bigger number. It doesn't, so the top is at the left look or to its right, and everything before the left look can be dropped. If the left look holds the bigger number, the same argument from the other side drops everything after the right look.

The simple choice is to put the looks one third and two thirds of the way along the range. Whichever outer third is dropped, two thirds remain: a little slower than halving, but the same rule works on integers and on real numbers, with no step to choose. When only three places or fewer are left, look at all of them.

This is ternary search. It takes O(\log n) rounds of two looks each.

The top is somewhere from l = 0 to r = 9. The arrows mark l and r.

The looks are 3 (12) and 6 (17). 12 < 17, so l moves to 3 and indices 0–2 are dropped. The looks are outlined in blue, the end that moved is red, and dropped cells are grey.

The looks are 5 (15) and 7 (16). 15 < 16, so l moves to 5 and indices 3–4 are dropped.

The looks are 6 (17) and 8 (6). 17 > 6, so r moves to 8 and index 9 is dropped.

The looks are 6 (17) and 7 (16). 17 > 16, so r moves to 7 and index 8 is dropped.

Now r − l = 2, so the loop stops. Of the last places 5 to 7, index 6 holds the largest number, 17: the top.

1/6

Fig. 3. Step through ternary search with the buttons or the arrow keys. Blue cells are the two looks, grey cells are dropped, and the top is green at the end.

On ten numbers the search makes 11 looks, more than the 8 a scan from the left needs here. The gain shows for large arrays: for 10^6 numbers the loop runs at most 33 rounds (the bound \log_{3/2} 10^6 \approx 34), so it makes at most 69 looks.

Functions of a real number

Take a square sheet of card 12 cm wide, cut a square of side $x$ from each corner and fold the sides up into an open box. The box has volume x \cdot (12 - 2x)^2. A small cut gives a flat box, a big cut a narrow one, so as $x$ goes from 0 to 6 the volume grows and then shrinks.

The same two looks work on the function: look at $x$ one third and two thirds of the way from 0 to 6, that is at 2 and 4. The volumes are 128 and 64, so everything after 4 is dropped. There are no places to list, so instead of stopping at three places the loop runs a fixed number of rounds, as binary search does on real numbers.

Fig. 4. Each round drops the third beyond the look with the smaller volume.

The largest box comes from x = 2, with volume 128.

Implementation

The range still searched runs from l to r, both included, and keeps the top. The left look is m1 and the right look is m2:

m1 = l + (r - l) / 3
m2 = r - (r - l) / 3

In the first round l = 0 and r = 9, so (r - l) / 3 is 3, and the looks are 3 and 6. Integer division rounds down: in round 3, l = 5 and r = 9, (9 - 5) / 3 is 1, so the looks are 6 and 8. While r - l is at least 3, (r - l) / 3 is at least 1, so each round drops at least one place. When r - l is 2 or less, it is 0, the looks fall on l and r, and nothing would move, so the loop stops and the program checks the last places itself.

1. Start: l = 0 and r = n - 1.

2. Look: compute m1 and m2.

3. Compare and drop: if a[m1] < a[m2], set l = m1; otherwise set r = m2.

4. Repeat from step 2 while r - l > 2.

5. Finish: the largest of a[l] to a[r], at most three numbers.

The program reads n, then n numbers that rise and then fall, and prints the index of the top and its value. For the main example the input is:

10
8 9 11 12 14 15 17 16 6 1

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // start: the top is somewhere in 0..n-1
    int l = 0, r = n - 1;
    // the top always stays somewhere from l to r
    while (r - l > 2) {
        // look: one third and two thirds of the way
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        // compare and drop (for a function, replace a[m] with f(m))
        if (a[m1] < a[m2]) l = m1;   // the top is not left of m1
        else r = m2;                 // the top is not right of m2
    }
    // finish: at most 3 places are left
    int best = l;
    for (int i = l + 1; i <= r; i++)
        if (a[i] > a[best]) best = i;
    cout << best << ' ' << a[best] << '\n';
}

The loop makes O(\log n) rounds with two looks each. When each value comes from a function f(m) that takes $O(T)$ time, an integer search over a range of size $K$ costs O(T \log K). To find the lowest point of a function that falls and then rises, flip the comparison: if (f(m1) > f(m2)) l = m1; else r = m2;.

Code for a function of a real number

The program for the box reads the side of the sheet s and searches x from 0 to s / 2 in 100 rounds of double arithmetic. Since (2/3)^{100} \approx 2.5 \cdot 10^{-18}, 100 rounds shrink the range of 6 down to the gap between neighbouring double values, for 200 calls of volume. It can't shrink further, and near the top the two volumes become equal up to rounding. So x is accurate to about 10^{-8}, while the volume, which hardly changes there, is accurate in all printed digits. For the box the input is 12, and the program prints 2.000000 128.000000.

#include <cstdio>

double s;

double volume(double x) {
    return x * (s - 2 * x) * (s - 2 * x);
}

int main() {
    scanf("%lf", &s);
    // start: the cut is between 0 and s / 2
    double l = 0, r = s / 2;
    for (int it = 0; it < 100; it++) {
        // look
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        // compare and drop
        if (volume(m1) < volume(m2)) l = m1;
        else r = m2;
    }
    // finish
    printf("%.6f %.6f\n", l, volume(l));
}

Correctness proof

Let $t$ be the index of the top. The loop keeps one invariant: the top is always somewhere from l to r. In symbols, l \le t \le r.

The rule in the Explanation shows that each strict comparison keeps $t$ between $l$ and $r$. If a_{m_1} = a_{m_2}, the looks can't be both on the rising or both on the falling side, so m_1 < t < m_2 and either move is safe.

Each round drops at least one place (see Implementation), so the loop ends with at most three places from $l$ to $r$. The top is one of them, and the finish checks them all.

When the values are not unimodal

The proof used that the numbers only rise before the top and only fall after it. With two tops this fails. In 1, 9, 2, 3, 4, 5, 6, 2, 1 the first round drops the 9, and the search returns 6.

Fig. 5. With two tops, the first round drops the higher one (red).

Flat stretches break the proof too: two equal numbers no longer have to be on different sides. On 1, 3, 3, 3, 3, 3, 9, 2 the first looks, at indices 2 and 5, both hold 3, r moves to 5, and the search returns 3 instead of 9. On such an array there is no logarithmic method in general; scan it in $O(n)$.

Equal looks are safe when the function is flat nowhere except at its top or lowest point. A convex function, whose slope never decreases, is like that: |1 - k| + |5 - k| for $k$ from 0 to 6 gives 6, 4, 4, 4, 4, 4, 6, flat only at the bottom. So a total cost such as the sum of c_i \cdot |h_i - k| over all $i$ (moving every item $i$ from height h_i to height $k$ at cost c_i per unit) can be searched over $k$.

Common mistakes

• Stopping when r - l drops below a small eps. The range can't shrink below the gap between neighbouring double values, and around 10^9 that gap is about 1.2 \cdot 10^{-7}, so while (r - l > 1e-9) on (x - c)^2 with c = 10^9 + 0.3 was still running after 10^7 rounds. Run a fixed 100 rounds.

Similar algorithms

Binary search finds where a yes/no check turns. On an array, the check "is a[m] < a[m + 1]?" from the Explanation finds the top with about half the looks. On a function of a real number the check becomes f(m) < f(m + eps), and the answer depends on the choice of eps; ternary search needs no eps.

Golden-section search places the looks so that one of them is reused in the next round. Each round keeps about 0.618 of the range for one new look; ternary search keeps two thirds for two looks, which is \sqrt{2/3} \approx 0.816 per look.

The name "ternary search" is sometimes used for splitting a sorted array into three parts to find a value. That is binary search with two looks per round, and it gains nothing.

Practice