Data Structures & AlgorithmsTernary Search

Ternary Search — Finding Extrema in Unimodal Functions

LevelIntermediate

Duration55 mins

TopicTernary Search

4 / 4

Comparison with Binary Search

Two Powerful Search Algorithms — When to Use Which?

By now, you've mastered two fundamental search algorithms:

Binary Search: Finds elements or boundaries in monotonic sequences, eliminating half the search space per iteration
Ternary Search: Finds extrema in unimodal functions, eliminating one-third the search space per iteration

Both are logarithmic. Both use a divide-and-conquer strategy. But they solve fundamentally different problems. The key to algorithmic mastery is not just knowing how each works, but understanding precisely when each applies.

This page provides a definitive comparison, helping you make the right choice instantly when facing a new problem.

What You Will Learn

By the end of this page, you will be able to classify problems as binary-search-appropriate or ternary-search-appropriate, understand the efficiency trade-offs between them, recognize problems where both could apply and choose the better option, and avoid common misapplications of either algorithm.

Fundamental Differences

Let's establish the core distinctions clearly. These differences stem from the mathematical properties each algorithm exploits.

What Binary Search Exploits

Binary search relies on monotonicity—a sequence or function that is entirely non-decreasing (or non-increasing). The key insight is that a single comparison tells you definitively which half contains the answer.

If searching for value x in sorted array A, comparing A[mid] with x tells you exactly which half to search
If checking if condition P(k) is satisfiable, and P is monotonic, one evaluation tells you which half to explore

What Ternary Search Exploits

Ternary search relies on unimodality—a function that has a single peak (or valley). The key insight is that comparing two points tells you which side of those points the extremum lies.

If f(m1) < f(m2), the maximum is to the right of m1
If f(m1) > f(m2), the maximum is to the left of m2

Binary Search vs. Ternary Search — Fundamental Comparison
Aspect	Binary Search	Ternary Search
Required property	Monotonicity	Unimodality
Query points per iteration	1	2
Elimination per iteration	1/2 (50%)	1/3 (33%)
Comparisons to reach precision ε	log₂(n/ε)	2 × log₁.₅(n/ε) ≈ 2.4 × log₂(n/ε)
Typical problem type	Finding element/boundary	Finding extremum
Works on discrete domains	Yes (natural)	Yes (with modification)
Works on continuous domains	Yes (with precision)	Yes (with precision)

The Factor of 2.4

Ternary search needs roughly 2.4× as many function evaluations as binary search to achieve the same precision. This is because: (1) each iteration makes 2 evaluations instead of 1, and (2) each iteration only shrinks the interval by factor 2/3 instead of 1/2. Mathematically: 2 × log(1.5) / log(2) ≈ 2 × 1.71 / 1 ≈ 2.4.

Problem Structure Recognition

The most important skill is recognizing which algorithm fits a given problem. Here's a decision framework:

Use Binary Search When:

Existence queries — "Is there an element with property X?"
Boundary finding — "What's the first/last element satisfying condition?"
Feasibility checking — "Is it possible to achieve at least value K?" (when feasibility is monotonic in K)
Sorted array operations — Finding elements, insertion points, ranges
Binary predicates — Any yes/no question that transitions exactly once across the domain

Use Ternary Search When:

Optimization — "What value of x maximizes/minimizes f(x)?"
Trade-off problems — "Find the sweet spot where too little and too much both hurt"
Peak/valley finding — In functions without a usable monotonic predicate
Continuous optimization — When derivatives aren't available or practical
Unimodal functions — Any function with exactly one extremum in the domain

Binary Search Problems

•Find 42 in sorted array
•First index where A[i] ≥ 100
•Maximum K such that we can ship all packages in D days with capacity K
•Minimum time to complete all tasks
•Largest square that fits in grid
•Is there a path shorter than X?

Ternary Search Problems

•Price that maximizes revenue
•Angle that maximizes projectile range
•Learning rate that minimizes loss
•Point closest to multiple targets
•Optimal resource allocation
•Peak of a unimodal measurement

The "What Are You Looking For?" Test

Ask yourself: Am I looking for a specific value or boundary (→ binary search), or am I looking for the best/worst value (→ ternary search)? This simple question correctly classifies most problems.

Efficiency Analysis

Let's quantify the efficiency difference precisely.

