Изменения
Нет описания правки
{{В разработке}}
'''Троичный поиск''' (или ''тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке.
== Алгоритм ==
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).
Значит если <tex>f(a) < f(b)</tex>, то <tex>x_{min} \in [l, b]</tex>,
аналогично из <tex>f(a) > f(b)</tex> следует <tex> x_{min} \in [a, gr]</tex>.
Тогда нам нужно изменить границы поиска и искать дальше,
пока не будет достигнута необходимая точность, то есть <tex> r-l < \varepsilon </tex>.
=== Псевдокод:===
return (left + right) / 2
a = (left * 2 + right) / 3
b = (left + right * 2) / 3
if (f(a) < f(b))
return ternarySearch(f, l, b, eps)
else
return ternarySearch(f, a, r, eps)
end
Возможен и нерекурсивный вариант:
ternarySearchMin(f, l, r, eps)
while (r - l < eps)
{
a = (left * 2 + right) / 3
b = (left + right * 2) / 3
if (f(a) < f(b))
r = b
else
l = a
}
return (left + right) / 2
end
=== Время работы ===
Так как на каждой итерации мы считаем 2 значения функции и уменьшаем область поиска в полтора раза, пока <tex> r - l > \varepsilon</tex>,
то время работы алгоритма составит
<tex>2 \log_{\frac32} \left(\frac{r - l}{\varepsilon}\right)</tex>
