Data Structures & AlgorithmsTernary Search

Ternary Search — Finding Extrema in Unimodal Functions

LevelIntermediate

Duration55 mins

TopicTernary Search

3 / 4

Finding Maximum/Minimum of Unimodal Functions

From Theory to Implementation

We've established the theoretical foundation: ternary search solves optimization problems on unimodal functions where binary search fails. Now it's time to translate this understanding into working code.

This page provides complete, production-quality implementations of ternary search. We'll cover:

The core algorithm for continuous domains
Precision and termination considerations
Discrete (integer) domain variations
Finding minima vs. maxima
Advanced optimizations including golden section search

By the end, you'll have a robust toolkit for optimization problems in competitive programming and real-world applications.

What You Will Learn

By the end of this page, you will be able to implement ternary search from scratch for both continuous and discrete domains, handle precision issues correctly, choose appropriate termination conditions, and apply golden section search for improved efficiency.

The Core Algorithm — Continuous Maximum

Let's start with the most common case: finding the x-value that maximizes a unimodal function over a continuous interval [a, b].

Algorithm Overview

Start with interval [left, right] = [a, b]
Place two interior points m1 and m2 that divide the interval into thirds
Compare f(m1) and f(m2)
Eliminate the third that cannot contain the maximum
Repeat until the interval is smaller than desired precision
Return the midpoint of the final interval

Why This Works

For a unimodal function with maximum at x*:

If f(m1) < f(m2): Since f is increasing toward x* and decreasing after, x* must be to the right of m1. We can safely eliminate [left, m1].
If f(m1) > f(m2): Symmetrically, x* must be to the left of m2. Eliminate [m2, right].
If f(m1) = f(m2): Either point could be on either side of x*, but we can eliminate either outer third safely. Convention: eliminate the right third.

Each iteration shrinks the interval to 2/3 of its previous size.

TernarySearchMax.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Ternary Search: Find x that maximizes f(x) on continuous [left, right]
 * 
 * @param f - The unimodal function to maximize
 * @param left - Left bound of search interval
 * @param right - Right bound of search interval
 * @param epsilon - Desired precision (default: 1e-9)
 * @returns x value that (approximately) maximizes f
 */
function ternarySearchMax(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    while (right - left > epsilon) {
        // Divide interval into thirds
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        
        // Compare function values at interior points
        if (f(m1) < f(m2)) {
            // Maximum is to the right of m1
            // Eliminate left third: [left, m1]
            left = m1;
        } else {
            // Maximum is to the left of m2
            // Eliminate right third: [m2, right]
            right = m2;
        }
    }
    
    // Return midpoint of final interval
    return (left + right) / 2;
}
 
// Example: Find x that maximizes f(x) = -(x - 7)² + 100
// Maximum should be at x = 7 where f(7) = 100
function exampleFunc(x: number): number {
    return -Math.pow(x - 7, 2) + 100;
}
 
const xMax = ternarySearchMax(exampleFunc, 0, 20);
console.log(`Maximum at x = ${xMax.toFixed(6)}`);        // ~7.000000
console.log(`f(x) = ${exampleFunc(xMax).toFixed(6)}`);    // ~100.000000

Understanding the Division

The points m1 and m2 divide [left, right] into three equal parts. m1 = left + (right - left)/3 is 1/3 of the way from left to right. m2 = right - (right - left)/3 is 2/3 of the way (equivalently, 1/3 from the right).

Finding Minimum — The Dual Case

Finding the minimum of a unimodal function (a "valley" rather than "peak") requires only a small modification: we reverse the comparison.

For Maximum: If f(m1) < f(m2), eliminate left third (go toward higher values) For Minimum: If f(m1) < f(m2), eliminate right third (go toward lower values)

Alternatively, you can reuse the maximum-finding code by negating the function: min f(x) = max -f(x).

TernarySearchMin.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Ternary Search: Find x that minimizes f(x) on continuous [left, right]
 */
function ternarySearchMin(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    while (right - left > epsilon) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        
        // REVERSED COMPARISON for minimum
        if (f(m1) > f(m2)) {
            // Minimum is to the right of m1
            left = m1;
        } else {
            // Minimum is to the left of m2
            right = m2;
        }
    }
    
    return (left + right) / 2;
}
 
// Example: Find x that minimizes f(x) = (x - 4)² + 5
// Minimum should be at x = 4 where f(4) = 5
function convexFunc(x: number): number {
    return Math.pow(x - 4, 2) + 5;
}
 
const xMin = ternarySearchMin(convexFunc, -10, 10);
console.log(`Minimum at x = ${xMin.toFixed(6)}`);        // ~4.000000
console.log(`f(x) = ${convexFunc(xMin).toFixed(6)}`);    // ~5.000000
 
// Alternative: Use max version with negated function
function ternarySearchMaxFromMin(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    return ternarySearchMax(x => -f(x), left, right, epsilon);
}
 