Binary Search Iterations

To reduce interval from n to ε:

Each iteration halves the interval
After k iterations: interval = n × (1/2)^k
To reach ε: n × (1/2)^k ≤ ε
Solving: k ≥ log₂(n/ε)

Ternary Search Iterations

Each iteration reduces interval to 2/3
After k iterations: interval = n × (2/3)^k
To reach ε: n × (2/3)^k ≤ ε
Solving: k ≥ log_{3/2}(n/ε) = ln(n/ε) / ln(3/2)

Comparison

log_{3/2}(x) = ln(x) / ln(1.5) = ln(x) / 0.405 ≈ 2.47 × ln(x) / ln(2) = 2.47 × log₂(x)

So ternary search needs about 2.47× as many iterations. Combined with 2 evaluations per iteration, that's roughly 4.94× as many function evaluations as binary search for the same precision.

However, golden section search reduces this to about 2.47× as many evaluations (since it reuses one evaluation per iteration).

EfficiencyComparison.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
// Efficiency comparison: Binary vs Ternary search
 
function countBinarySearchIterations(n: number, epsilon: number): number {
    return Math.ceil(Math.log2(n / epsilon));
}
 
function countTernarySearchIterations(n: number, epsilon: number): number {
    return Math.ceil(Math.log(n / epsilon) / Math.log(1.5));
}
 
function countTernarySearchEvaluations(n: number, epsilon: number): number {
    return 2 * countTernarySearchIterations(n, epsilon);
}
 
function countGoldenSectionEvaluations(n: number, epsilon: number): number {
    // Initial 2 evaluations + 1 per iteration thereafter
    const phi = (1 + Math.sqrt(5)) / 2;
    const grRatio = 1 / phi;  // ≈ 0.618
    const iterations = Math.ceil(Math.log(epsilon / n) / Math.log(grRatio));
    return iterations + 1;
}
 
// Compare for different scales
console.log("\nSearch efficiency comparison:\n");
console.log("Interval\tε\t\tBinary\t\tTernary\t\tGolden");
console.log("-".repeat(70));
 
const testCases = [
    [1000, 1],
    [1e6, 1],
    [1e9, 1],
    [100, 1e-6],
    [1e6, 1e-9],
];
 
for (const [n, eps] of testCases) {
    const binary = countBinarySearchIterations(n, eps);
    const ternaryEvals = countTernarySearchEvaluations(n, eps);
    const goldenEvals = countGoldenSectionEvaluations(n, eps);
    
    console.log(
        `${n.toExponential(0)}\t\t${eps.toExponential(0)}\t\t${binary}\t\t${ternaryEvals}\t\t${goldenEvals}`
    );
}
 
// Output:
// Interval   ε        Binary    Ternary   Golden
// ----------------------------------------------------------------------
// 1e+3       1e+0     10        34        18
// 1e+6       1e+0     20        70        36
// 1e+9       1e+0     30        104       53
// 1e+2       1e-6     27        94        49
// 1e+6       1e-9     50        174       89

Practical Implications

The 2-5× efficiency difference is usually acceptable. In competitive programming, even 200 iterations of ternary search complete in microseconds. The key is using the RIGHT algorithm for your problem type—using binary search on a unimodal function doesn't work at all, which is infinitely worse than a 2× slowdown.

When Both Could Apply

Interestingly, some problems can be solved by either algorithm. Understanding these cases deepens your algorithmic intuition.

Case 1: Peak Element in Array

Given an array where elements increase then decrease (mountain array), find the peak.

Ternary search approach: Treat array index as domain, array value as function. Find index that maximizes value.

Binary search approach: At index i, check if A[i] < A[i+1]. This predicate is false after the peak. Binary search finds the transition point.

Which is better? Binary search. It needs half as many comparisons and leverages the hidden monotonic predicate.

Case 2: Minimum Distance to a Point

Given points on a line, find position that minimizes sum of distances to all points.

Ternary search approach: The sum-of-distances function is convex (unimodal with minimum). Ternary search finds the minimum.

Binary search approach: The optimal position is the median. Binary search can find the median in a sorted list.

Which is better? Depends on the representation. If distances are given as a function, ternary search. If points are listed, just compute the median directly.

Case 3: Binary Search on Answer + Feasibility Check

