Ҷустуҷӯи тернарӣ
Функсияи дода шудааст, ки дар фосилаи унимодалӣ мебошад.
Зери функсияи унимодалӣ яке аз ду рафтори он фаҳмида мешавад:
Фарз мекунем, ки функсия хосияти дуюм дорад, ва лозим аст қимати максималӣ-и
-ро ҳангоми ёфт.
Фосилаи ҷориро ба се қисм ҷудо мекунем. Бигзор
Ҳолатҳои имконпазирро баррасӣ мекунем:
Агар , пас максимум дар қисми чап буда наметавонад, бинобар ин
.
Агар , пас бо мантиқи симметрӣ максимум дар қисми рост буда наметавонад, бинобар ин
.
Агар , пас максимум байни ва ҷойгир аст. Дар ин ҳолат метавон ҳам қисми якум ва ҳам қисми сеюмро партофт, аммо барои соддагии татбиқ одатан яке аз онҳоро (масалан, дуюмро) мепартоянд.
Ин равандро такрор карда, мо тадриҷан фосиларо, ки нуқтаи максимумро дар бар мегирад, танг мекунем.
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);
}