Троичный поиск

Эта статья находится в разработке!

Троичный поиск — метод поиска минимума или максимума функции на отрезке.

Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).

Пусть функция [math]f(x)[/math] на отрезке [math][a, b][/math] имеет минимум, и мы хотим найти точку [math]x_{min}[/math], в которой он достигается.

Посчитаем значения функции в точках [math] x_1 = a + \frac{(b-a)}{3} [/math] и [math] x_2 = a + \frac{2(b-a)}{3} [/math]. Так как в точке [math]x_{min}[/math] минимум, то до нее на отрезке [math][a, b][/math] функция убывает, а после нее — возрастает, то есть [math] \forall x', x'' \in [a, b]: \\ a \lt x' \lt x'' \lt x_{min} \Rightarrow f(a) \gt f(x') \gt f(x'') \gt f(x_{min}) \\ x_{min} \lt x' \lt x'' \lt b \Rightarrow f(x_{min}) \lt f(x') \lt f(x'') \lt f(b) [/math].

Значит если [math]f(x_1) \lt f(x_2)[/math], то [math]x_{min} \in [a, x_2][/math], аналогично из [math]f(x_1) \gt f(x_2)[/math] следует [math] x_{min} \in [x_1, b][/math]. Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть [math] b-a \lt \varepsilon [/math].