Many optimization problems can be transformed: instead of directly finding optimal X, binary search on "is X achievable?" which is monotonic.

If the predicate is easy to compute, binary search on the answer space is more efficient. If the predicate is expensive but the objective function is unimodal, ternary search may be simpler.

PeakElementBothWays.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
// Finding peak element: Both approaches work, binary search is better
 
const mountainArray = [1, 4, 7, 11, 15, 13, 8, 4, 1];
 
// Approach 1: Ternary Search (works but less efficient)
function peakTernary(arr: number[]): number {
    let left = 0, right = arr.length - 1;
    let iterations = 0;
    
    while (right - left >= 3) {
        iterations++;
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (arr[m1] < arr[m2]) left = m1;
        else right = m2;
    }
    
    // Linear scan remaining
    let peakIdx = left;
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] > arr[peakIdx]) peakIdx = i;
        iterations++;
    }
    
    console.log(`Ternary: ${iterations} iterations`);
    return peakIdx;
}
 
// Approach 2: Binary Search with monotonic predicate (better)
function peakBinary(arr: number[]): number {
    let left = 0, right = arr.length - 1;
    let iterations = 0;
    
    while (left < right) {
        iterations++;
        const mid = left + Math.floor((right - left) / 2);
        
        // Monotonic predicate: "Is mid in the ascending region?"
        // Ascending region: arr[mid] < arr[mid + 1]
        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;  // Peak is to the right
        } else {
            right = mid;  // Peak is at mid or to the left
        }
    }
    
    console.log(`Binary: ${iterations} iterations`);
    return left;
}
 
console.log("Array:", mountainArray);
console.log("\nPeak (ternary):", peakTernary(mountainArray));
console.log("Peak (binary):", peakBinary(mountainArray));
 
// Output:
// Array: [1, 4, 7, 11, 15, 13, 8, 4, 1]
// Ternary: 4 iterations
// Peak (ternary): 4
// Binary: 3 iterations
// Peak (binary): 4
//
// Binary search wins with fewer iterations!

The Hidden Monotonicity Rule

When a problem looks like it needs ternary search, always ask: "Is there a hidden monotonic predicate?" If you can find one, binary search will be more efficient. Examples: 'Am I in the ascending region?' or 'Is the slope positive?'

Common Misapplications

Mistakes to Avoid

•Using binary search for optimization — "Find x that maximizes f(x)" on a unimodal function. Binary search needs a target value or monotonic predicate, not an objective function alone.
•Using ternary search for boundary finding — "Find first index where condition holds." If the condition is monotonic, binary search is simpler and faster.
•Using ternary search on multi-modal functions — The algorithm assumes exactly one extremum. Multiple peaks cause incorrect results.
•Ignoring hidden monotonicity — Many 'find peak' problems have a monotonic predicate. Check before defaulting to ternary search.
•Ternary search for discrete sorted array search — Looking for a specific value in a sorted array? Binary search is the answer.
•Binary search on non-monotonic predicates — If the condition can flip back and forth (true, false, true), binary search fails.

The Cost of Misapplication

Using binary search where ternary is needed → Wrong answer (algorithm doesn't apply)
Using ternary search where binary is sufficient → Correct but ~2.5× slower
Using either on inappropriate problems (multi-modal, non-monotonic) → Wrong answer

The asymmetry is important: using the wrong algorithm entirely gives wrong answers, while using a sub-optimal but applicable algorithm just costs some performance.

Correctness Before Efficiency

First ensure the algorithm is applicable (correct problem type). Then optimize for efficiency (choose better variant). A fast wrong answer is useless; a slow correct answer is still useful.

Decision Framework

Here's a systematic approach to choosing between binary and ternary search:

Step 1: Identify the Goal

Finding a specific element or boundary? → Lean toward binary search
Finding an optimal (maximum/minimum) value? → Lean toward ternary search

Step 2: Analyze the Structure

Is there a monotonic predicate? → Binary search is applicable
Is the objective function unimodal? → Ternary search is applicable
Neither? → Consider other algorithms

Step 3: If Both Apply, Compare

Is computing the predicate cheap? → Binary search is usually better
Is the predicate complex but function evaluation easy? → Consider either
Default to binary search if a monotonic predicate exists (more efficient)

Step 4: Verify Problem Constraints

Multi-modal function? → Neither works directly (need different approach)
Non-monotonic predicate? → Binary search doesn't apply
Continuous domain with precision requirements? → Both need epsilon handling

Converting Mermaid diagram...

Practical Examples Side-by-Side

Let's compare the algorithms on related problems to reinforce the distinction.

Problem A (Binary Search): Find index of value 15 in sorted array.

Problem B (Ternary Search): Find index of maximum value in unimodal array.

Both involve finding an index, but the nature of what we're finding differs.

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
// Problem A: Find value in sorted array (Binary Search)
function findValue(arr: number[], target: number): number {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
 
// Problem B: Find peak in unimodal array (Ternary Search)
function findPeak(arr: number[]): number {
    let left = 0, right = arr.length - 1;
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (arr[m1] < arr[m2]) left = m1;
        else right = m2;
    }
    let peak = left;
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] > arr[peak]) peak = i;
    }
    return peak;
}
 
