Ternary Search

Quick Revisit

• USE WHEN: Finding the max/min of a unimodal function (one peak or valley)
• INVARIANT: The interval always contains the extremum; trisect and discard the provably worse third
• TIME: O(log n) discrete, O(log(range/ε)) continuous | SPACE: O(1)
• CLASSIC BUG: Applying to a non-unimodal function (two peaks)—comparison gives no info about global optimum
• PRACTICE: 01-ladder-1100-to-1400

Find the maximum or minimum of a unimodal function on a continuous or discrete domain in $O(\log n)$ or $O(\log (\text{range}/\epsilon ))$.

Difficulty: Beginner | Prerequisites: Binary Search | CF Rating Range: 1200–1800

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Common Mistakes
• Debug Drills
• Further Reading

---

Intuition

Take the unimodal function $f(x)=-(x-42{)}^2+100$ on the integer domain $[0,100]$. It climbs to a peak at $x=42$ and falls symmetrically. You need the $x$ that maximizes $f$.

The naive approach evaluates every integer:

  x:    0     10     20     30     40     41     42     43     50     100
  f: -1664  -924   -384    -44     96     99    100     99     36   -3264

That is 101 evaluations. Scale the domain to $[0,{10}^9]$ and naive scanning needs ${10}^9$ evaluations—way too slow when you have 2 seconds and $f$ itself might cost $O(n)$ to evaluate.

Binary search is also off the table: there is no monotonic predicate to split on. The function rises to a peak, then falls. Binary search needs a single false-to-true transition; here there is none.

Trisect the interval instead. Evaluate $f$ at two points $m_1,m_2$ that divide $[\text{lo},\text{hi}]$ into thirds. If $f(m_1)<f(m_2)$, the maximum cannot lie in $[\text{lo},m_1]$—discard that third. Each step shrinks the interval by a factor of $2/3$.

Analogy: Imagine searching for the highest point on a fog-shrouded hill. You cannot see the summit, but you can measure altitude at any position. Pick two probes a third of the way into the search zone from each end. If the left probe sits lower than the right, the summit is not to the left of that probe—that flank is still climbing. Cut it away and repeat on the remainder.

Where the analogy breaks: A real hill may have plateaus or multiple ridges. Ternary search demands strict unimodality—exactly one peak (or valley). With two peaks, the comparison between $m_1$ and $m_2$ tells you nothing about the global maximum.

Visual Walkthrough

$f(x)=-(x-42{)}^2+100$ on $[\text{lo},\text{hi}]=[0,100]$.

ASCII plot (approximate shape):

  f(x)
  100 |                        *
   80 |                     *     *
   60 |                  *           *
   40 |               *                 *
   20 |            *                       *
    0 |        *                               *
  -20 |     *                                     *
      +---+---+---+---+---+---+---+---+---+---+---+--> x
      0  10  20  30  40  50  60  70  80  90 100
                              ^
                          peak at 42

Iteration 1: $\text{lo}=0,\text{hi}=100$

  m1 = 0 + (100 - 0) / 3     = 33
  m2 = 100 - (100 - 0) / 3   = 67

  f(33) = -(33-42)^2 + 100 = -81 + 100  =  19
  f(67) = -(67-42)^2 + 100 = -625 + 100 = -525

  f(m1) = 19 > f(m2) = -525  --->  discard right: hi = m2 = 67

  |<--------------------- search zone ----->|
  0              33          67             100
  |               ^           ^              |
                 m1          m2=hi(new)

Iteration 2: $\text{lo}=0,\text{hi}=67$

  m1 = 0 + (67 - 0) / 3     = 22
  m2 = 67 - (67 - 0) / 3    = 45

  f(22) = -(22-42)^2 + 100 = -400 + 100 = -300
  f(45) = -(45-42)^2 + 100 = -9 + 100   =  91

  f(m1) = -300 < f(m2) = 91  --->  discard left: lo = m1 = 22

  0         22          45       67
  |          ^           ^        |
         lo(new)=m1     m2

