Lesson 38.1 · Advanced Search and Divide & Conquer

Ternary Search on Unimodal Functions

If a function increases then decreases, compare two inner points and throw away the third that can't contain the peak. On integer arrays, comparing mid with mid + 1 (binary search) does the same job faster.

10 min

Think of it like this

Finding the top of a hill in fog: take two steps apart and compare heights. The higher point is closer to the summit, so the far side beyond the lower point can be ignored.

1.Two forms

Continuous (real-valued f): pick m1 = lo + (hi − lo)/3 and m2 = hi − (hi − lo)/3. If f(m1) < f(m2), the peak is right of m1: lo = m1; else hi = m2. Repeat a fixed number of times (each step keeps two thirds).

Discrete (array that rises then falls): binary search on the slope. If a[mid] < a[mid + 1], you're on the rising side: lo = mid + 1; else hi = mid. O(log n) and no plateau issues when values are strictly unimodal.

Main.java

public class Main {
    static double f(double x) { return -(x - 2) * (x - 2) + 5; }   // peak at x = 2

    public static void main(String[] args) {
        double lo = -10, hi = 10;
        for (int i = 0; i < 100; i++) {
            double m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
            if (f(m1) < f(m2)) lo = m1; else hi = m2;
        }
        System.out.printf("peak near x = %.4f, f = %.4f%n", lo, f(lo));

        int[] a = {1, 3, 8, 12, 9, 4, 2};
        int l = 0, r = a.length - 1;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (a[mid] < a[mid + 1]) l = mid + 1; else r = mid;
        }
        System.out.println("array peak at index " + l);
    }
}

Output

peak near x = 2.0000, f = 5.0000
array peak at index 3

Remember

Unimodal = one peak.
Real values: ternary with a fixed iteration count.
Arrays: binary search on the slope.

Common mistakes

Using ternary search when there are flat regions (it can't decide which side to drop).

Words used in this lesson

Unimodal: Increases up to one peak and then decreases (or the reverse).

Command Palette

Ternary Search on Unimodal Functions

1.Two forms