Uchlik qidiruv
funksiyasi berilgan bo‘lib, u oraliqda unimodal hisoblanadi.
Unimodal funksiya deganda uning quyidagi ikki xatti-harakatidan biri tushuniladi:
Faraz qilaylik, funksiya ikkinchi xususiyatga ega, va da
ning ni topish talab etiladi.
Joriy oraliqni uch qismga bo‘lamiz. Quyidagicha bo‘lsin:
Mumkin bo‘lgan holatlarni ko‘rib chiqamiz:
Agar bo‘lsa, maksimum chap qismda bo‘la olmaydi, shuning uchun
.
Agar bo‘lsa, simmetrik mantiqqa ko‘ra maksimum o‘ng qismda bo‘la olmaydi, shuning uchun
.
Agar bo‘lsa, maksimum va orasida joylashgan. Bu holda ham birinchi, ham uchinchi qismni tashlab yuborish mumkin, ammo amalga oshirish soddaligi uchun odatda ulardan birini (masalan, ikkinchisini) tashlab yuborishadi.
Bu jarayonni takrorlab, biz maksimum nuqtasini o‘z ichiga olgan oraliqni asta-sekin toraytiramiz.
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);
}