Iteration 3: $\text{lo}=22,\text{hi}=67$

  m1 = 22 + (67 - 22) / 3   = 37
  m2 = 67 - (67 - 22) / 3   = 52

  f(37) = -(37-42)^2 + 100 = -25 + 100  = 75
  f(52) = -(52-42)^2 + 100 = -100 + 100 = 0

  f(m1) = 75 > f(m2) = 0  --->  discard right: hi = m2 = 52

  22        37          52
  |          ^           ^
            m1         m2=hi(new)

Iteration 4: $\text{lo}=22,\text{hi}=52$

  m1 = 22 + (52 - 22) / 3   = 32
  m2 = 52 - (52 - 22) / 3   = 42

  f(32) = -(32-42)^2 + 100 = -100 + 100 = 0
  f(42) = -(42-42)^2 + 100 = 0 + 100    = 100

  f(m1) = 0 < f(m2) = 100  --->  discard left: lo = m1 = 32

  22     32          42     52
  |       ^           ^      |
       lo(new)=m1    m2

After 4 iterations the search zone has shrunk from $[0,100]$ (width 100) to $[32,52]$ (width 20). Four more iterations and the zone is roughly width 2, pinpointing $x=42$.

Operation count:

  Naive:          101 evaluations of f
  Ternary search: ~40 evaluations (to reach precision < 1)
  For [0, 10^9]:  naive = 10^9,  ternary = ~200 evaluations

The Invariant

+------------------------------------------------------------------+
| INVARIANT: The maximum of f lies in [lo, hi]. Each iteration     |
| shrinks the interval by factor 2/3. After k iterations, the      |
| width is (2/3)^k * (hi_0 - lo_0). After ~190 iterations on a    |
| range of 10^18, the width drops below 10^(-9).                   |
+------------------------------------------------------------------+

Why the invariant holds: The function is unimodal—it increases to the peak, then decreases. When $f(m_1)<f(m_2)$, the peak cannot be at or to the left of $m_1$: if it were, $f$ would be decreasing at both $m_1$ and $m_2$, so $f(m_1)>f(m_2)$—a contradiction. Therefore the peak is in $(m_1,\text{hi}]$, and setting $\text{lo}=m_1$ preserves the invariant. Symmetric reasoning applies when $f(m_1)>f(m_2)$.

Verify with Iteration 1: $f(33)=19>f(67)=-525$. The peak at 42 lies between $m_1=33$ and ${\text{hi}}_{\text{old}}=100$. Setting $\text{hi}=67$ keeps it inside $[0,67]$. Invariant preserved.

Why factor $2/3$: Each step discards the segment from $\text{lo}$ to $m_1$ (or from $m_2$ to $\text{hi}$)—exactly $1/3$ of the interval. The surviving interval is $2/3$ of the previous width. After $k$ iterations: width $=(2/3{)}^k\cdot W_0$.

To reach precision $\epsilon$ from initial width $W_0$:

$$k=\lceil \frac{\log (W_0/\epsilon )}{\log (3/2)}\rceil$$

For $W_0={10}^{18}$ and $\epsilon ={10}^{-9}$: $k\approx \frac{27\cdot \ln 10}{\ln (3/2)}\approx 153$. In practice, 200 iterations is a safe, universal choice.

What the Code Won't Teach You

The problem is proving unimodality, not coding the loop. The ternary search template is 8 lines. The entire intellectual challenge is staring at a cost function and proving it has exactly one extremum in the search range. Fail to prove this and ternary search may silently converge to a local optimum that is not the global one.

Many optimization problems have a hidden unimodal structure. "What angle maximizes projectile range?"—unimodal in angle. "What price maximizes revenue?"—often unimodal. "How do you split tasks between two machines to minimize total time?"—convex cost. The challenge is recognizing that the objective is unimodal, not applying the search once you have.

  IS MY FUNCTION UNIMODAL? -- DECISION TREE
  ==========================================

  Can you prove f''(x) <= 0 everywhere (concave)?
       │
       ├── YES ──-> Single maximum OK  ->  Ternary search for max
       │
       └── NO  ──-> Can you prove f''(x) >= 0 (convex)?
                     │
                     ├── YES ──-> Single minimum OK  ->  Ternary search for min
                     │
                     └── NO  ──-> Is f(x) = g(x) + h(x) where both are
                                  convex/concave?
                                    │
                                    ├── YES ──-> Sum of convex is convex OK
                                    │
                                    └── NO  ──-> Ternary search may FAIL.
                                                Plot/test before trusting.