// ternarySearchMaxFromMin returns same result by maximizing -f(x)

Duality Principle

Minimization and maximization are dual problems. Any algorithm that finds a maximum can find a minimum by negating the function (or flipping comparisons). This duality means you only need to truly understand one case.

Precision and Termination Strategies

Choosing when to terminate ternary search is subtle. Unlike discrete binary search which naturally terminates, continuous ternary search can refine indefinitely. Here are the main approaches:

Strategy 1: Absolute Epsilon

Terminate when right - left < epsilon for some fixed epsilon (e.g., 1e-9).

Pros: Simple, predictable
Cons: May be too tight for large values (wasted iterations) or too loose for small values (insufficient precision)

Strategy 2: Relative Epsilon

Terminate when (right - left) / |right + left| < epsilon.

Pros: Adapts to the scale of the answer
Cons: Problematic when the answer is near zero

Strategy 3: Fixed Iteration Count

Run exactly N iterations regardless of convergence.

Pros: Predictable runtime, no precision issues
Cons: May over-compute or under-compute depending on N

Strategy 4: Combined Approach

Use relative epsilon with a fallback to absolute epsilon, plus a maximum iteration limit.

TerminationStrategies.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Different termination strategies for ternary search
 
// Strategy 1: Absolute epsilon
function ternarySearchAbsolute(
    f: (x: number) => number,
    left: number,
    right: number,
    absEps: number = 1e-9
): number {
    while (right - left > absEps) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    return (left + right) / 2;
}
 
// Strategy 2: Relative epsilon
function ternarySearchRelative(
    f: (x: number) => number,
    left: number,
    right: number,
    relEps: number = 1e-9
): number {
    while (true) {
        const mid = (left + right) / 2;
        if (Math.abs(mid) < 1e-15 || (right - left) / Math.abs(mid) <= relEps) {
            return mid;
        }
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
}
 
// Strategy 3: Fixed iterations (most common in competitive programming)
function ternarySearchIterations(
    f: (x: number) => number,
    left: number,
    right: number,
    iterations: number = 200  // Usually sufficient for 1e-60 precision
): number {
    for (let i = 0; i < iterations; i++) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    return (left + right) / 2;
}
 
// Strategy 4: Combined approach (production-grade)
function ternarySearchRobust(
    f: (x: number) => number,
    left: number,
    right: number,
    absEps: number = 1e-12,
    relEps: number = 1e-9,
    maxIter: number = 300
): number {
    for (let i = 0; i < maxIter; i++) {
        const width = right - left;
        const mid = (left + right) / 2;
        
        // Check termination conditions
        if (width < absEps) break;
        if (Math.abs(mid) > 1e-15 && width / Math.abs(mid) < relEps) break;
        
        const m1 = left + width / 3;
        const m2 = right - width / 3;
        
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    return (left + right) / 2;
}
 
// Demo: How many iterations for given precision?
console.log("Iterations needed for precision:");
console.log(`ε = 1e-6:  ~${Math.ceil(Math.log(1e6) / Math.log(1.5))} iterations`);
console.log(`ε = 1e-9:  ~${Math.ceil(Math.log(1e9) / Math.log(1.5))} iterations`);
console.log(`ε = 1e-12: ~${Math.ceil(Math.log(1e12) / Math.log(1.5))} iterations`);

Competitive Programming Tip

In contests, use the fixed iteration approach with 200-300 iterations. This gives precision well beyond any reasonable requirement (~10^-60 relative to initial interval) and has completely predictable performance. No need to worry about edge cases with epsilon comparisons.

Convergence Analysis

Each iteration reduces the interval to 2/3 of its previous size. After k iterations:

final_width = initial_width × (2/3)^k

To achieve precision ε:

(2/3)^k < ε / initial_width

k > log(initial_width / ε) / log(3/2)

k > log_{1.5}(initial_width / ε)

For initial_width = 10^9 and ε = 10^-9:

k > log_{1.5}(10^18) ≈ 102 iterations

200 iterations provides a massive safety margin.

Discrete Domain Implementation

When the domain is integers (as in many competitive programming problems), ternary search needs slight modifications:

Use integer arithmetic for m1 and m2
Terminate when right - left < 3 (can't place two distinct interior points)
Check remaining candidates directly

The key insight is that with integers, when right - left = 2, we have exactly 3 candidates: left, left+1, right. We can't place two distinct interior points, so we must compare all three directly.

TernarySearchDiscrete.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * Ternary Search for integers: Find integer x that maximizes f(x)
 */
function ternarySearchMaxInt(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    // Phase 1: Ternary search until only a few candidates remain
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        
        if (f(m1) < f(m2)) {
            left = m1;  // Note: m1 itself might be the answer!
        } else {
            right = m2;
        }
    }
    
    // Phase 2: Linear scan of remaining candidates
    let bestX = left;
    let bestVal = f(left);
    
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val > bestVal) {
            bestVal = val;
            bestX = x;
        }
    }
    
    return bestX;
}
 
