Ternary search
A function is given, which is unimodal on the interval .
A unimodal function is understood as one of two behaviors:
Assume that the function has the second property, and it is required to find the maximum value
for .
Divide the current interval into three parts. Let
Consider the possible cases:
If , then the maximum cannot be in the left part, therefore
.
If , then by symmetric logic the maximum cannot be in the right part, therefore
.
If , then the maximum lies between and . In this case, you can discard both the first and the third part, but for simplicity of implementation they usually discard one of them (for example, the second).
By repeating this process, we gradually narrow the interval containing the point of maximum.
double ternary_search(double l, double r) {
for (int it = 0; it < 200; it++) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(m1) < f(m2)) {
l = m1;
} else {
r = m2;
}
}
return f(l);
}