const sorted = [3, 7, 12, 15, 20, 28, 35];
const unimodal = [3, 7, 12, 20, 15, 10, 5];
 
console.log("Find 15 in sorted:", findValue(sorted, 15));  // 3
console.log("Peak in unimodal:", findPeak(unimodal));      // 3

Summary: Mastering Both Algorithms

You now have a complete understanding of when to use binary search vs. ternary search. Here's the definitive comparison:

Definitive Binary vs. Ternary Comparison
Criterion	Binary Search	Ternary Search
Required structure	Monotonicity	Unimodality
Goal	Find element/boundary	Find extremum
Queries per iteration	1	2 (or 1 with golden section)
Reduction factor	1/2	1/3 (or 1/φ with golden section)
Efficiency	log₂(n)	~2.4 × log₂(n)
Typical questions	"Where is X?" "First/last satisfying?"	"What maximizes/minimizes?"
Failure mode if misapplied	Incorrect elimination	Incorrect elimination

Key Takeaways

•Different problems, different tools — Binary search for boundaries in monotonic structures; ternary search for extrema in unimodal functions.
•Binary search is more efficient — When applicable, prefer binary search (~2.5× fewer evaluations).
•Look for hidden monotonicity — Many 'find peak' problems have a monotonic predicate; use binary search.
•Correctness first — Ensure the algorithm applies before worrying about efficiency.
•Both have O(log n) complexity — The constant factor difference is usually acceptable.
•Practice recognition — The key skill is identifying problem structure, not memorizing algorithms.

Congratulations on Completing This Module!

You now have mastery of ternary search—from understanding when binary search fails, through the mathematical foundation of unimodality, to complete implementations and efficiency analysis. Combined with your binary search knowledge, you're equipped to tackle a wide range of search and optimization problems.

What's Next in Chapter 17:

The next module covers interpolation search, which uses the distribution of values to make smarter guesses than binary search's midpoint. You'll see how additional assumptions about data can enable even faster search under the right conditions.

Module Complete

You've mastered ternary search and understand its relationship to binary search. You can now recognize which algorithm applies to a given problem, implement both correctly, and make informed efficiency trade-offs. This completes Module 8: Ternary Search (Conceptual).

4 / 4

Loading learning content...

Data Structures & AlgorithmsTernary Search

Ternary Search — Finding Extrema in Unimodal Functions

LevelIntermediate

Duration55 mins

TopicTernary Search

4 / 4

Comparison with Binary Search

Two Powerful Search Algorithms — When to Use Which?

By now, you've mastered two fundamental search algorithms:

Binary Search: Finds elements or boundaries in monotonic sequences, eliminating half the search space per iteration
Ternary Search: Finds extrema in unimodal functions, eliminating one-third the search space per iteration

This page provides a definitive comparison, helping you make the right choice instantly when facing a new problem.

What You Will Learn

Fundamental Differences

Let's establish the core distinctions clearly. These differences stem from the mathematical properties each algorithm exploits.

What Binary Search Exploits

If searching for value x in sorted array A, comparing A[mid] with x tells you exactly which half to search
If checking if condition P(k) is satisfiable, and P is monotonic, one evaluation tells you which half to explore

What Ternary Search Exploits

Ternary search relies on unimodality—a function that has a single peak (or valley). The key insight is that comparing two points tells you which side of those points the extremum lies.