/**
 * Ternary Search for integers: Find integer x that minimizes f(x)
 */
function ternarySearchMinInt(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        
        if (f(m1) > f(m2)) {  // Reversed for minimum
            left = m1;
        } else {
            right = m2;
        }
    }
    
    let bestX = left;
    let bestVal = f(left);
    
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val < bestVal) {  // Reversed for minimum
            bestVal = val;
            bestX = x;
        }
    }
    
    return bestX;
}
 
// Example: Find k ∈ {0, 1, ..., 100} that minimizes f(k) = |k - 37|
const targetK = ternarySearchMinInt(k => Math.abs(k - 37), 0, 100);
console.log(`Answer: k = ${targetK}`);  // 37
 
// Example: Revenue optimization with discrete prices
// price ∈ {0, 1, 2, ..., 100}, revenue = price × (100 - price)
const optimalPrice = ternarySearchMaxInt(
    price => price * (100 - price),
    0, 100
);
console.log(`Optimal price: ${optimalPrice}`);  // 50

Integer Boundary Subtlety

In integer ternary search, when we set left = m1, we're NOT eliminating m1 itself—m1 might be the answer. This differs from the continuous case where boundaries are infinitesimally refined. The final linear scan handles this correctly.

Golden Section Search — An Optimization

Standard ternary search evaluates f at two points per iteration. But there's a clever optimization: golden section search positions the probe points such that one evaluation from the previous iteration can be reused.

The Golden Ratio

The golden ratio φ = (1 + √5) / 2 ≈ 1.618 has a remarkable property: if we divide an interval by φ, the ratio of the whole to the larger part equals the ratio of the larger part to the smaller part.

How Golden Section Works

Place probe points at distances gr and 1-gr from the left, where gr = 2 - φ ≈ 0.382:

m1 = left + (right - left) × gr
m2 = left + (right - left) × (1 - gr)

When we eliminate one third and shift the interval:

One of the old probe points falls at exactly the right position to be reused
We only need ONE new function evaluation per iteration

This reduction from 2 to 1 evaluation per iteration halves the number of function calls!

GoldenSectionSearch.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Golden Section Search: Find x that maximizes f(x)
 * More efficient than standard ternary search - uses only 1 evaluation per iteration
 */
function goldenSectionMax(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    // Golden ratio constants
    const phi = (1 + Math.sqrt(5)) / 2;
    const gr = 2 - phi;  // ≈ 0.381966...
    
    // Initial probe points
    let m1 = left + gr * (right - left);
    let m2 = right - gr * (right - left);
    let f1 = f(m1);
    let f2 = f(m2);
    
    while (right - left > epsilon) {
        if (f1 < f2) {
            // Maximum is in [m1, right]
            left = m1;
            m1 = m2;
            f1 = f2;
            // Reused m1/f1, only compute new m2/f2
            m2 = right - gr * (right - left);
            f2 = f(m2);
        } else {
            // Maximum is in [left, m2]
            right = m2;
            m2 = m1;
            f2 = f1;
            // Reused m2/f2, only compute new m1/f1
            m1 = left + gr * (right - left);
            f1 = f(m1);
        }
    }
    
    return (left + right) / 2;
}
 
// Example: Same function as before
function exampleFunc(x: number): number {
    return -Math.pow(x - 7, 2) + 100;
}
 
// Count function evaluations for comparison
let ternaryEvals = 0;
let goldenEvals = 0;
 
function countedFuncTernary(x: number): number {
    ternaryEvals++;
    return exampleFunc(x);
}
 
function countedFuncGolden(x: number): number {
    goldenEvals++;
    return exampleFunc(x);
}
 
// Run both with same precision
const eps = 1e-9;
ternarySearchMax(countedFuncTernary, 0, 20, eps);
goldenSectionMax(countedFuncGolden, 0, 20, eps);
 
console.log(`Ternary search evaluations: ${ternaryEvals}`);  // ~144
console.log(`Golden section evaluations: ${goldenEvals}`);   // ~74 (roughly half!)

Ternary Search vs. Golden Section Search
Aspect	Ternary Search	Golden Section Search
Evaluations per iteration	2	1 (after initialization)
Interval reduction factor	2/3 ≈ 0.667	1/φ ≈ 0.618
Total evaluations (N iterations)	2N	N + 1
Implementation complexity	Simple	Slightly more complex
Numerical stability	Excellent	Excellent
Best for	General use	Expensive function evaluations

When to Use Golden Section

Use golden section search when function evaluation is expensive (database queries, simulations, external API calls). For simple mathematical functions, the overhead of the additional bookkeeping may not justify the savings. In competitive programming, standard ternary search is usually sufficient.

Complete Reference Implementation

Here's a production-ready ternary search module that handles all common cases:

TernarySearchComplete.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/**
 * Complete Ternary Search Module
 * Production-ready implementations for all common use cases
 */
 
// ========================================
// CONTINUOUS DOMAIN
// ========================================
 
