Пусть дана функция f(x), унимодальная на некотором отрезке [l;r] (т.е. сначала строго возрастает, потом достигает максимума (в одной точке или целом отрезке), потом строго убывает; или наоборот: убывает, достигает минимума, возрастает). Будем рассматривать первый вариант, с максимумом, второй будет симметричен ему.
Итак, требуется найти максимум функции на отрезке [l;r]. Тогда возьмём любые две точки в этом отрезке: l < m1 < m2 < r. Посчитаем значения функции f(m1) и f(m2).
Если окажется, что f(m1) < f(m2), то искомый максимум не может находиться в левой части, т.е. в части [l;m1].
Если наоборот f(m1) > f(m2), то искомый максимум не может находиться в правой части, т.е. в части [m2;r].
Ну если f(m1) = f(m2), то по определению унимодальности это будет означать, что и m1, и m2 - точки максимума, поэтому этот случай можно произвольно отнести к первому или второму случаю.
В первом случае мы получаем, что дальше искать максимум есть смысл только в отрезке [m1;r], а во втором случае - в [l;m2]. Вот мы и нашли итерационный переход: как от отрезка [l;r] перейти к новому отрезку [l';r']. Всё, берём этот новый отрезок, в нём всё повторяем, переходим к следующему отрезку, и т.д. Рано или поздно длина отрезка станет маленькой (< заранее определённого EPS), и процесс можно останавливать - считать, например, что левый конец найденного отрезка и есть искомый максимум.
(если аргумент функции f целочисленный, то отрезок [l;r] тоже дискретный, но на корректность метода это не влияет; просто процесс надо будет останавливать, когда r-l < 3)
Наконец, осталось сказать, что точки m1 и m2 мы брали произвольными. На практике часто берут их так, чтобы [l;r] делилось на 3 равные части (потому что это проще всего написать), хотя никто не мешает брать точки m1 и m2 поближе друг к другу, чтобы ускорить сходимость.
Код:
double f (double x) {
...
}
double l = ..., r = ...;
while (r - l > EPS) { // или: for (int i=0; i<200; ++i) - задав большое количество итераций, нужная точность уж наверняка достигнется
double m1 = l + (r - l) / 3,
m2 = r - (r - l) / 3;
if (f (m1) < f (m2))
l = m1;
else
r = m2;
}
Можно говорить, что тернарный поиск - это обобщение бинарного поиска.
, другого выбора нет), но у меня с этим пока слабо