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

Как работает тернарный поиск?

Тернарный поиск — это алгоритм для нахождения максимума или минимума унимодальной функции (функции, которая сначала возрастает, а потом убывает, или наоборот).

    f(x)
     ↑
     │    ╱╲
     │   ╱  ╲
     │  ╱    ╲
     │ ╱      ╲
     │╱        ╲
     └──────────→ x
        l    r

Пример унимодальной функции (сначала ↗, потом ↘)

Основная идея

Если функция унимодальна (сначала возрастает, потом убывает, или наоборот), то максимум (или минимум) можно найти, сравнивая значения в двух внутренних точках.

Пошаговое объяснение

Имеем отрезок [l, r), на котором ищем максимум
Пока длина отрезка больше 2, делим его на три части:

m1 = l + (r - l) / 3
m2 = r - (r - l) / 3

Сравниваем f(m1) и f(m2):
- Если f(m1) < f(m2) → максимум правее m1, сдвигаем l = m1
- Иначе → максимум левее m2, сдвигаем r = m2
Когда осталось 2-3 точки, перебираем их и находим максимум

Почему это работает?

Если f(m1) < f(m2), то m1 не может быть максимумом (справа есть большее значение), и всё, что левее m1 — тоже
Если f(m1) > f(m2), то m2 не может быть максимумом, и всё, что правее m2 — тоже
За одну итерацию отрезок сокращается в ≈1.5 раза

Временная сложность: O(log n) — за каждый шаг отрезок уменьшается в 1.5 раза.

Когда применяется:

Поиск максимума/минимума выпуклой/вогнутой функции
Оптимизационные задачи на отрезке
Поиск точки экстремума, когда функция непрерывна и унимодальна

Пример работы

Пусть функция f(x) = -(x-5)² + 25 (парабола ветвями вниз, максимум в x=5). Ищем максимум на отрезке [0, 10].

Шаги алгоритма:

Начало: l=0, r=10
Шаг 1: m1 = 0 + (10-0)/3 = 3, m2 = 10 - (10-0)/3 = 7
       f(3) = -(3-5)²+25 = 21, f(7) = -(7-5)²+25 = 21
       f(3) == f(7) → сдвигаем l = 3, r = 7

Шаг 2: m1 = 3 + (7-3)/3 = 4, m2 = 7 - (7-3)/3 = 6
       f(4) = 24, f(6) = 24
       f(4) == f(6) → сдвигаем l = 4, r = 6

Шаг 3: m1 = 4 + (6-4)/3 = 4, m2 = 6 - (6-4)/3 = 6
       r - l = 2 → останавливаемся

Перебираем точки 4, 5, 6: f(4)=24, f(5)=25, f(6)=24
Максимум в x = 5

Ответ: x = 5 (максимум функции)