export function ternaryMaxContinuous(
    f: (x: number) => number,
    left: number,
    right: number,
    options: { epsilon?: number; maxIter?: number } = {}
): { x: number; value: number } {
    const { epsilon = 1e-9, maxIter = 300 } = options;
    
    for (let i = 0; i < maxIter && right - left > epsilon; i++) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    
    const x = (left + right) / 2;
    return { x, value: f(x) };
}
 
export function ternaryMinContinuous(
    f: (x: number) => number,
    left: number,
    right: number,
    options: { epsilon?: number; maxIter?: number } = {}
): { x: number; value: number } {
    // Minimize f = maximize -f
    const result = ternaryMaxContinuous(x => -f(x), left, right, options);
    return { x: result.x, value: f(result.x) };
}
 
// ========================================
// DISCRETE (INTEGER) DOMAIN
// ========================================
 
export function ternaryMaxDiscrete(
    f: (x: number) => number,
    left: number,
    right: number
): { x: number; value: number } {
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    
    let bestX = left;
    let bestVal = f(left);
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val > bestVal) {
            bestVal = val;
            bestX = x;
        }
    }
    return { x: bestX, value: bestVal };
}
 
export function ternaryMinDiscrete(
    f: (x: number) => number,
    left: number,
    right: number
): { x: number; value: number } {
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (f(m1) > f(m2)) left = m1;
        else right = m2;
    }
    
    let bestX = left;
    let bestVal = f(left);
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val < bestVal) {
            bestVal = val;
            bestX = x;
        }
    }
    return { x: bestX, value: bestVal };
}
 
// ========================================
// GOLDEN SECTION (EFFICIENT FOR EXPENSIVE F)
// ========================================
 
export function goldenMaxContinuous(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): { x: number; value: number } {
    const phi = (1 + Math.sqrt(5)) / 2;
    const gr = 2 - phi;
    
    let m1 = left + gr * (right - left);
    let m2 = right - gr * (right - left);
    let f1 = f(m1), f2 = f(m2);
    
    while (right - left > epsilon) {
        if (f1 < f2) {
            left = m1;
            m1 = m2; f1 = f2;
            m2 = right - gr * (right - left);
            f2 = f(m2);
        } else {
            right = m2;
            m2 = m1; f2 = f1;
            m1 = left + gr * (right - left);
            f1 = f(m1);
        }
    }
    
    const x = (left + right) / 2;
    return { x, value: f(x) };
}
 
// ========================================
// USAGE EXAMPLES
// ========================================
 
// Example 1: Continuous maximum
const result1 = ternaryMaxContinuous(x => -(x - 5) ** 2 + 100, 0, 10);
console.log(`Continuous max: x=${result1.x.toFixed(4)}, f(x)=${result1.value.toFixed(4)}`);
 
// Example 2: Discrete minimum
const result2 = ternaryMinDiscrete(x => (x - 42) ** 2, 0, 100);
console.log(`Discrete min: x=${result2.x}, f(x)=${result2.value}`);
 
// Example 3: Golden section for expensive function
let callCount = 0;
function expensiveF(x: number): number {
    callCount++;
    // Simulate expensive computation
    return -x ** 2 + 10 * x - 5;
}
const result3 = goldenMaxContinuous(expensiveF, 0, 10);
console.log(`Golden section: x=${result3.x.toFixed(4)}, calls=${callCount}`);

Common Pitfalls and Debugging

Common Implementation Mistakes

•Wrong comparison direction — For maximum, eliminate where values are LOWER; for minimum, eliminate where values are HIGHER. Easy to flip accidentally.
•Floating-point precision issues — Using == to compare floats. Use epsilon-based comparison or sufficient iterations instead.
•Integer truncation in discrete search — Forgetting Math.floor() for integer division. JavaScript / gives floats even for integers!
•Forgetting the linear scan for discrete — Terminating when right - left < 3 but not checking remaining candidates.
•Assuming strict unimodality — If function has plateaus (f(m1) = f(m2)), the standard comparison may behave unexpectedly. Handle the equality case explicitly.
•Wrong bounds — Starting with bounds that don't contain the optimum. Ternary search won't magically find values outside [left, right].
•Not verifying unimodality — Running ternary search on multi-modal function gives an answer—just not the right one.

Debugging Strategy

When ternary search gives unexpected results:

Verify unimodality — Plot the function or print values at several points. Confirm single peak/valley.
Check bounds — Ensure [left, right] contains the optimum.
Trace first few iterations — Print left, right, m1, m2, f(m1), f(m2) and verify elimination is correct.
Test on known functions — Try f(x) = -(x-5)² where you know the answer should be x=5.
Check termination — Ensure epsilon is appropriate for the problem scale.

Unit Testing Ternary Search

Create a test suite with known unimodal functions: parabolas, triangle functions, Gaussians. Verify the algorithm finds the correct extremum within expected precision. Include edge cases: very large ranges, very small ranges, answer at boundary, answer near zero.

