Изменения

'''Троичный поиск''' (или ''тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке.

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

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

Значит если <tex>f(x_1a) < f(x_2b)</tex>, то <tex>x_{min} \in [al, x_2b]</tex>, аналогично из <tex>f(x_1a) > f(x_2b)</tex> следует <tex> x_{min} \in [x_1a, bg]</tex>. Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть <tex> br-a l < \varepsilon </tex>. Псевдокод:  ternarySearch(l, r, eps) if (r-l < eps) return (left + right) / 2 a = (left * 2 + right) / 3 b = (left + right * 2) / 3 if (f(a) < f(b)) return ternarySearch(f, a, r, eps) else return ternarySearch(f, l, b, eps) end