Know when binary search on the derivative wins. On integers, if you can cheaply evaluate $f(x+1)-f(x)$, binary search on the sign of this "derivative" eliminates half the range per step (versus one-third for ternary). Use ternary search only when the domain is continuous or adjacent-value comparison is expensive.

With those deeper insights in hand, here is how to spot ternary search problems during a contest.

When to Reach for This

Trigger phrases in problem statements:

• "unimodal function" or "first increases then decreases"—direct application.
• "find the maximum / minimum on an interval" with a function that has a single extremum.
• "convex function optimization"—minimize a convex function (unimodal with a single minimum).
• "minimize cost where cost first decreases then increases as parameter grows."
• "find optimal real-valued parameter" with a smooth, single-peaked objective.

Counter-examples (looks like ternary search but isn't):

• Multimodal function: $f$ has two peaks. Ternary search can converge to either—no guarantee it finds the global maximum. You need a different approach: random restarts, analytical methods, or exhaustive search if the domain is small.
• Monotone function: $f$ only increases (or only decreases). The maximum is at an endpoint. Binary search on a predicate is simpler and faster—each step eliminates $1/2$ instead of $1/3$.
• Discrete domain with accessible derivative: If you can cheaply compute whether $f(x+1)>f(x)$, binary search on that condition is strictly better—it eliminates half the range each step rather than one-third.

---

C++ STL Reference

No STL function directly performs ternary search. You implement it manually. Related utilities:

Function / Class	Header	What it does	Time Complexity
midpoint(a, b)	<numeric>	Overflow-safe $(a+b)/2$ (C++20)	$O(1)$
abs(x)	<cstdlib> / <cmath>	Absolute value	$O(1)$
fixed / setprecision(k)	<iomanip>	Output real number with $k$ decimal digits	—

---

Implementation (Contest-Ready)

Continuous Ternary Search—Minimal Template

#include <bits/stdc++.h>
using namespace std;

double f(double x) {
    return -(x - 42) * (x - 42) + 100; // replace with problem function
}

int main() {
    double lo = 0, hi = 100;
    for (int i = 0; i < 200; i++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2))
            lo = m1;  // maximum is not in [lo, m1]
        else
            hi = m2;  // maximum is not in [m2, hi]
    }
    cout << fixed << setprecision(9) << lo << "\n";
}

Continuous Ternary Search—Explained

#include <bits/stdc++.h>
using namespace std;

// The unimodal function to maximize.
// Must have exactly one peak: increases then decreases.
// For minimization: flip the comparison (f(m1) > f(m2) -> lo = m1).
double f(double x) {
    return -(x - 42) * (x - 42) + 100;
}

int main() {
    // [lo, hi] = initial search interval containing the peak.
    double lo = 0, hi = 100;

    // Fixed iteration count: 200 iterations shrink the interval by
    // (2/3)^200 ~ 10^(-35), far beyond double precision (~10^(-15)).
    // Never use "while (hi - lo > eps)" -- it can infinite-loop for
    // large values due to floating-point granularity.
    for (int i = 0; i < 200; i++) {
        double m1 = lo + (hi - lo) / 3;  // left trisection point
        double m2 = hi - (hi - lo) / 3;  // right trisection point

        if (f(m1) < f(m2))
            lo = m1;   // peak is in (m1, hi] -- discard [lo, m1]
        else
            hi = m2;   // peak is in [lo, m2) -- discard [m2, hi]
    }
    // lo and hi have converged; either is the answer.
    cout << fixed << setprecision(9) << lo << "\n";
}

Discrete Ternary Search—Minimal Template

#include <bits/stdc++.h>
using namespace std;

long long f(long long x) {
    return -(x - 42) * (x - 42) + 100; // replace with problem function
}

int main() {
    long long lo = 0, hi = 100;
    while (hi - lo > 2) {
        long long m1 = lo + (hi - lo) / 3;
        long long m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2))
            lo = m1;
        else
            hi = m2;
    }
    // Brute-force the remaining 1--3 candidates.
    long long best = lo;
    for (long long x = lo; x <= hi; x++)
        if (f(x) > f(best))
            best = x;
    cout << best << "\n";
}