Summary: Ternary Search Mastery

We've covered complete, production-ready implementations of ternary search for finding extrema in unimodal functions.

Key Takeaways

•Core algorithm is simple — Divide into thirds, compare, eliminate one third, repeat.
•Max vs. Min differs only in comparison direction — Or negate the function.
•Termination needs care — Use fixed iterations (200+) in competitive programming; use epsilon with max iterations in production.
•Discrete domains need linear scan — When too few candidates remain, check them directly.
•Golden section halves evaluations — Worth using when function calls are expensive.
•Verify unimodality before trusting results — Multi-modal functions fail silently.

What's Next:

We've mastered the algorithm itself. The next page compares ternary search with binary search in depth—when to use each, their relative efficiency, and how to recognize which approach fits a given problem. This comparison cements your understanding and gives you clear decision criteria.

Page Complete

You now have complete implementations for ternary search across continuous and discrete domains, with optimization techniques and debugging strategies. Next, we'll compare ternary search with binary search to understand exactly when each applies.

3 / 4

Loading learning content...

Data Structures & AlgorithmsTernary Search

Ternary Search — Finding Extrema in Unimodal Functions

LevelIntermediate

Duration55 mins

TopicTernary Search

3 / 4

Finding Maximum/Minimum of Unimodal Functions

From Theory to Implementation

This page provides complete, production-quality implementations of ternary search. We'll cover:

The core algorithm for continuous domains
Precision and termination considerations
Discrete (integer) domain variations
Finding minima vs. maxima
Advanced optimizations including golden section search

By the end, you'll have a robust toolkit for optimization problems in competitive programming and real-world applications.

What You Will Learn

The Core Algorithm — Continuous Maximum

Let's start with the most common case: finding the x-value that maximizes a unimodal function over a continuous interval [a, b].

Algorithm Overview

Start with interval [left, right] = [a, b]
Place two interior points m1 and m2 that divide the interval into thirds
Compare f(m1) and f(m2)
Eliminate the third that cannot contain the maximum
Repeat until the interval is smaller than desired precision
Return the midpoint of the final interval

Why This Works

For a unimodal function with maximum at x*:

If f(m1) < f(m2): Since f is increasing toward x* and decreasing after, x* must be to the right of m1. We can safely eliminate [left, m1].
If f(m1) > f(m2): Symmetrically, x* must be to the left of m2. Eliminate [m2, right].
If f(m1) = f(m2): Either point could be on either side of x*, but we can eliminate either outer third safely. Convention: eliminate the right third.

Each iteration shrinks the interval to 2/3 of its previous size.

TernarySearchMax.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Ternary Search: Find x that maximizes f(x) on continuous [left, right]
 * 
 * @param f - The unimodal function to maximize
 * @param left - Left bound of search interval
 * @param right - Right bound of search interval
 * @param epsilon - Desired precision (default: 1e-9)
 * @returns x value that (approximately) maximizes f
 */
function ternarySearchMax(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    while (right - left > epsilon) {
        // Divide interval into thirds
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        
        // Compare function values at interior points
        if (f(m1) < f(m2)) {
            // Maximum is to the right of m1
            // Eliminate left third: [left, m1]
            left = m1;
        } else {
            // Maximum is to the left of m2
            // Eliminate right third: [m2, right]
            right = m2;
        }
    }
    
    // Return midpoint of final interval
    return (left + right) / 2;
}
 
// Example: Find x that maximizes f(x) = -(x - 7)² + 100
// Maximum should be at x = 7 where f(7) = 100
function exampleFunc(x: number): number {
    return -Math.pow(x - 7, 2) + 100;
}
 
const xMax = ternarySearchMax(exampleFunc, 0, 20);
console.log(`Maximum at x = ${xMax.toFixed(6)}`);        // ~7.000000
console.log(`f(x) = ${exampleFunc(xMax).toFixed(6)}`);    // ~100.000000

Understanding the Division

Finding Minimum — The Dual Case

Finding the minimum of a unimodal function (a "valley" rather than "peak") requires only a small modification: we reverse the comparison.

For Maximum: If f(m1) < f(m2), eliminate left third (go toward higher values) For Minimum: If f(m1) < f(m2), eliminate right third (go toward lower values)

Alternatively, you can reuse the maximum-finding code by negating the function: min f(x) = max -f(x).

TernarySearchMin.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Ternary Search: Find x that minimizes f(x) on continuous [left, right]
 */
function ternarySearchMin(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    while (right - left > epsilon) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        
        // REVERSED COMPARISON for minimum
        if (f(m1) > f(m2)) {
            // Minimum is to the right of m1
            left = m1;
        } else {
            // Minimum is to the left of m2
            right = m2;
        }
    }
    
    return (left + right) / 2;
}
 
// Example: Find x that minimizes f(x) = (x - 4)² + 5
// Minimum should be at x = 4 where f(4) = 5
function convexFunc(x: number): number {
    return Math.pow(x - 4, 2) + 5;
}
 
