Ternary search
We need ternary search to find the maximum or minimum of a unimodal function on the segment
[l, r]. A function is unimodal when it has one extremum on a segment.
The search for the maximum values of a function is often used for optimization problems. For example, we need to find the maximum possible angle of a right triangle, at which the area will be the largest. To do this, we will go through the angles from
0 to
90, and on this segment we are looking for an area that will first increase and then decrease, i.e. the function will be unimodal.
How it works
The principle of operation is similar to binary search, but we may have a case when dividing the segment in half, when the middle of the segment falls exactly on the extremum, and & nbsp; we will not get a clear result.
Therefore, to avoid such a case, it is necessary to divide the segment not into two parts, but into three, and we discard the part in which there is no extremum, etc., until the boundaries converge on the result.
double f( double hypo, double alpha ) {
alpha = (alpha *M_PI)/180;
return 0.5 * hypo * hypo * cos(alpha) * sin(alpha);
}
int main() {
double l = 0;
double r = 90;
double EPS = 1e-6;
double hypo = 100;
while (r - l >=EPS) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(hypo, m1) < f(hypo, m2)) {
l=m1;
}
else {
r=m2;
}
}
out<< ((l + r) / 2);
return 0;
}
Ternary search can be modified using golden section method, which increases the convergence rate by about 2 times.
Sources
1) ternary search and golden ratio
2) ternary search