Ternary Search from Scratch (2026)
Ternary search is a divide-and-conquer algorithm that splits the search space into three parts instead of two. It is used to find the maximum or minimum of a unimodal function (a function that first increases then decreases, or vice versa). With O(log base 3 of n) comparisons, it is slightly more efficient than binary search for certain types of problems.
In this tutorial, we will implement ternary search for both discrete and continuous functions, analyze its time complexity, compare it with binary search and golden section search, and explore applications in optimization problems like finding the peak of a function and minimizing maximum distance.
Ternary Search on Discrete Domain
For a unimodal function defined on a discrete domain (like an array), ternary search divides the interval [low, high] into three equal parts using two midpoints: mid1 = low + (high - low) / 3 and mid2 = high - (high - low) / 3. We compare the function values at these points. If f(mid1) < f(mid2), the maximum lies in [mid1, high]; otherwise, it lies in [low, mid2].
We repeat until the interval is small enough (high - low <= 2). Ternary search performs about 2 * log base 3 of n function evaluations, each reducing the search space by one-third.
def ternary_search(arr):
low, high = 0, len(arr) - 1
while high - low > 2:
mid1 = low + (high - low) // 3
mid2 = high - (high - low) // 3
if arr[mid1] < arr[mid2]:
low = mid1 + 1
else:
high = mid2 - 1
max_idx = low
for i in range(low + 1, high + 1):
if arr[i] > arr[max_idx]: max_idx = i
return max_idx
def ternary_search_min(func, low, high, epsilon=1e-9):
while high - low > epsilon:
m1 = low + (high - low) / 3
m2 = high - (high - low) / 3
if func(m1) > func(m2): low = m1
else: high = m2
return (low + high) / 2
def f(x): return -(x - 3)**2 + 10
result = ternary_search_min(lambda x: -f(x), 0, 10)
print(f"Peak at x = {result:.6f}, f(x) = {f(result):.6f}")Ternary Search on Continuous Domain
For continuous functions, ternary search works by narrowing the interval [low, high] using two interior points. At each step, we evaluate the function at mid1 and mid2, compare the values, and discard one-third of the search space. The process continues until the interval width is below a tolerance epsilon.
Ternary search is particularly useful for finding the optimum of convex or concave functions, optimizing parameters in machine learning, and solving geometric problems. The number of iterations needed is approximately log base 3 of ((high - low) / epsilon).
#include
#include
#include
using namespace std;
double f(double x) { return -(x - 3) * (x - 3) + 10; }
double ternarySearchMax(double low, double high, double eps) {
while (high - low > eps) {
double m1 = low + (high - low) / 3;
double m2 = high - (high - low) / 3;
if (f(m1) < f(m2)) low = m1;
else high = m2;
}
return (low + high) / 2;
}
int main() {
double result = ternarySearchMax(0, 10, 1e-9);
cout << fixed << setprecision(6);
cout << "Peak at x = " << result << endl;
cout << "f(x) = " << f(result) << endl;
} Ternary Search vs Binary Search
Binary search is designed for finding a specific value in a sorted array by comparing with the middle element. Ternary search is designed for finding the maximum or minimum of a unimodal function by comparing two interior points. Binary search uses 1 comparison per step; ternary search uses 2 comparisons per step.
For finding a value, binary search is better (O(log base 2 of n) with 1 comparison). For optimization of unimodal functions, ternary search is preferred. The golden section search is a variant that uses only 1 function evaluation per step by using the golden ratio, making it more efficient than standard ternary search.
import math
def golden_section_search(func, low, high, eps=1e-9):
phi = (1 + math.sqrt(5)) / 2
resphi = 2 - phi
x1 = low + resphi * (high - low)
x2 = high - resphi * (high - low)
f1, f2 = func(x1), func(x2)
while high - low > eps:
if f1 < f2:
low = x1
x1, f1 = x2, f2
x2 = high - resphi * (high - low)
f2 = func(x2)
else:
high = x2
x2, f2 = x1, f1
x1 = low + resphi * (high - low)
f1 = func(x1)
return (low + high) / 2Applications of Ternary Search
Ternary search is used in optimization problems where the objective function is unimodal. Common applications include minimizing the maximum distance in geometric problems, optimizing convex functions, finding the best parameter in machine learning models, and solving problems like minimum radius to cover all points or maximum minimum distance.
In competitive programming, ternary search is the go-to approach for problems with unimodal functions. It is also used in real-time systems where a quick optimization is needed, and in game theory for finding optimal strategies in continuous action spaces.
import java.util.*;
public class TernarySearchApps {
static double minMaxDistance(double[] points) {
double low = 0, high = 1e9;
for (int iter = 0; iter < 100; iter++) {
double m1 = low + (high - low) / 3;
double m2 = high - (high - low) / 3;
double maxD1 = 0, maxD2 = 0;
for (double p : points) {
maxD1 = Math.max(maxD1, Math.abs(p - m1));
maxD2 = Math.max(maxD2, Math.abs(p - m2));
}
if (maxD1 < maxD2) high = m2;
else low = m1;
}
return low;
}
}Frequently Asked Questions
When to use ternary search vs binary search?
Use ternary search for finding maximum/minimum of unimodal functions. Use binary search for finding a value in sorted arrays or for binary search on answer space.
What is a unimodal function?
A unimodal function has exactly one peak (or valley) in the search interval. It first increases then decreases (or vice versa). Examples: parabola, Gaussian, single-peaked distributions.
How many iterations does ternary search need?
Ternary search needs about log base 3 of ((high-low)/epsilon) iterations for continuous functions. For discrete domains, it needs about 2*log base 3 of n function evaluations.
What is golden section search?
Golden section search is an optimization of ternary search that uses only 1 function evaluation per step (instead of 2) by using the golden ratio. It is more efficient for expensive function evaluations.
Originally published on Ayodhyyya. Last updated June 1, 2026.