Data Structures & AlgorithmsTernary Search

Ternary Search — Finding Extrema in Unimodal Functions

LevelIntermediate

Duration55 mins

TopicTernary Search

2 / 4

Unimodal Functions

The Shape of Searchable Problems

In the previous page, we discovered that binary search fails when we need to find the maximum or minimum of a function without a monotonic structure. We introduced ternary search as the solution, but we glossed over a critical requirement: the function must be unimodal.

But what exactly does 'unimodal' mean? Why is unimodality so important? And how do you recognize when a problem's underlying function is unimodal?

This page answers these questions comprehensively. By the end, you'll have deep intuition for unimodal functions—their formal definition, their geometric properties, how to identify them in disguised forms, and why they're the perfect match for ternary search.

What You Will Learn

By the end of this page, you will understand the formal definition of unimodal functions, visualize their characteristic shape, distinguish them from other function types, and recognize unimodality in practical optimization problems.

Formal Definition of Unimodality

Let's establish rigorous definitions. Mathematics prizes precision, and algorithmic correctness depends on it.

Definition (Unimodal Function — Maximum Case)

A function f: [a, b] → ℝ is unimodal with a maximum if there exists a point x* ∈ [a, b] such that:

For all x₁, x₂ ∈ [a, x*] where x₁ < x₂: f(x₁) ≤ f(x₂) (non-decreasing on [a, x*])
For all x₁, x₂ ∈ [x*, b] where x₁ < x₂: f(x₁) ≥ f(x₂) (non-increasing on [x*, b])

The point x* is called the mode of the function.

Definition (Unimodal Function — Minimum Case)

Similarly, a function f: [a, b] → ℝ is unimodal with a minimum if there exists a point x* ∈ [a, b] such that:

For all x₁, x₂ ∈ [a, x*] where x₁ < x₂: f(x₁) ≥ f(x₂) (non-increasing on [a, x*])
For all x₁, x₂ ∈ [x*, b] where x₁ < x₂: f(x₁) ≤ f(x₂) (non-decreasing on [x*, b])

This is the "valley" case, dual to the "peak" case above.

Strict vs. Non-Strict Unimodality

The definitions above use ≤ and ≥ (non-strict). In strictly unimodal functions, we use < and > (strict), meaning the function is strictly increasing before x* and strictly decreasing after. Strict unimodality guarantees a unique maximum; non-strict unimodality allows plateaus where f(x) = f(x*) for a range of x values.

Intuitive Interpretation

Think of a unimodal function as having a single "mode" — a single peak (for maximum) or valley (for minimum). You can start at the left boundary, ascend continuously to the peak, then descend continuously to the right boundary. At no point do you encounter a second climb or a secondary peak.

Key Properties of Unimodal Functions

Single Extremum — Exactly one global maximum (or minimum) in the interval
No Local Traps — No local maxima other than the global maximum (critical for search algorithms!)
Monotonic Regions — The domain partitions into two monotonic regions separated by the mode
Comparison-Based Direction — Comparing two points tells you which direction leads toward the extremum

Unimodal Function Properties
Property	Maximum Case	Minimum Case
Shape	Single peak (∧-shaped)	Single valley (∨-shaped)
Left of mode	Non-decreasing	Non-increasing
Right of mode	Non-increasing	Non-decreasing
Mode location	Global maximum	Global minimum
Ternary search finds	Maximum point	Minimum point

Visualizing Unimodal Functions

Let's build visual intuition with concrete examples. Each example illustrates the unimodal shape and how it manifests in different mathematical contexts.

Example 1: Quadratic Function (Parabola)

The most classic unimodal function is the quadratic:

f(x) = -x² + 4x + 1 — Opens downward, maximum at x = 2
f(x) = x² - 6x + 8 — Opens upward, minimum at x = 3

These are textbook examples: smooth, symmetric, and obviously unimodal.

Example 2: Gaussian (Bell Curve)

f(x) = e^(-x²)

The Gaussian is unimodal with maximum at x = 0. It rises smoothly from the left, peaks, then falls smoothly to the right. Unlike the parabola, it's not symmetric in its rate of change, but it is unimodal.

Example 3: Piecewise Linear (Triangle)