const xMin = ternarySearchMin(convexFunc, -10, 10);
console.log(`Minimum at x = ${xMin.toFixed(6)}`);        // ~4.000000
console.log(`f(x) = ${convexFunc(xMin).toFixed(6)}`);    // ~5.000000
 
// Alternative: Use max version with negated function
function ternarySearchMaxFromMin(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    return ternarySearchMax(x => -f(x), left, right, epsilon);
}
 
// ternarySearchMaxFromMin returns same result by maximizing -f(x)

Duality Principle

Precision and Termination Strategies

Choosing when to terminate ternary search is subtle. Unlike discrete binary search which naturally terminates, continuous ternary search can refine indefinitely. Here are the main approaches:

Strategy 1: Absolute Epsilon

Terminate when right - left < epsilon for some fixed epsilon (e.g., 1e-9).

Pros: Simple, predictable
Cons: May be too tight for large values (wasted iterations) or too loose for small values (insufficient precision)

Strategy 2: Relative Epsilon

Terminate when (right - left) / |right + left| < epsilon.

Pros: Adapts to the scale of the answer
Cons: Problematic when the answer is near zero

Strategy 3: Fixed Iteration Count

Run exactly N iterations regardless of convergence.

Pros: Predictable runtime, no precision issues
Cons: May over-compute or under-compute depending on N

Strategy 4: Combined Approach

Use relative epsilon with a fallback to absolute epsilon, plus a maximum iteration limit.

TerminationStrategies.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Different termination strategies for ternary search
 
// Strategy 1: Absolute epsilon
function ternarySearchAbsolute(
    f: (x: number) => number,
    left: number,
    right: number,
    absEps: number = 1e-9
): number {
    while (right - left > absEps) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    return (left + right) / 2;
}
 
// Strategy 2: Relative epsilon
function ternarySearchRelative(
    f: (x: number) => number,
    left: number,
    right: number,
    relEps: number = 1e-9
): number {
    while (true) {
        const mid = (left + right) / 2;
        if (Math.abs(mid) < 1e-15 || (right - left) / Math.abs(mid) <= relEps) {
            return mid;
        }
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
}
 
// Strategy 3: Fixed iterations (most common in competitive programming)
function ternarySearchIterations(
    f: (x: number) => number,
    left: number,
    right: number,
    iterations: number = 200  // Usually sufficient for 1e-60 precision
): number {
    for (let i = 0; i < iterations; i++) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    return (left + right) / 2;
}
 
// Strategy 4: Combined approach (production-grade)
function ternarySearchRobust(
    f: (x: number) => number,
    left: number,
    right: number,
    absEps: number = 1e-12,
    relEps: number = 1e-9,
    maxIter: number = 300
): number {
    for (let i = 0; i < maxIter; i++) {
        const width = right - left;
        const mid = (left + right) / 2;
        
        // Check termination conditions
        if (width < absEps) break;
        if (Math.abs(mid) > 1e-15 && width / Math.abs(mid) < relEps) break;
        
        const m1 = left + width / 3;
        const m2 = right - width / 3;
        
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    return (left + right) / 2;
}
 
// Demo: How many iterations for given precision?
console.log("Iterations needed for precision:");
console.log(`ε = 1e-6:  ~${Math.ceil(Math.log(1e6) / Math.log(1.5))} iterations`);
console.log(`ε = 1e-9:  ~${Math.ceil(Math.log(1e9) / Math.log(1.5))} iterations`);
console.log(`ε = 1e-12: ~${Math.ceil(Math.log(1e12) / Math.log(1.5))} iterations`);

Competitive Programming Tip

Convergence Analysis

Each iteration reduces the interval to 2/3 of its previous size. After k iterations:

final_width = initial_width × (2/3)^k

To achieve precision ε:

(2/3)^k < ε / initial_width

k > log(initial_width / ε) / log(3/2)

k > log_{1.5}(initial_width / ε)

For initial_width = 10^9 and ε = 10^-9:

k > log_{1.5}(10^18) ≈ 102 iterations

200 iterations provides a massive safety margin.

Discrete Domain Implementation

When the domain is integers (as in many competitive programming problems), ternary search needs slight modifications:

Use integer arithmetic for m1 and m2
Terminate when right - left < 3 (can't place two distinct interior points)
Check remaining candidates directly

TernarySearchDiscrete.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * Ternary Search for integers: Find integer x that maximizes f(x)
 */
function ternarySearchMaxInt(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    // Phase 1: Ternary search until only a few candidates remain
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        
        if (f(m1) < f(m2)) {
            left = m1;  // Note: m1 itself might be the answer!
        } else {
            right = m2;
        }
    }
    
    // Phase 2: Linear scan of remaining candidates
    let bestX = left;
    let bestVal = f(left);
    
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val > bestVal) {
            bestVal = val;
            bestX = x;
        }
    }
    
    return bestX;
}
 