If f(m1) < f(m2), the maximum is to the right of m1
If f(m1) > f(m2), the maximum is to the left of m2

Binary Search vs. Ternary Search — Fundamental Comparison
Aspect	Binary Search	Ternary Search
Required property	Monotonicity	Unimodality
Query points per iteration	1	2
Elimination per iteration	1/2 (50%)	1/3 (33%)
Comparisons to reach precision ε	log₂(n/ε)	2 × log₁.₅(n/ε) ≈ 2.4 × log₂(n/ε)
Typical problem type	Finding element/boundary	Finding extremum
Works on discrete domains	Yes (natural)	Yes (with modification)
Works on continuous domains	Yes (with precision)	Yes (with precision)

The Factor of 2.4

Problem Structure Recognition

The most important skill is recognizing which algorithm fits a given problem. Here's a decision framework:

Use Binary Search When:

Existence queries — "Is there an element with property X?"
Boundary finding — "What's the first/last element satisfying condition?"
Feasibility checking — "Is it possible to achieve at least value K?" (when feasibility is monotonic in K)
Sorted array operations — Finding elements, insertion points, ranges
Binary predicates — Any yes/no question that transitions exactly once across the domain

Use Ternary Search When:

Optimization — "What value of x maximizes/minimizes f(x)?"
Trade-off problems — "Find the sweet spot where too little and too much both hurt"
Peak/valley finding — In functions without a usable monotonic predicate
Continuous optimization — When derivatives aren't available or practical
Unimodal functions — Any function with exactly one extremum in the domain

Binary Search Problems

•Find 42 in sorted array
•First index where A[i] ≥ 100
•Maximum K such that we can ship all packages in D days with capacity K
•Minimum time to complete all tasks
•Largest square that fits in grid
•Is there a path shorter than X?

Ternary Search Problems

•Price that maximizes revenue
•Angle that maximizes projectile range
•Learning rate that minimizes loss
•Point closest to multiple targets
•Optimal resource allocation
•Peak of a unimodal measurement

The "What Are You Looking For?" Test

Efficiency Analysis

Let's quantify the efficiency difference precisely.

Binary Search Iterations

To reduce interval from n to ε:

Each iteration halves the interval
After k iterations: interval = n × (1/2)^k
To reach ε: n × (1/2)^k ≤ ε
Solving: k ≥ log₂(n/ε)

Ternary Search Iterations

Each iteration reduces interval to 2/3
After k iterations: interval = n × (2/3)^k
To reach ε: n × (2/3)^k ≤ ε
Solving: k ≥ log_{3/2}(n/ε) = ln(n/ε) / ln(3/2)

Comparison

log_{3/2}(x) = ln(x) / ln(1.5) = ln(x) / 0.405 ≈ 2.47 × ln(x) / ln(2) = 2.47 × log₂(x)

So ternary search needs about 2.47× as many iterations. Combined with 2 evaluations per iteration, that's roughly 4.94× as many function evaluations as binary search for the same precision.

However, golden section search reduces this to about 2.47× as many evaluations (since it reuses one evaluation per iteration).

EfficiencyComparison.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
// Efficiency comparison: Binary vs Ternary search
 
function countBinarySearchIterations(n: number, epsilon: number): number {
    return Math.ceil(Math.log2(n / epsilon));
}
 
function countTernarySearchIterations(n: number, epsilon: number): number {
    return Math.ceil(Math.log(n / epsilon) / Math.log(1.5));
}
 
function countTernarySearchEvaluations(n: number, epsilon: number): number {
    return 2 * countTernarySearchIterations(n, epsilon);
}
 
function countGoldenSectionEvaluations(n: number, epsilon: number): number {
    // Initial 2 evaluations + 1 per iteration thereafter
    const phi = (1 + Math.sqrt(5)) / 2;
    const grRatio = 1 / phi;  // ≈ 0.618
    const iterations = Math.ceil(Math.log(epsilon / n) / Math.log(grRatio));
    return iterations + 1;
}
 
// Compare for different scales
console.log("\nSearch efficiency comparison:\n");
console.log("Interval\tε\t\tBinary\t\tTernary\t\tGolden");
console.log("-".repeat(70));
 
const testCases = [
    [1000, 1],
    [1e6, 1],
    [1e9, 1],
    [100, 1e-6],
    [1e6, 1e-9],
];
 