Discrete Ternary Search—Explained

#include <bits/stdc++.h>
using namespace std;

// Unimodal function on integers. Single peak: f(x-1) <= f(x) >= f(x+1)
// at the peak position.
long long f(long long x) {
    return -(x - 42) * (x - 42) + 100;
}

int main() {
    long long lo = 0, hi = 100;

    // Shrink until the interval has at most 3 elements.
    // Why > 2?  With hi - lo <= 2, there are at most 3 candidates
    // (lo, lo+1, lo+2). Trisecting further risks m1 == m2,
    // which causes no progress. So we stop and brute-force.
    while (hi - lo > 2) {
        long long m1 = lo + (hi - lo) / 3;
        long long m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2))
            lo = m1;   // peak is in (m1, hi]
        else
            hi = m2;   // peak is in [lo, m2)
    }

    // Check every remaining candidate (at most 3 values).
    long long best = lo;
    for (long long x = lo; x <= hi; x++)
        if (f(x) > f(best))
            best = x;

    cout << best << "\n";
}

Minimization of a Convex Function (Continuous)

#include <bits/stdc++.h>
using namespace std;

double cost(double x) {
    return (x - 3.7) * (x - 3.7) + 5; // convex: one minimum
}

int main() {
    double lo = -1e9, hi = 1e9;
    for (int i = 0; i < 200; i++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (cost(m1) > cost(m2))
            lo = m1;  // minimum is not in [lo, m1]
        else
            hi = m2;  // minimum is not in [m2, hi]
    }
    cout << fixed << setprecision(9) << lo << "\n";
}

Binary Search on Derivative (Discrete Alternative)

When $f$ is unimodal on integers, you can binary search on the condition $f(x)<f(x+1)$ (the "derivative" is positive). This condition is monotonic: true for $x$ before the peak, false after. This uses $O(\log n)$ evaluations instead of $O({\log }_{1.5}n)$.

#include <bits/stdc++.h>
using namespace std;

long long f(long long x) {
    return -(x - 42) * (x - 42) + 100;
}

int main() {
    long long lo = 0, hi = 100;
    // Binary search: find the last x where f(x) < f(x+1).
    // The peak is at lo+1 (or lo if f is non-decreasing everywhere).
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (f(mid) < f(mid + 1))
            lo = mid + 1;   // still ascending, peak is to the right
        else
            hi = mid;       // descending or at peak
    }
    cout << lo << " " << f(lo) << "\n";
}

---

Operations Reference

All variants boil down to repeated function evaluations—the table below shows how the iteration count and per-evaluation cost combine.

Operation	Time	Space
Continuous ternary search (200 iterations)	$O(200\cdot C)$	$O(1)$
Discrete ternary search on range $[lo,hi]$	$O({\log }_{1.5}(hi-lo)\cdot C)$	$O(1)$
Binary search on discrete derivative	$O(\log (hi-lo)\cdot C)$	$O(1)$

$C$ = cost of one evaluation of $f$. Typically $O(1)$ to $O(n)$.

Comparison: Ternary search needs $\sim 1.71\times$ more evaluations than binary search on derivative for the same range. Use ternary search when you cannot easily compute $f(x+1)-f(x)$ separately, or when the domain is continuous.

---

Problem Patterns & Tricks

Optimize a Parameter in a Geometric / Physics Problem

The function computes a distance, area, time, or cost that depends on a single real parameter and is unimodal. Ternary-search on that parameter.

Example: "A rope of length $L$ hangs between two points at heights $h_1$ and $h_2$. Find the horizontal distance between them that minimizes the lowest point." The height of the lowest point is a unimodal function of that distance.

Examples: CF 578C -- Weakness and Poorness, CF 439D -- Devu and his Brother

---

Ternary Search on Answer with Greedy Check

The answer to the problem is a real number $t$, and the cost function $g(t)$ is unimodal. Ternary search on $t$; for each candidate, run a greedy or simulation to compute $g(t)$.