/**
 * Ternary Search for integers: Find integer x that minimizes f(x)
 */
function ternarySearchMinInt(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        
        if (f(m1) > f(m2)) {  // Reversed for minimum
            left = m1;
        } else {
            right = m2;
        }
    }
    
    let bestX = left;
    let bestVal = f(left);
    
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val < bestVal) {  // Reversed for minimum
            bestVal = val;
            bestX = x;
        }
    }
    
    return bestX;
}
 
// Example: Find k ∈ {0, 1, ..., 100} that minimizes f(k) = |k - 37|
const targetK = ternarySearchMinInt(k => Math.abs(k - 37), 0, 100);
console.log(`Answer: k = ${targetK}`);  // 37
 
// Example: Revenue optimization with discrete prices
// price ∈ {0, 1, 2, ..., 100}, revenue = price × (100 - price)
const optimalPrice = ternarySearchMaxInt(
    price => price * (100 - price),
    0, 100
);
console.log(`Optimal price: ${optimalPrice}`);  // 50

Integer Boundary Subtlety

Golden Section Search — An Optimization

The Golden Ratio

How Golden Section Works

Place probe points at distances gr and 1-gr from the left, where gr = 2 - φ ≈ 0.382:

m1 = left + (right - left) × gr
m2 = left + (right - left) × (1 - gr)

When we eliminate one third and shift the interval:

One of the old probe points falls at exactly the right position to be reused
We only need ONE new function evaluation per iteration

This reduction from 2 to 1 evaluation per iteration halves the number of function calls!

GoldenSectionSearch.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Golden Section Search: Find x that maximizes f(x)
 * More efficient than standard ternary search - uses only 1 evaluation per iteration
 */
function goldenSectionMax(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): number {
    // Golden ratio constants
    const phi = (1 + Math.sqrt(5)) / 2;
    const gr = 2 - phi;  // ≈ 0.381966...
    
    // Initial probe points
    let m1 = left + gr * (right - left);
    let m2 = right - gr * (right - left);
    let f1 = f(m1);
    let f2 = f(m2);
    
    while (right - left > epsilon) {
        if (f1 < f2) {
            // Maximum is in [m1, right]
            left = m1;
            m1 = m2;
            f1 = f2;
            // Reused m1/f1, only compute new m2/f2
            m2 = right - gr * (right - left);
            f2 = f(m2);
        } else {
            // Maximum is in [left, m2]
            right = m2;
            m2 = m1;
            f2 = f1;
            // Reused m2/f2, only compute new m1/f1
            m1 = left + gr * (right - left);
            f1 = f(m1);
        }
    }
    
    return (left + right) / 2;
}
 
// Example: Same function as before
function exampleFunc(x: number): number {
    return -Math.pow(x - 7, 2) + 100;
}
 
// Count function evaluations for comparison
let ternaryEvals = 0;
let goldenEvals = 0;
 
function countedFuncTernary(x: number): number {
    ternaryEvals++;
    return exampleFunc(x);
}
 
function countedFuncGolden(x: number): number {
    goldenEvals++;
    return exampleFunc(x);
}
 
// Run both with same precision
const eps = 1e-9;
ternarySearchMax(countedFuncTernary, 0, 20, eps);
goldenSectionMax(countedFuncGolden, 0, 20, eps);
 
console.log(`Ternary search evaluations: ${ternaryEvals}`);  // ~144
console.log(`Golden section evaluations: ${goldenEvals}`);   // ~74 (roughly half!)

Ternary Search vs. Golden Section Search
Aspect	Ternary Search	Golden Section Search
Evaluations per iteration	2	1 (after initialization)
Interval reduction factor	2/3 ≈ 0.667	1/φ ≈ 0.618
Total evaluations (N iterations)	2N	N + 1
Implementation complexity	Simple	Slightly more complex
Numerical stability	Excellent	Excellent
Best for	General use	Expensive function evaluations

When to Use Golden Section

Complete Reference Implementation

Here's a production-ready ternary search module that handles all common cases:

TernarySearchComplete.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/**
 * Complete Ternary Search Module
 * Production-ready implementations for all common use cases
 */
 
// ========================================
// CONTINUOUS DOMAIN
// ========================================
 
export function ternaryMaxContinuous(
    f: (x: number) => number,
    left: number,
    right: number,
    options: { epsilon?: number; maxIter?: number } = {}
): { x: number; value: number } {
    const { epsilon = 1e-9, maxIter = 300 } = options;
    
    for (let i = 0; i < maxIter && right - left > epsilon; i++) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    
    const x = (left + right) / 2;
    return { x, value: f(x) };
}
 
export function ternaryMinContinuous(
    f: (x: number) => number,
    left: number,
    right: number,
    options: { epsilon?: number; maxIter?: number } = {}
): { x: number; value: number } {
    // Minimize f = maximize -f
    const result = ternaryMaxContinuous(x => -f(x), left, right, options);
    return { x: result.x, value: f(result.x) };
}
 