for (const [n, eps] of testCases) {
    const binary = countBinarySearchIterations(n, eps);
    const ternaryEvals = countTernarySearchEvaluations(n, eps);
    const goldenEvals = countGoldenSectionEvaluations(n, eps);
    
    console.log(
        `${n.toExponential(0)}\t\t${eps.toExponential(0)}\t\t${binary}\t\t${ternaryEvals}\t\t${goldenEvals}`
    );
}
 
// Output:
// Interval   ε        Binary    Ternary   Golden
// ----------------------------------------------------------------------
// 1e+3       1e+0     10        34        18
// 1e+6       1e+0     20        70        36
// 1e+9       1e+0     30        104       53
// 1e+2       1e-6     27        94        49
// 1e+6       1e-9     50        174       89

Practical Implications

When Both Could Apply

Interestingly, some problems can be solved by either algorithm. Understanding these cases deepens your algorithmic intuition.

Case 1: Peak Element in Array

Given an array where elements increase then decrease (mountain array), find the peak.

Ternary search approach: Treat array index as domain, array value as function. Find index that maximizes value.

Binary search approach: At index i, check if A[i] < A[i+1]. This predicate is false after the peak. Binary search finds the transition point.

Which is better? Binary search. It needs half as many comparisons and leverages the hidden monotonic predicate.

Case 2: Minimum Distance to a Point

Given points on a line, find position that minimizes sum of distances to all points.

Ternary search approach: The sum-of-distances function is convex (unimodal with minimum). Ternary search finds the minimum.

Binary search approach: The optimal position is the median. Binary search can find the median in a sorted list.

Which is better? Depends on the representation. If distances are given as a function, ternary search. If points are listed, just compute the median directly.

Case 3: Binary Search on Answer + Feasibility Check

Many optimization problems can be transformed: instead of directly finding optimal X, binary search on "is X achievable?" which is monotonic.

If the predicate is easy to compute, binary search on the answer space is more efficient. If the predicate is expensive but the objective function is unimodal, ternary search may be simpler.

PeakElementBothWays.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
// Finding peak element: Both approaches work, binary search is better
 
const mountainArray = [1, 4, 7, 11, 15, 13, 8, 4, 1];
 
// Approach 1: Ternary Search (works but less efficient)
function peakTernary(arr: number[]): number {
    let left = 0, right = arr.length - 1;
    let iterations = 0;
    
    while (right - left >= 3) {
        iterations++;
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (arr[m1] < arr[m2]) left = m1;
        else right = m2;
    }
    
    // Linear scan remaining
    let peakIdx = left;
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] > arr[peakIdx]) peakIdx = i;
        iterations++;
    }
    
    console.log(`Ternary: ${iterations} iterations`);
    return peakIdx;
}
 
// Approach 2: Binary Search with monotonic predicate (better)
function peakBinary(arr: number[]): number {
    let left = 0, right = arr.length - 1;
    let iterations = 0;
    
    while (left < right) {
        iterations++;
        const mid = left + Math.floor((right - left) / 2);
        
        // Monotonic predicate: "Is mid in the ascending region?"
        // Ascending region: arr[mid] < arr[mid + 1]
        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;  // Peak is to the right
        } else {
            right = mid;  // Peak is at mid or to the left
        }
    }
    
    console.log(`Binary: ${iterations} iterations`);
    return left;
}
 
console.log("Array:", mountainArray);
console.log("\nPeak (ternary):", peakTernary(mountainArray));
console.log("Peak (binary):", peakBinary(mountainArray));
 
// Output:
// Array: [1, 4, 7, 11, 15, 13, 8, 4, 1]
// Ternary: 4 iterations
// Peak (ternary): 4
// Binary: 3 iterations
// Peak (binary): 4
//
// Binary search wins with fewer iterations!

The Hidden Monotonicity Rule

Common Misapplications

Mistakes to Avoid

•Using binary search for optimization — "Find x that maximizes f(x)" on a unimodal function. Binary search needs a target value or monotonic predicate, not an objective function alone.
•Using ternary search for boundary finding — "Find first index where condition holds." If the condition is monotonic, binary search is simpler and faster.
•Using ternary search on multi-modal functions — The algorithm assumes exactly one extremum. Multiple peaks cause incorrect results.
•Ignoring hidden monotonicity — Many 'find peak' problems have a monotonic predicate. Check before defaulting to ternary search.
•Ternary search for discrete sorted array search — Looking for a specific value in a sorted array? Binary search is the answer.
•Binary search on non-monotonic predicates — If the condition can flip back and forth (true, false, true), binary search fails.

