Тернарный поиск
Дана функция , которая является унимодальной на интервале .
Под унимодальной функцией понимается одно из двух её поведений:
Предположим, что функция имеет второе свойство, и требуется найти максимальное значение
при .
Разделим текущий интервал на три части. Пусть
Рассмотрим возможные случаи:
Если , то максимум не может находиться в левой части, поэтому
.
Если , то по симметричной логике максимум не может находиться в правой части, поэтому
.
Если , то максимум находится между и . В этом случае можно отбросить как первую, так и третью часть, но для простоты реализации обычно отбрасывают одну из них (например, вторую).
Повторяя этот процесс, мы постепенно сужаем интервал, содержащий точку максимума.
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);
}