auto cost = [&](double t) -> double {
    // Simulate / greedy to compute cost given parameter t
    double total = 0;
    for (int i = 0; i < n; i++)
        total += /* problem-specific cost depending on t */;
    return total;
};

Examples: CF 578C -- Weakness and Poorness

---

Discrete Peak-Finding

Array $a[0..n-1]$ is unimodal (increases then decreases). Find the peak index. Ternary search or binary search on derivative.

// Binary search on derivative is preferred for discrete arrays
int lo = 0, hi = n - 1;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[mid + 1])
        lo = mid + 1;
    else
        hi = mid;
}
// a[lo] is the peak

Examples: LeetCode 162 -- Find Peak Element, CF 1301B -- Motarack's Birthday

---

Ternary Search on Convex Cost for Partitioning

Split $n$ items into groups, where the cost per group is convex (e.g., quadratic). The total cost as a function of the split point is unimodal. Ternary search on the split point.

Example: Distribute tasks between two machines. Machine $A$ takes $a\cdot k^2$ time for $k$ tasks, machine $B$ takes $b\cdot (n-k{)}^2$. Total time $=a{k}^2+b(n-k{)}^2$ is convex in $k$. Ternary search on $k\in [0,n]$.

Examples: CF 1355E -- Restorer Distance

---

Nested Ternary Search (2D Optimization)

The function $f(x,y)$ is unimodal in both $x$ and $y$ independently (e.g., the sum of distances to a set of points on a plane). Fix $x$, ternary-search on $y$; wrap an outer ternary search on $x$.

Warning: This only works if $f$ is unimodal in each variable when the other is fixed, and the global structure has a single extremum. It does not work for general 2D functions.

auto solve_y = [&](double x) -> double {
    double lo = -1e9, hi = 1e9;
    for (int i = 0; i < 200; i++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (cost(x, m1) > cost(x, m2)) lo = m1;
        else hi = m2;
    }
    return cost(x, lo);
};
double lo = -1e9, hi = 1e9;
for (int i = 0; i < 200; i++) {
    double m1 = lo + (hi - lo) / 3;
    double m2 = hi - (hi - lo) / 3;
    if (solve_y(m1) > solve_y(m2)) lo = m1;
    else hi = m2;
}

Total evaluations: $200\times 200=40000$.

Examples: CF 782B -- The Meeting Place Cannot Be Changed

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                    TERNARY SEARCH CHEAT SHEET                    |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - Unimodal f (one peak or one valley)                         |
|   - "Find max/min of function on interval"                      |
|   - Convex cost minimization                                    |
|   - Continuous or discrete domain                               |
+------------------------------------------------------------------+
| CONTINUOUS (maximize):                                           |
|   double lo = LO, hi = HI;                                      |
|   for (int i = 0; i < 200; i++) {                               |
|       double m1 = lo + (hi-lo)/3, m2 = hi - (hi-lo)/3;         |
|       if (f(m1) < f(m2)) lo = m1; else hi = m2;                |
|   }                                                              |
| DISCRETE (maximize):                                             |
|   while (hi - lo > 2) {                                         |
|       ll m1 = lo+(hi-lo)/3, m2 = hi-(hi-lo)/3;                 |
|       if (f(m1) < f(m2)) lo = m1; else hi = m2;                |
|   }                                                              |
|   for (ll x = lo; x <= hi; x++) best = max(best, f(x));        |
+------------------------------------------------------------------+
| MINIMIZE: flip comparison (f(m1) > f(m2) -> lo = m1)            |
+------------------------------------------------------------------+
| COMPLEXITY: O(log(range/eps) * C)  /  O(log_{1.5}(range) * C)  |
| SPACE:      O(1)                                                 |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Using Ternary Search on a Non-Unimodal Function

The #1 mistake. Ternary search gives garbage if $f$ has multiple local maxima. Before coding, prove that $f$ has exactly one peak (or valley) in the search range. Sketch the function or argue monotonicity on each side of the extremum.

Minimization vs. Maximization—Flipped Comparison

For maximization (find peak): if (f(m1) < f(m2)) lo = m1; else hi = m2; For minimization (find valley): if (f(m1) > f(m2)) lo = m1; else hi = m2;

Getting this backwards makes the algorithm diverge to an endpoint instead of converging to the extremum.