The Cost of Misapplication

Using binary search where ternary is needed → Wrong answer (algorithm doesn't apply)
Using ternary search where binary is sufficient → Correct but ~2.5× slower
Using either on inappropriate problems (multi-modal, non-monotonic) → Wrong answer

The asymmetry is important: using the wrong algorithm entirely gives wrong answers, while using a sub-optimal but applicable algorithm just costs some performance.

Correctness Before Efficiency

First ensure the algorithm is applicable (correct problem type). Then optimize for efficiency (choose better variant). A fast wrong answer is useless; a slow correct answer is still useful.

Decision Framework

Here's a systematic approach to choosing between binary and ternary search:

Step 1: Identify the Goal

Finding a specific element or boundary? → Lean toward binary search
Finding an optimal (maximum/minimum) value? → Lean toward ternary search

Step 2: Analyze the Structure

Is there a monotonic predicate? → Binary search is applicable
Is the objective function unimodal? → Ternary search is applicable
Neither? → Consider other algorithms

Step 3: If Both Apply, Compare

Is computing the predicate cheap? → Binary search is usually better
Is the predicate complex but function evaluation easy? → Consider either
Default to binary search if a monotonic predicate exists (more efficient)

Step 4: Verify Problem Constraints

Multi-modal function? → Neither works directly (need different approach)
Non-monotonic predicate? → Binary search doesn't apply
Continuous domain with precision requirements? → Both need epsilon handling

Converting Mermaid diagram...

Practical Examples Side-by-Side

Let's compare the algorithms on related problems to reinforce the distinction.

Problem A (Binary Search): Find index of value 15 in sorted array.

Problem B (Ternary Search): Find index of maximum value in unimodal array.

Both involve finding an index, but the nature of what we're finding differs.

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
// Problem A: Find value in sorted array (Binary Search)
function findValue(arr: number[], target: number): number {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
 
// Problem B: Find peak in unimodal array (Ternary Search)
function findPeak(arr: number[]): number {
    let left = 0, right = arr.length - 1;
    while (right - left >= 3) {
        const m1 = left + Math.floor((right - left) / 3);
        const m2 = right - Math.floor((right - left) / 3);
        if (arr[m1] < arr[m2]) left = m1;
        else right = m2;
    }
    let peak = left;
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] > arr[peak]) peak = i;
    }
    return peak;
}
 
const sorted = [3, 7, 12, 15, 20, 28, 35];
const unimodal = [3, 7, 12, 20, 15, 10, 5];
 
console.log("Find 15 in sorted:", findValue(sorted, 15));  // 3
console.log("Peak in unimodal:", findPeak(unimodal));      // 3

Summary: Mastering Both Algorithms

You now have a complete understanding of when to use binary search vs. ternary search. Here's the definitive comparison:

Definitive Binary vs. Ternary Comparison
Criterion	Binary Search	Ternary Search
Required structure	Monotonicity	Unimodality
Goal	Find element/boundary	Find extremum
Queries per iteration	1	2 (or 1 with golden section)
Reduction factor	1/2	1/3 (or 1/φ with golden section)
Efficiency	log₂(n)	~2.4 × log₂(n)
Typical questions	"Where is X?" "First/last satisfying?"	"What maximizes/minimizes?"
Failure mode if misapplied	Incorrect elimination	Incorrect elimination

Key Takeaways

•Different problems, different tools — Binary search for boundaries in monotonic structures; ternary search for extrema in unimodal functions.
•Binary search is more efficient — When applicable, prefer binary search (~2.5× fewer evaluations).
•Look for hidden monotonicity — Many 'find peak' problems have a monotonic predicate; use binary search.
•Correctness first — Ensure the algorithm applies before worrying about efficiency.
•Both have O(log n) complexity — The constant factor difference is usually acceptable.
•Practice recognition — The key skill is identifying problem structure, not memorizing algorithms.

Congratulations on Completing This Module!

What's Next in Chapter 17:

Module Complete

4 / 4