f(x) = { x           if x ≤ 5
       { 10 - x      if x > 5

This forms a triangle peak at x = 5. Despite being non-smooth (derivative undefined at x = 5), it's still unimodal. Ternary search handles this perfectly.

UnimodalExamples.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
// Examples of unimodal functions and where they peak/valley
 
// Example 1: Quadratic - Maximum at x = 2
function quadraticMax(x: number): number {
    return -x * x + 4 * x + 1;  // = -(x-2)² + 5, max at x=2
}
 
// Example 2: Quadratic - Minimum at x = 3
function quadraticMin(x: number): number {
    return x * x - 6 * x + 8;  // = (x-3)² - 1, min at x=3
}
 
// Example 3: Gaussian - Maximum at x = 0
function gaussian(x: number): number {
    return Math.exp(-x * x);
}
 
// Example 4: Triangle Peak - Maximum at x = 5
function trianglePeak(x: number): number {
    if (x <= 5) return x;
    return 10 - x;
}
 
// Example 5: Triangle Valley - Minimum at x = 3
function triangleValley(x: number): number {
    if (x <= 3) return 3 - x;
    return x - 3;
}
 
// Example 6: Product Revenue Model
// Revenue = price × demand, where demand = 100 - price
// Revenue = price × (100 - price) = -price² + 100*price
// This is unimodal with max at price = 50
function revenue(price: number): number {
    const demand = Math.max(0, 100 - price);
    return price * demand;
}
 
// Visualization helper: sample function in interval
function sampleFunction(
    f: (x: number) => number, 
    start: number, 
    end: number, 
    samples: number = 10
): void {
    console.log("x\t\tf(x)");
    console.log("-".repeat(25));
    for (let i = 0; i <= samples; i++) {
        const x = start + (end - start) * (i / samples);
        console.log(`${x.toFixed(2)}\t\t${f(x).toFixed(4)}`);
    }
}
 
// Demo: Quadratic maximum
console.log("
Quadratic Maximum (peak at x=2):");
sampleFunction(quadraticMax, 0, 4);
 
// Demo: Revenue (peak at price=50)
console.log("
Revenue Function (peak at price=50):");
sampleFunction(revenue, 0, 100);

Smoothness Not Required

Notice that the triangle function has a "corner" — the derivative doesn't exist at the peak. This is perfectly fine for ternary search. Unimodality is about the global shape (one peak or valley), not local smoothness. This makes ternary search applicable to a wide range of practical problems.

Non-Unimodal Functions — What Breaks

Understanding what makes a function not unimodal is crucial. When unimodality fails, ternary search can return incorrect results. Let's examine the failure modes:

Multi-Modal Functions

A multi-modal function has multiple peaks (or valleys). Examples:

f(x) = sin(x) over [0, 4π] — Multiple peaks and valleys
f(x) = x⁴ - 3x² + 1 — Creates two peaks and a valley
Optimization landscapes in neural networks — Notoriously multi-modal

Why Ternary Search Fails on Multi-Modal Functions

Consider f(x) = sin(x) over [0, 2π] where there's a maximum near π/2 and a minimum near 3π/2. If ternary search happens to compare two points that are both on the "descending" side of one peak but on opposite sides of the global maximum, it will make an incorrect elimination.

More concretely:

Let m1 = π and m2 = 4π/3 (both after the first peak)
f(m1) = 0, f(m2) ≈ -0.87
Since f(m1) > f(m2), ternary search eliminates the right third
But this elimination might discard the search space containing the global maximum if we started with different bounds!

Function Types Where Ternary Search Fails

•Multi-Modal (Multiple Peaks) — sin(x), polynomial oscillations, real-world optimization surfaces. Ternary search finds a local extremum, not necessarily the global one.
•Monotonic Functions — Purely increasing or decreasing functions technically don't have an interior maximum. The 'peak' is at a boundary. Ternary search may find the boundary, but binary search is more efficient for monotonic constraints.
•Constant Functions — If f(x) = c for all x, every point is equally good. Ternary search works but provides no meaningful answer beyond 'any x is fine.'
•Discontinuous Functions — Jumps can trick the comparison logic. If f(m1) and f(m2) are on opposite sides of a discontinuity, the direction inference may be wrong.
•Functions with Plateaus — Extended flat regions (f(x) = c for x ∈ [a, b]) can cause ternary search to converge slowly or get stuck, though technically it still works for non-strict unimodality.

MultiModalFailure.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
// Demonstration: Ternary search on multi-modal function
// THIS IS BROKEN - shown for educational purposes
 
function multiModal(x: number): number {
    // Two peaks: one near x=1, one near x=4
    return -((x - 1) ** 2) * ((x - 4) ** 2) + 10;
    // Peaks at x=1 and x=4, valley at x=2.5
}
 
function brokenTernarySearch(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    const epsilon = 1e-6;
    
    while (right - left > epsilon) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        
        if (f(m1) < f(m2)) {
            left = m1;  // Assumes peak is right of m1
        } else {
            right = m2;  // Assumes peak is left of m2
        }
    }
    
    return (left + right) / 2;
}
 
// Different search ranges give different (wrong) answers!
console.log("Searching [0, 5]:", brokenTernarySearch(multiModal, 0, 5));
console.log("Searching [0, 2.5]:", brokenTernarySearch(multiModal, 0, 2.5));
console.log("Searching [2.5, 5]:", brokenTernarySearch(multiModal, 2.5, 5));
 
// The function has peaks at x=1 and x=4
// Depending on initial bounds and comparisons, we might find either!
// This demonstrates why unimodality is REQUIRED

Silent Failures Are Dangerous

The worst aspect of running ternary search on non-unimodal functions is that it produces an answer—just not necessarily the correct one. Unlike a crash or exception, the algorithm completes normally. You must verify unimodality before trusting ternary search results.

Convexity and Concavity — Related Concepts

If you've studied calculus or optimization, you've likely encountered the terms convex and concave. These are closely related to unimodality, and understanding the connection deepens your algorithmic intuition.

Definition Recap

Convex function: For any two points x₁, x₂ and any λ ∈ [0, 1]: f(λx₁ + (1-λ)x₂) ≤ λf(x₁) + (1-λ)f(x₂)

Geometrically: the line segment connecting any two points on the graph lies above the graph. The function "curves upward" like a bowl.
Concave function: The inequality is reversed: f(λx₁ + (1-λ)x₂) ≥ λf(x₁) + (1-λ)f(x₂)

The line segment lies below the graph. The function "curves downward" like a dome.

The Key Insight

Every convex function is unimodal with a minimum (it has a single valley)
Every concave function is unimodal with a maximum (it has a single peak)

But the reverse is not true! Unimodality is a weaker condition than convexity/concavity. A function can be unimodal without being convex or concave.

Why Does This Matter?

Convex optimization is a massive field with powerful algorithms (gradient descent, Newton's method, interior point methods). If your function is convex, you have access to these tools and strong guarantees about global optimality.

Ternary search, however, works on the broader class of unimodal functions—including those that are neither convex nor concave. This makes it valuable when:

The function doesn't have derivatives (or they're hard to compute)
You only have black-box access to the function (can evaluate but not differentiate)
The function is piecewise linear or has corners
You want a simple, robust algorithm without convexity assumptions

Convexity, Concavity, and Unimodality
Function Class	Bowl/Dome Shape	Unimodal?	Ternary Search?	Gradient-Based?
Strictly Convex	U-shaped (bowl)	✅ Yes (minimum)	✅ Works	✅ Guaranteed global min
Strictly Concave	∩-shaped (dome)	✅ Yes (maximum)	✅ Works	✅ Guaranteed global max
Unimodal (not convex)	Single peak/valley	✅ Yes	✅ Works	⚠️ May work, no guarantee
Multi-modal	Multiple peaks	❌ No	❌ Fails	⚠️ Finds local extremum only

The Hierarchy of Function Classes

Strictly Convex ⊂ Convex ⊂ Unimodal (for minima). Similarly, Strictly Concave ⊂ Concave ⊂ Unimodal (for maxima). Ternary search works on the broadest class here, but stronger problem structure enables more efficient algorithms.

Recognizing Unimodality in Problems

Competitive programming problems and real-world optimization scenarios rarely say "this function is unimodal." You need to recognize the property from problem structure. Here are patterns and heuristics:

Pattern 1: Physical Systems

Many physical quantities are unimodal:

Projectile range vs. launch angle (max at ~45°)
Signal strength vs. frequency (peaks at resonance)
Efficiency vs. operating point (optimal load balancing)

Physics tends to produce smooth, well-behaved functions with single optima.

Pattern 2: Economic Models

Revenue = Price × Quantity, where Quantity decreases with Price → Unimodal with a maximum
Cost functions often have decreasing returns → Convex (unimodal minimum)
Profit = Revenue - Cost → Often unimodal (sum of concave and convex)

Pattern 3: "Too Little / Too Much" Problems

When the problem involves a trade-off where:

Too small a value is bad (insufficient resources, capacity, etc.)
Too large a value is also bad (overhead, diminishing returns, constraints)
There's a sweet spot in between

...the function is likely unimodal.

Pattern 4: Squared Terms Without Higher Powers

Functions involving (x - a)² terms without higher-order terms are often unimodal:

f(x) = -(x - 5)² → Unimodal max at 5
f(x) = (x - 3)² + (x - 7)² → Unimodal (sum of convex functions is convex)

Pattern 5: Binary Search Predicate Hint

If you can phrase a related yes/no question that's monotonic:

"Is it possible to achieve at least value V?" → If this is monotonic in V
Then the optimal V is at the boundary, suggesting underlying unimodality

Quick Unimodality Checklist

•Single Optimal Point — The problem asks for ONE best value, not multiple good values
•Trade-off Structure — Increasing the parameter helps up to a point, then hurts
•No Oscillations — The objective doesn't go up-down-up-down with the parameter
•Smooth Problem Domain — Real-valued rather than combinatorial structure
•Physical Intuition — Real-world analogs suggest a single optimum

UnimodalRecognition.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
// Common problem patterns that produce unimodal functions
 
// Pattern 1: Minimizing maximum difference (often unimodal in the answer)
function minMaxDifference(speeds: number[], targetTime: number): number {
    // If we allocate 'capacity' to everyone, the max waiting time
    // first decreases (more capacity helps) then increases
    // (distributing capacity causes some to wait longer)
    // This is a simplified illustration
 
    const n = speeds.length;
    // Function is unimodal in capacity allocation
    return 0; // Placeholder
}
 
// Pattern 2: Revenue maximization
function maxRevenue(priceElasticity: number): (price: number) => number {
    // demand = 100 - elasticity * price
    // revenue = price * demand = price * (100 - elasticity * price)
    // revenue = -elasticity * price² + 100 * price
    // This is a downward parabola - unimodal with maximum
 
    return (price: number) => {
        const demand = Math.max(0, 100 - priceElasticity * price);
        return price * demand;
    };
}
 
// Pattern 3: Allocation to minimize waste
function minWaste(totalResource: number, units: number): (perUnit: number) => number {
    // Allocate 'perUnit' amount to each of 'units' items
    // Too little: items fail (waste the resource given)
    // Too much: excess resource is wasted
    // Optimal: exactly meets requirements
 
    // Simplified model: waste = sum of shortfalls + sum of overages
    const requirements = [10, 15, 20, 12, 18]; // Each unit needs this much
 
    return (perUnit: number) => {
        let waste = 0;
        for (const req of requirements) {
            if (perUnit < req) {
                waste += req - perUnit; // Shortfall cost
            } else {
                waste += (perUnit - req) * 0.5; // Overage cost (less severe)
            }
        }
        return waste;
    };
}
 
// Usage: The waste function is unimodal - can use ternary search to find optimal allocation

Proving Unimodality

In competitive programming, intuition often suffices. But for production systems or when debugging unexpected results, you may need to prove that your function is unimodal. Here are rigorous approaches:

Method 1: Second Derivative Test (For Smooth Functions)

If f(x) is twice differentiable:

Find critical points where f'(x) = 0
If there's exactly one critical point x* and f''(x*) < 0, function has a unique maximum at x*
If there's exactly one critical point x* and f''(x*) > 0, function has a unique minimum at x*

This proves strict unimodality for smooth functions.

Method 2: Composition Rules

Sum of unimodal functions (with same mode) → Generally unimodal
Sum of convex functions → Convex (hence unimodal for minimum)
Max of convex functions → Convex
Negation flips concave ↔ convex

Method 3: Discrete Verification (For Discrete Domains)

If the domain is discrete and small, you can check:

List all values: [f(1), f(2), ..., f(n)]
Verify: values increase to a point, then decrease
This is O(n) but gives certainty

Method 4: Problem Structure Argument

Often the strongest proof comes from understanding why the function must be unimodal:

"Adding more workers helps until communication overhead dominates"
"Revenue grows with price until demand drops too much"
"Error decreases as we approach the target, then increases past it"

These structural arguments are compelling and don't require calculus.

Pragmatic Approach in Contests

In competitive programming, if the problem strongly hints at optimization with a single optimum, and the sample cases work, assume unimodality and proceed. Rigorous proofs are for production code and edge cases. But always have a mental model for why the function should be unimodal.

Example Proof: Revenue Function

Let's prove the revenue function R(p) = p × (100 - p) is unimodal on [0, 100].

Proof:

Expand: R(p) = 100p - p²
First derivative: R'(p) = 100 - 2p
Critical point: R'(p) = 0 → p = 50
Second derivative: R''(p) = -2 < 0 (always negative)
Since R''(50) < 0, the critical point is a maximum
Since there's exactly one critical point in [0, 100], the function is strictly unimodal ✓

This is the gold standard for proving unimodality: find the unique critical point and confirm its nature.

Discrete Unimodal Sequences

So far we've focused on continuous functions, but unimodality extends naturally to discrete sequences. This is especially relevant in competitive programming where we often work with integer domains.

Definition (Discrete Unimodal Sequence)

A sequence a[0], a[1], ..., a[n-1] is unimodal with a maximum if there exists an index k such that:

a[0] ≤ a[1] ≤ ... ≤ a[k] (non-decreasing up to k)
a[k] ≥ a[k+1] ≥ ... ≥ a[n-1] (non-increasing from k)

The element a[k] is the mode (peak) of the sequence.

Why Discrete Unimodality Matters

Many integer optimization problems produce discrete unimodal functions:

Minimizing the cost of allocating k resources
Maximizing profit with k items purchased
Finding optimal buffer size, batch size, or threshold

Ternary Search on Integers

When the domain is integers {0, 1, 2, ..., n}, ternary search needs slight modification:

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

DiscreteUnimodal.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
// Ternary search on discrete unimodal sequences
 
// Find peak in unimodal integer sequence
function ternarySearchDiscrete(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    // Assumes f is unimodal with a maximum over integers [left, right]
    
    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;  // Peak is right of m1 (might be at m1 or later)
        } else {
            right = m2;  // Peak is left of m2 (might be at m2 or earlier)
        }
    }
    
    // Only 2-3 candidates left, check all
    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;
}
 
// Example: Find k that maximizes f(k) = k * (10 - k)
// This is maximized at k = 5 where f(5) = 25
function exampleF(k: number): number {
    return k * (10 - k);
}
 
const result = ternarySearchDiscrete(exampleF, 0, 10);
console.log(`Maximum at k = ${result}`);  // 5
console.log(`f(${result}) = ${exampleF(result)}`);  // 25
 
// Example: Unimodal array - find peak index
const unimodalArray = [1, 3, 7, 12, 15, 13, 8, 4, 2];
const peakIdx = ternarySearchDiscrete(i => unimodalArray[i], 0, unimodalArray.length - 1);
console.log(`Peak at index ${peakIdx}: ${unimodalArray[peakIdx]}`);  // Index 4: 15

Integer Domain Subtlety

Unlike continuous ternary search which can converge to arbitrary precision, discrete ternary search must eventually check remaining candidates directly. When right - left < 3, you can't place two distinct interior points, so the algorithm necessarily terminates and checks remaining values.

Summary: The Foundation of Ternary Search

We've built a comprehensive understanding of unimodal functions—the mathematical structure that makes ternary search correct and efficient.

Key Takeaways

•Unimodal = One Peak (or Valley) — The function increases to a maximum point, then decreases (or vice versa for minimum).
•Strict vs. Non-Strict — Strict unimodality uses < and >, guaranteeing unique optimum. Non-strict allows plateaus.
•Ternary Search Requires Unimodality — Without unimodality, ternary search can return incorrect results silently.
•Convex/Concave ⊂ Unimodal — Convexity implies unimodality, but unimodality doesn't require smoothness or convexity.
•Recognition Patterns — Trade-off problems, physical systems, economics, and "too little/too much" scenarios often produce unimodal functions.
•Discrete Unimodality — Integer sequences can be unimodal too, needing slightly modified termination conditions.

What's Next:

Now that we understand the mathematical foundation, we're ready to implement ternary search. The next page covers finding maximum and minimum values of unimodal functions, with complete algorithms for both continuous and discrete domains, including precision considerations and early termination strategies.

Page Complete

You now have deep understanding of unimodal functions—what they are, how to recognize them, and why they're essential for ternary search. Next, we'll put this knowledge into practice with the ternary search algorithm itself.

2 / 4

Loading learning content...

Data Structures & AlgorithmsTernary Search

Ternary Search — Finding Extrema in Unimodal Functions

LevelIntermediate

Duration55 mins

TopicTernary Search

2 / 4

Unimodal Functions

The Shape of Searchable Problems

But what exactly does 'unimodal' mean? Why is unimodality so important? And how do you recognize when a problem's underlying function is unimodal?

What You Will Learn

Formal Definition of Unimodality

Let's establish rigorous definitions. Mathematics prizes precision, and algorithmic correctness depends on it.

Definition (Unimodal Function — Maximum Case)

A function f: [a, b] → ℝ is unimodal with a maximum if there exists a point x* ∈ [a, b] such that:

For all x₁, x₂ ∈ [a, x*] where x₁ < x₂: f(x₁) ≤ f(x₂) (non-decreasing on [a, x*])
For all x₁, x₂ ∈ [x*, b] where x₁ < x₂: f(x₁) ≥ f(x₂) (non-increasing on [x*, b])

The point x* is called the mode of the function.

Definition (Unimodal Function — Minimum Case)

Similarly, a function f: [a, b] → ℝ is unimodal with a minimum if there exists a point x* ∈ [a, b] such that:

For all x₁, x₂ ∈ [a, x*] where x₁ < x₂: f(x₁) ≥ f(x₂) (non-increasing on [a, x*])
For all x₁, x₂ ∈ [x*, b] where x₁ < x₂: f(x₁) ≤ f(x₂) (non-decreasing on [x*, b])

This is the "valley" case, dual to the "peak" case above.

Strict vs. Non-Strict Unimodality

Intuitive Interpretation

Key Properties of Unimodal Functions

Single Extremum — Exactly one global maximum (or minimum) in the interval
No Local Traps — No local maxima other than the global maximum (critical for search algorithms!)
Monotonic Regions — The domain partitions into two monotonic regions separated by the mode
Comparison-Based Direction — Comparing two points tells you which direction leads toward the extremum

Unimodal Function Properties
Property	Maximum Case	Minimum Case
Shape	Single peak (∧-shaped)	Single valley (∨-shaped)
Left of mode	Non-decreasing	Non-increasing
Right of mode	Non-increasing	Non-decreasing
Mode location	Global maximum	Global minimum
Ternary search finds	Maximum point	Minimum point

Visualizing Unimodal Functions

Let's build visual intuition with concrete examples. Each example illustrates the unimodal shape and how it manifests in different mathematical contexts.

Example 1: Quadratic Function (Parabola)

The most classic unimodal function is the quadratic:

f(x) = -x² + 4x + 1 — Opens downward, maximum at x = 2
f(x) = x² - 6x + 8 — Opens upward, minimum at x = 3

These are textbook examples: smooth, symmetric, and obviously unimodal.

Example 2: Gaussian (Bell Curve)

f(x) = e^(-x²)

Example 3: Piecewise Linear (Triangle)

f(x) = { x           if x ≤ 5
       { 10 - x      if x > 5

This forms a triangle peak at x = 5. Despite being non-smooth (derivative undefined at x = 5), it's still unimodal. Ternary search handles this perfectly.

UnimodalExamples.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
// Examples of unimodal functions and where they peak/valley
 
// Example 1: Quadratic - Maximum at x = 2
function quadraticMax(x: number): number {
    return -x * x + 4 * x + 1;  // = -(x-2)² + 5, max at x=2
}
 
// Example 2: Quadratic - Minimum at x = 3
function quadraticMin(x: number): number {
    return x * x - 6 * x + 8;  // = (x-3)² - 1, min at x=3
}
 
// Example 3: Gaussian - Maximum at x = 0
function gaussian(x: number): number {
    return Math.exp(-x * x);
}
 
// Example 4: Triangle Peak - Maximum at x = 5
function trianglePeak(x: number): number {
    if (x <= 5) return x;
    return 10 - x;
}
 
// Example 5: Triangle Valley - Minimum at x = 3
function triangleValley(x: number): number {
    if (x <= 3) return 3 - x;
    return x - 3;
}
 
// Example 6: Product Revenue Model
// Revenue = price × demand, where demand = 100 - price
// Revenue = price × (100 - price) = -price² + 100*price
// This is unimodal with max at price = 50
function revenue(price: number): number {
    const demand = Math.max(0, 100 - price);
    return price * demand;
}
 
// Visualization helper: sample function in interval
function sampleFunction(
    f: (x: number) => number, 
    start: number, 
    end: number, 
    samples: number = 10
): void {
    console.log("x\t\tf(x)");
    console.log("-".repeat(25));
    for (let i = 0; i <= samples; i++) {
        const x = start + (end - start) * (i / samples);
        console.log(`${x.toFixed(2)}\t\t${f(x).toFixed(4)}`);
    }
}
 
// Demo: Quadratic maximum
console.log("
Quadratic Maximum (peak at x=2):");
sampleFunction(quadraticMax, 0, 4);
 
// Demo: Revenue (peak at price=50)
console.log("
Revenue Function (peak at price=50):");
sampleFunction(revenue, 0, 100);

Smoothness Not Required

Non-Unimodal Functions — What Breaks

Understanding what makes a function not unimodal is crucial. When unimodality fails, ternary search can return incorrect results. Let's examine the failure modes:

Multi-Modal Functions

A multi-modal function has multiple peaks (or valleys). Examples:

f(x) = sin(x) over [0, 4π] — Multiple peaks and valleys
f(x) = x⁴ - 3x² + 1 — Creates two peaks and a valley
Optimization landscapes in neural networks — Notoriously multi-modal

Why Ternary Search Fails on Multi-Modal Functions

More concretely:

Let m1 = π and m2 = 4π/3 (both after the first peak)
f(m1) = 0, f(m2) ≈ -0.87
Since f(m1) > f(m2), ternary search eliminates the right third
But this elimination might discard the search space containing the global maximum if we started with different bounds!

Function Types Where Ternary Search Fails

•Multi-Modal (Multiple Peaks) — sin(x), polynomial oscillations, real-world optimization surfaces. Ternary search finds a local extremum, not necessarily the global one.
•Monotonic Functions — Purely increasing or decreasing functions technically don't have an interior maximum. The 'peak' is at a boundary. Ternary search may find the boundary, but binary search is more efficient for monotonic constraints.
•Constant Functions — If f(x) = c for all x, every point is equally good. Ternary search works but provides no meaningful answer beyond 'any x is fine.'
•Discontinuous Functions — Jumps can trick the comparison logic. If f(m1) and f(m2) are on opposite sides of a discontinuity, the direction inference may be wrong.
•Functions with Plateaus — Extended flat regions (f(x) = c for x ∈ [a, b]) can cause ternary search to converge slowly or get stuck, though technically it still works for non-strict unimodality.

MultiModalFailure.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
// Demonstration: Ternary search on multi-modal function
// THIS IS BROKEN - shown for educational purposes
 
function multiModal(x: number): number {
    // Two peaks: one near x=1, one near x=4
    return -((x - 1) ** 2) * ((x - 4) ** 2) + 10;
    // Peaks at x=1 and x=4, valley at x=2.5
}
 
function brokenTernarySearch(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    const epsilon = 1e-6;
    
    while (right - left > epsilon) {
        const m1 = left + (right - left) / 3;
        const m2 = right - (right - left) / 3;
        
        if (f(m1) < f(m2)) {
            left = m1;  // Assumes peak is right of m1
        } else {
            right = m2;  // Assumes peak is left of m2
        }
    }
    
    return (left + right) / 2;
}
 
// Different search ranges give different (wrong) answers!
console.log("Searching [0, 5]:", brokenTernarySearch(multiModal, 0, 5));
console.log("Searching [0, 2.5]:", brokenTernarySearch(multiModal, 0, 2.5));
console.log("Searching [2.5, 5]:", brokenTernarySearch(multiModal, 2.5, 5));
 
// The function has peaks at x=1 and x=4
// Depending on initial bounds and comparisons, we might find either!
// This demonstrates why unimodality is REQUIRED

Silent Failures Are Dangerous

Convexity and Concavity — Related Concepts

Definition Recap

Convex function: For any two points x₁, x₂ and any λ ∈ [0, 1]: f(λx₁ + (1-λ)x₂) ≤ λf(x₁) + (1-λ)f(x₂)

Geometrically: the line segment connecting any two points on the graph lies above the graph. The function "curves upward" like a bowl.
Concave function: The inequality is reversed: f(λx₁ + (1-λ)x₂) ≥ λf(x₁) + (1-λ)f(x₂)

The line segment lies below the graph. The function "curves downward" like a dome.

The Key Insight

Every convex function is unimodal with a minimum (it has a single valley)
Every concave function is unimodal with a maximum (it has a single peak)

But the reverse is not true! Unimodality is a weaker condition than convexity/concavity. A function can be unimodal without being convex or concave.

Why Does This Matter?

Ternary search, however, works on the broader class of unimodal functions—including those that are neither convex nor concave. This makes it valuable when:

The function doesn't have derivatives (or they're hard to compute)
You only have black-box access to the function (can evaluate but not differentiate)
The function is piecewise linear or has corners
You want a simple, robust algorithm without convexity assumptions

Convexity, Concavity, and Unimodality
Function Class	Bowl/Dome Shape	Unimodal?	Ternary Search?	Gradient-Based?
Strictly Convex	U-shaped (bowl)	✅ Yes (minimum)	✅ Works	✅ Guaranteed global min
Strictly Concave	∩-shaped (dome)	✅ Yes (maximum)	✅ Works	✅ Guaranteed global max
Unimodal (not convex)	Single peak/valley	✅ Yes	✅ Works	⚠️ May work, no guarantee
Multi-modal	Multiple peaks	❌ No	❌ Fails	⚠️ Finds local extremum only

The Hierarchy of Function Classes

Recognizing Unimodality in Problems

Pattern 1: Physical Systems

Many physical quantities are unimodal:

Projectile range vs. launch angle (max at ~45°)
Signal strength vs. frequency (peaks at resonance)
Efficiency vs. operating point (optimal load balancing)

Physics tends to produce smooth, well-behaved functions with single optima.

Pattern 2: Economic Models

Revenue = Price × Quantity, where Quantity decreases with Price → Unimodal with a maximum
Cost functions often have decreasing returns → Convex (unimodal minimum)
Profit = Revenue - Cost → Often unimodal (sum of concave and convex)

Pattern 3: "Too Little / Too Much" Problems

When the problem involves a trade-off where:

Too small a value is bad (insufficient resources, capacity, etc.)
Too large a value is also bad (overhead, diminishing returns, constraints)
There's a sweet spot in between

...the function is likely unimodal.

Pattern 4: Squared Terms Without Higher Powers

Functions involving (x - a)² terms without higher-order terms are often unimodal:

f(x) = -(x - 5)² → Unimodal max at 5
f(x) = (x - 3)² + (x - 7)² → Unimodal (sum of convex functions is convex)

Pattern 5: Binary Search Predicate Hint

If you can phrase a related yes/no question that's monotonic:

"Is it possible to achieve at least value V?" → If this is monotonic in V
Then the optimal V is at the boundary, suggesting underlying unimodality

Quick Unimodality Checklist

•Single Optimal Point — The problem asks for ONE best value, not multiple good values
•Trade-off Structure — Increasing the parameter helps up to a point, then hurts
•No Oscillations — The objective doesn't go up-down-up-down with the parameter
•Smooth Problem Domain — Real-valued rather than combinatorial structure
•Physical Intuition — Real-world analogs suggest a single optimum

UnimodalRecognition.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
// Common problem patterns that produce unimodal functions
 
// Pattern 1: Minimizing maximum difference (often unimodal in the answer)
function minMaxDifference(speeds: number[], targetTime: number): number {
    // If we allocate 'capacity' to everyone, the max waiting time
    // first decreases (more capacity helps) then increases
    // (distributing capacity causes some to wait longer)
    // This is a simplified illustration
 
    const n = speeds.length;
    // Function is unimodal in capacity allocation
    return 0; // Placeholder
}
 
// Pattern 2: Revenue maximization
function maxRevenue(priceElasticity: number): (price: number) => number {
    // demand = 100 - elasticity * price
    // revenue = price * demand = price * (100 - elasticity * price)
    // revenue = -elasticity * price² + 100 * price
    // This is a downward parabola - unimodal with maximum
 
    return (price: number) => {
        const demand = Math.max(0, 100 - priceElasticity * price);
        return price * demand;
    };
}
 
// Pattern 3: Allocation to minimize waste
function minWaste(totalResource: number, units: number): (perUnit: number) => number {
    // Allocate 'perUnit' amount to each of 'units' items
    // Too little: items fail (waste the resource given)
    // Too much: excess resource is wasted
    // Optimal: exactly meets requirements
 
    // Simplified model: waste = sum of shortfalls + sum of overages
    const requirements = [10, 15, 20, 12, 18]; // Each unit needs this much
 
    return (perUnit: number) => {
        let waste = 0;
        for (const req of requirements) {
            if (perUnit < req) {
                waste += req - perUnit; // Shortfall cost
            } else {
                waste += (perUnit - req) * 0.5; // Overage cost (less severe)
            }
        }
        return waste;
    };
}
 
// Usage: The waste function is unimodal - can use ternary search to find optimal allocation

Proving Unimodality

Method 1: Second Derivative Test (For Smooth Functions)

If f(x) is twice differentiable:

Find critical points where f'(x) = 0
If there's exactly one critical point x* and f''(x*) < 0, function has a unique maximum at x*
If there's exactly one critical point x* and f''(x*) > 0, function has a unique minimum at x*

This proves strict unimodality for smooth functions.

Method 2: Composition Rules

Sum of unimodal functions (with same mode) → Generally unimodal
Sum of convex functions → Convex (hence unimodal for minimum)
Max of convex functions → Convex
Negation flips concave ↔ convex

Method 3: Discrete Verification (For Discrete Domains)

If the domain is discrete and small, you can check:

List all values: [f(1), f(2), ..., f(n)]
Verify: values increase to a point, then decrease
This is O(n) but gives certainty

Method 4: Problem Structure Argument

Often the strongest proof comes from understanding why the function must be unimodal:

"Adding more workers helps until communication overhead dominates"
"Revenue grows with price until demand drops too much"
"Error decreases as we approach the target, then increases past it"

These structural arguments are compelling and don't require calculus.

Pragmatic Approach in Contests

Example Proof: Revenue Function

Let's prove the revenue function R(p) = p × (100 - p) is unimodal on [0, 100].

Proof:

Expand: R(p) = 100p - p²
First derivative: R'(p) = 100 - 2p
Critical point: R'(p) = 0 → p = 50
Second derivative: R''(p) = -2 < 0 (always negative)
Since R''(50) < 0, the critical point is a maximum
Since there's exactly one critical point in [0, 100], the function is strictly unimodal ✓

This is the gold standard for proving unimodality: find the unique critical point and confirm its nature.

Discrete Unimodal Sequences

So far we've focused on continuous functions, but unimodality extends naturally to discrete sequences. This is especially relevant in competitive programming where we often work with integer domains.

Definition (Discrete Unimodal Sequence)

A sequence a[0], a[1], ..., a[n-1] is unimodal with a maximum if there exists an index k such that:

a[0] ≤ a[1] ≤ ... ≤ a[k] (non-decreasing up to k)
a[k] ≥ a[k+1] ≥ ... ≥ a[n-1] (non-increasing from k)

The element a[k] is the mode (peak) of the sequence.

Why Discrete Unimodality Matters

Many integer optimization problems produce discrete unimodal functions:

Minimizing the cost of allocating k resources
Maximizing profit with k items purchased
Finding optimal buffer size, batch size, or threshold

Ternary Search on Integers

When the domain is integers {0, 1, 2, ..., n}, ternary search needs slight modification:

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

DiscreteUnimodal.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
// Ternary search on discrete unimodal sequences
 
// Find peak in unimodal integer sequence
function ternarySearchDiscrete(
    f: (x: number) => number,
    left: number,
    right: number
): number {
    // Assumes f is unimodal with a maximum over integers [left, right]
    
    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;  // Peak is right of m1 (might be at m1 or later)
        } else {
            right = m2;  // Peak is left of m2 (might be at m2 or earlier)
        }
    }
    
    // Only 2-3 candidates left, check all
    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;
}
 
// Example: Find k that maximizes f(k) = k * (10 - k)
// This is maximized at k = 5 where f(5) = 25
function exampleF(k: number): number {
    return k * (10 - k);
}
 
const result = ternarySearchDiscrete(exampleF, 0, 10);
console.log(`Maximum at k = ${result}`);  // 5
console.log(`f(${result}) = ${exampleF(result)}`);  // 25
 
// Example: Unimodal array - find peak index
const unimodalArray = [1, 3, 7, 12, 15, 13, 8, 4, 2];
const peakIdx = ternarySearchDiscrete(i => unimodalArray[i], 0, unimodalArray.length - 1);
console.log(`Peak at index ${peakIdx}: ${unimodalArray[peakIdx]}`);  // Index 4: 15

Integer Domain Subtlety

Summary: The Foundation of Ternary Search

We've built a comprehensive understanding of unimodal functions—the mathematical structure that makes ternary search correct and efficient.

Key Takeaways

•Unimodal = One Peak (or Valley) — The function increases to a maximum point, then decreases (or vice versa for minimum).
•Strict vs. Non-Strict — Strict unimodality uses < and >, guaranteeing unique optimum. Non-strict allows plateaus.
•Ternary Search Requires Unimodality — Without unimodality, ternary search can return incorrect results silently.
•Convex/Concave ⊂ Unimodal — Convexity implies unimodality, but unimodality doesn't require smoothness or convexity.
•Recognition Patterns — Trade-off problems, physical systems, economics, and "too little/too much" scenarios often produce unimodal functions.
•Discrete Unimodality — Integer sequences can be unimodal too, needing slightly modified termination conditions.

What's Next:

Page Complete

2 / 4