Discrete Case: Stopping Too Early or Too Late

while (hi - lo > 2) is the safe stopping condition. If you use while (lo < hi), you risk an infinite loop when $m_1==m_2$ (which happens when $\text{hi}-\text{lo}\le 2$). Always brute-force the last 2–3 candidates.

Floating-Point: Using while (hi - lo > eps) with Large Values

Same trap as binary search. If lo and hi are around ${10}^{15}$, the difference can never shrink below ${10}^{-9}$ due to double precision. Always use a fixed iteration count (200 is safe).

Not Enough Iterations

With 200 iterations, the interval shrinks by $(2/3{)}^{200}\approx {10}^{-35}$—more than sufficient for double precision ($\sim 15$ significant digits). Using fewer iterations (e.g., 50) may not converge for ranges as wide as ${10}^{18}$.

Forgetting the Discrete Alternative

On integers, binary search on the derivative $f(x+1)-f(x)$ is strictly better: $O(\log n)$ vs. $O({\log }_{1.5}n)$ evaluations, and it avoids the "last 3 candidates" brute-force. Use ternary search on integers only when you cannot compare adjacent values cheaply or when the function is defined on reals.

$f(m_1)==f(m_2)$ in the Discrete Case

When $f(m_1)=f(m_2)$, both $m_1$ and $m_2$ could be near the peak. You can safely discard either side (conventionally do hi = m2). The invariant still holds because the peak can be at $m_1$ or between $m_1$ and $m_2$, both of which remain in $[\text{lo},m_2]$.

Debug Checklist

1. Print lo, hi, m1, m2, f(m1), f(m2) each iteration.
2. Test with the peak at the boundary of the initial range.
3. Test with the peak exactly at a trisection point.
4. For discrete: verify the brute-force loop covers all remaining candidates.
5. For continuous: verify the output precision matches the problem requirement.

Mental Traps

Trap 1: "Ternary search is just binary search with three parts." The structure looks similar but the reasoning is fundamentally different. Binary search halves a range based on a yes/no monotone predicate. Ternary search eliminates one-third based on comparing two function values—this requires the function to be unimodal, a much stronger condition than monotonicity. Treating them as interchangeable leads you to ternary-search a monotone function (wasteful) or binary-search a unimodal one (incorrect).

  BINARY SEARCH vs TERNARY SEARCH -- DIFFERENT PROBLEMS
  =====================================================

  Binary Search:                Ternary Search:
  ─────────────                 ──────────────
  Predicate: F F F T T T        Function:    /\
  Need: monotone transition     Need: single peak (unimodal)

  Each step: eliminate 1/2      Each step: eliminate 1/3
  Iterations: log₂(n)          Iterations: log₁.₅(n) ~= 1.7 x log₂(n)

  Use for:                      Use for:
  - "minimum x such that..."    - "x that maximizes f(x)"
  - "is condition satisfied?"   - "peak of unimodal function"

Trap 2: "I should use while (hi - lo > eps) for real-valued search." With lo and hi around ${10}^{15}$, floating-point granularity means the difference can never shrink below $\sim 1$. The loop runs forever. Always use a fixed iteration count (200 is universally safe). This trap kills more ternary-search submissions than any logic error.

---

Self-Test

Before moving on, answer these without looking at the file. If you cannot, re-read the relevant section.

• [ ] State the termination condition for integer ternary search and for real-valued ternary search—and explain why they differ.
• [ ] Explain why $f(m_1)<f(m_2)$ implies the maximum is not in $[\text{lo},m_1]$—sketch a unimodal curve to support your argument.
• [ ] Write the integer ternary search template from memory, including the brute-force base case for the last 2–3 candidates.
• [ ] Give an example of a function that looks unimodal but is not, and explain why ternary search fails on it.
• [ ] Explain when binary search on the discrete derivative is equivalent to ternary search and which uses fewer evaluations.

---

Practice Problems

• CF 1200: Find peak element in a discrete array; ternary search on an explicit unimodal formula.
• CF 1500: Ternary search on a convex cost function (e.g., minimize total distance); binary search on discrete derivative as equivalent.
• CF 1800: Ternary search on a real-valued parameter with tight precision requirements ($\epsilon ={10}^{-9}$); nested ternary search in 2D.
• CF 2100: Ternary search inside DP optimization; identifying hidden unimodality in complex cost functions; ternary search on answer with simulation inside.

