Suppose we are given a function that is unimodal on the interval .
A unimodal function has one of the following two forms:
In this note, we assume that the function has the second form, so our goal is to find the maximum value of
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
The idea of ternary search is to split the current interval into three parts.
Let
Then we compare the values and .
There are three cases:
By repeating this process many times, we make the interval very small and approach the point where the maximum is achieved.
double ternary_search(double l, double r) {
for (int it = 0; it < 200; it++) {
double m1 = l + (r - l) / 3.0;
double m2 = r - (r - l) / 3.0;
if (f(m1) < f(m2)) {
l = m1;
} else {
r = m2;
}
}
return f(l);
}