Ternary Search
Optimize a unimodal function on a discrete or continuous domain by keeping the side that still contains the optimum.
Ternary Search
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Ternary search is the search pattern for one-dimensional optimization when the objective is unimodal: it moves in one direction until the optimum, then moves in the other direction after the optimum. The contest version is usually ``the function is convex / concave enough on one variable that I can compare two interior points and discard one side.''
When to Use It
Use ternary search when:
the answer is the minimum or maximum of a function \(f(x)\),
the domain is one-dimensional,
\(f\) is unimodal on the searched interval,
evaluating \(f(x)\) is much cheaper than enumerating every candidate.
Typical contest signals are: ``choose one coordinate'', ``best time / angle / height'', and ``the cost is convex after the rest of the variables are fixed.''
Core Idea
Pick two interior points \(m_1 < m_2\).
For minimization, if \(f(m_1) \le f(m_2)\), then the optimum cannot lie strictly to the right of \(m_2\).
If \(f(m_1) > f(m_2)\), then the optimum cannot lie strictly to the left of \(m_1\).
So every comparison removes a constant fraction of the current interval.
Key Insight
The search works because unimodality is stronger than ``there is one best point.'' It says the function has only one direction change. Without that structural promise, comparing \(f(m_1)\) and \(f(m_2)\) does not tell you which side is safe to discard.
Worked Problem
Problem.
There are \(n\) drones on a line. Drone \(i\) starts at position \(p_i\) and flies with speed \(s_i\). Choose a real meeting point \(x\) that minimizes the time until all drones can reach it.
Why ternary search fits.
The objective is \[ f(x) = \max_i \frac{|x - p_i|}{s_i}. \] Each term is a V-shaped convex function. The maximum of convex functions is still convex, so \(f(x)\) is unimodal for minimization.
Algorithm outline.
Search on \([\min p_i, \max p_i]\).
Evaluate \(f(m_1)\) and \(f(m_2)\).
Keep the half that still contains the minimum.
Stop after enough iterations for the required precision.
Correctness Intuition
For a convex function, once the value at \(m_1\) is already no larger than the value at \(m_2\), the right side has started climbing or is not better than the left-middle region. So the minimizer cannot be hidden strictly beyond \(m_2\). The symmetric argument handles the other case.
Complexity Analysis
If one evaluation of \(f(x)\) costs \(T\), then:
continuous ternary search costs \(O(T \cdot I)\), where \(I\) is the chosen number of iterations,
discrete ternary search costs \(O(T \log R)\) until the interval becomes small enough to brute-force.
Implementation
The code includes:
a floating-point ternary search template,
a sample evaluator for the drone meeting-time problem above.
For integer domains, I usually shrink with ternary search until only a handful of candidates remain, then test them all.
Common Pitfalls
Using ternary search on a function that has multiple local optima.
Applying it to integers without a final brute-force cleanup.
Searching on a wider interval than the real feasible region and losing precision.
Forgetting that many ``convex-looking'' formulas become non-unimodal after hidden constraints are introduced.
Variants / Extensions
Discrete ternary search on arrays or DP transition indices.
Binary search on the derivative sign when the derivative is monotone.
Parametric reformulations where the optimization can be turned into a monotone decision problem instead.
Practice Problems
Choose one real coordinate minimizing the worst travel time.
Maximize a concave score depending on one continuous parameter.
Optimize one split point after all other combinatorial choices are fixed.
References
Code
Contest-ready reference implementation for the idea explained above.
template <class F>
double ternary_search_real(double lo, double hi, F f, int iterations = 200) {
for (int it = 0; it < iterations; ++it) {
double m1 = lo + (hi - lo) / 3.0;
double m2 = hi - (hi - lo) / 3.0;
if (f(m1) <= f(m2)) {
hi = m2;
} else {
lo = m1;
}
}
return (lo + hi) * 0.5;
}
double minimum_meeting_time(const vector<double>& position, const vector<double>& speed) {
double lo = *min_element(position.begin(), position.end());
double hi = *max_element(position.begin(), position.end());
auto cost = [&](double x) {
double worst = 0.0;
for (int i = 0; i < (int)position.size(); ++i) {
worst = max(worst, abs(position[i] - x) / speed[i]);
}
return worst;
};
double best_x = ternary_search_real(lo, hi, cost);
return cost(best_x);
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.