// ========================================
// DISCRETE (INTEGER) DOMAIN
// ========================================
 
export function ternaryMaxDiscrete(
    f: (x: number) => number,
    left: number,
    right: number
): { x: number; value: number } {
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (f(m1) < f(m2)) left = m1;
        else right = m2;
    }
    
    let bestX = left;
    let bestVal = f(left);
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val > bestVal) {
            bestVal = val;
            bestX = x;
        }
    }
    return { x: bestX, value: bestVal };
}
 
export function ternaryMinDiscrete(
    f: (x: number) => number,
    left: number,
    right: number
): { x: number; value: number } {
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (f(m1) > f(m2)) left = m1;
        else right = m2;
    }
    
    let bestX = left;
    let bestVal = f(left);
    for (let x = left + 1; x <= right; x++) {
        const val = f(x);
        if (val < bestVal) {
            bestVal = val;
            bestX = x;
        }
    }
    return { x: bestX, value: bestVal };
}
 
// ========================================
// GOLDEN SECTION (EFFICIENT FOR EXPENSIVE F)
// ========================================
 
export function goldenMaxContinuous(
    f: (x: number) => number,
    left: number,
    right: number,
    epsilon: number = 1e-9
): { x: number; value: number } {
    const phi = (1 + Math.sqrt(5)) / 2;
    const gr = 2 - phi;
    
    let m1 = left + gr * (right - left);
    let m2 = right - gr * (right - left);
    let f1 = f(m1), f2 = f(m2);
    
    while (right - left > epsilon) {
        if (f1 < f2) {
            left = m1;
            m1 = m2; f1 = f2;
            m2 = right - gr * (right - left);
            f2 = f(m2);
        } else {
            right = m2;
            m2 = m1; f2 = f1;
            m1 = left + gr * (right - left);
            f1 = f(m1);
        }
    }
    
    const x = (left + right) / 2;
    return { x, value: f(x) };
}
 
// ========================================
// USAGE EXAMPLES
// ========================================
 
// Example 1: Continuous maximum
const result1 = ternaryMaxContinuous(x => -(x - 5) ** 2 + 100, 0, 10);
console.log(`Continuous max: x=${result1.x.toFixed(4)}, f(x)=${result1.value.toFixed(4)}`);
 
// Example 2: Discrete minimum
const result2 = ternaryMinDiscrete(x => (x - 42) ** 2, 0, 100);
console.log(`Discrete min: x=${result2.x}, f(x)=${result2.value}`);
 
// Example 3: Golden section for expensive function
let callCount = 0;
function expensiveF(x: number): number {
    callCount++;
    // Simulate expensive computation
    return -x ** 2 + 10 * x - 5;
}
const result3 = goldenMaxContinuous(expensiveF, 0, 10);
console.log(`Golden section: x=${result3.x.toFixed(4)}, calls=${callCount}`);

Common Pitfalls and Debugging

Common Implementation Mistakes

•Wrong comparison direction — For maximum, eliminate where values are LOWER; for minimum, eliminate where values are HIGHER. Easy to flip accidentally.
•Floating-point precision issues — Using == to compare floats. Use epsilon-based comparison or sufficient iterations instead.
•Integer truncation in discrete search — Forgetting Math.floor() for integer division. JavaScript / gives floats even for integers!
•Forgetting the linear scan for discrete — Terminating when right - left < 3 but not checking remaining candidates.
•Assuming strict unimodality — If function has plateaus (f(m1) = f(m2)), the standard comparison may behave unexpectedly. Handle the equality case explicitly.
•Wrong bounds — Starting with bounds that don't contain the optimum. Ternary search won't magically find values outside [left, right].
•Not verifying unimodality — Running ternary search on multi-modal function gives an answer—just not the right one.

Debugging Strategy

When ternary search gives unexpected results:

Verify unimodality — Plot the function or print values at several points. Confirm single peak/valley.
Check bounds — Ensure [left, right] contains the optimum.
Trace first few iterations — Print left, right, m1, m2, f(m1), f(m2) and verify elimination is correct.
Test on known functions — Try f(x) = -(x-5)² where you know the answer should be x=5.
Check termination — Ensure epsilon is appropriate for the problem scale.

Unit Testing Ternary Search

Summary: Ternary Search Mastery

We've covered complete, production-ready implementations of ternary search for finding extrema in unimodal functions.

Key Takeaways

•Core algorithm is simple — Divide into thirds, compare, eliminate one third, repeat.
•Max vs. Min differs only in comparison direction — Or negate the function.
•Termination needs care — Use fixed iterations (200+) in competitive programming; use epsilon with max iterations in production.
•Discrete domains need linear scan — When too few candidates remain, check them directly.
•Golden section halves evaluations — Worth using when function calls are expensive.
•Verify unimodality before trusting results — Multi-modal functions fail silently.

What's Next:

Page Complete

3 / 4