#	Problem	Source	Difficulty	Key Idea
1	Find Peak Element	LeetCode 162	1100	Discrete peak finding, binary search on derivative
2	The Meeting Place Cannot Be Changed	CF 782B	1300	Ternary / binary search on real-valued answer
3	Restorer Distance	CF 1355E	1500	Ternary search on discrete convex cost
4	Devu and his Brother	CF 439D	1500	Ternary search on parameter / convex cost
5	Weakness and Poorness	CF 578C	1800	Ternary search on real parameter, tricky precision
6	Vanya and Brackets	CF 552C	1600	Enumerate bracket placement—unimodal subproblem
7	Jobs	CSES	1400	Binary search on answer, can frame as unimodal
8	Minimum Average Difference	LeetCode 2256	1300	Discrete unimodal—prefix sums + scan or ternary

---

Common Mistakes

A contestant used while (lo < hi) as the termination condition for integer ternary search. When lo + 1 == hi, both m1 and m2 equaled lo, the comparison f(m1) < f(m2) was always false, and hi never changed—infinite loop. The fix: terminate when lo + 2 >= hi and brute-force check the remaining 2–3 candidates. Integer ternary search always needs a small brute-force base case.

---

Debug Drills

Drill 1.

// Ternary search for maximum of unimodal f on [lo, hi]
while (hi - lo > 2) {
    int m1 = lo + (hi - lo) / 3;
    int m2 = hi - (hi - lo) / 3;
    if (f(m1) < f(m2))
        lo = m1;  // Bug here
    else
        hi = m2;
}

What's wrong?

Setting lo = m1 instead of lo = m1 + 1 can cause an infinite loop when hi - lo == 3 (then m1 == lo + 1 and lo might not advance). Use lo = m1 + 1 and hi = m2 - 1 (or equivalently lo = m1 only if you guarantee strict shrinkage with the termination condition).

Drill 2.

// Real-valued ternary search
double lo = 0, hi = 1e9;
for (int iter = 0; iter < 100; iter++) {
    double m1 = lo + (hi - lo) / 3;
    double m2 = hi - (hi - lo) / 3;
    if (f(m1) > f(m2))  // Looking for minimum
        lo = m1;
    else
        hi = m2;
}

What's wrong?

When searching for the minimum, if f(m1) > f(m2), the minimum is not in [lo, m1], so lo = m1 is correct. But 100 iterations shrinks the range by $(2/3{)}^{100}\approx 2.5\times {10}^{-18}$, which on a range of ${10}^9$ gives precision $\sim {10}^{-9}$—borderline. Use 200 iterations to be safe, or switch to while (hi - lo > 1e-9).

Drill 3.

// Discrete ternary search, but function is not unimodal
auto cost = [&](int x) {
    // cost goes down, then up, then down again (bimodal!)
    return abs(x - 10) + abs(x - 50);
};
// Ternary search on [0, 100]
int lo = 0, hi = 100;
while (hi - lo > 2) {
    int m1 = lo + (hi - lo) / 3;
    int m2 = hi - (hi - lo) / 3;
    if (cost(m1) < cost(m2)) hi = m2; else lo = m1;
}

What's wrong?

The function |x-10| + |x-50| is actually unimodal (convex, with minimum on the plateau $[10,50]$), so ternary search works here. But the real bug is the search direction: cost(m1) < cost(m2) means m1 is better (lower cost for a minimum search), so we should discard the right portion: hi = m2. The code does this, but the else branch sets lo = m1 instead of lo = m1 + 1, risking an infinite loop.

---

Further Reading

• cp-algorithms: Ternary Search—clean writeup with proof of convergence.
• CF Blog: Ternary Search—community discussion on when ternary search beats alternatives.
• CF Blog: Binary search vs ternary search—analysis of when to use derivative-based binary search instead.
• Prerequisite: Binary Search
• Related: Convex Hull Trick / DP Optimization—when the unimodal structure comes from DP transitions.