Тернарный поиск

Пусть дана функция 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;
}

Можно говорить, что тернарный поиск - это обобщение бинарного поиска.