Тернарный поиск: как найти максимум унимодальной функции

Коротко

Бинарный поиск находит границу между «нет» и «да». Тернарный ищет вершину — точку максимума или минимума.

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

Бинарный поиск требует монотонности: значения должны идти по возрастанию или убыванию. Но что делать с функцией, которая сначала растёт, а потом падает?

значение
    |        ▲
    |      ▲   ▲
    |    ▲       ▲
    |  ▲           ▲
    |▲               ▲
    +-------------------→ x
         ищем вершину

Монотонности нет, поэтому бинарный поиск неприменим. Зато есть унимодальность — ровно один экстремум, и этого достаточно.

Что такое унимодальность

Функция унимодальна на отрезке, если она:

• строго возрастает до некоторой точки, затем строго убывает (максимум), или
• строго убывает до точки, затем возрастает (минимум).

Ключевое слово — ровно один экстремум. Если функция колеблется, алгоритм найдёт какой-то локальный экстремум, но не обязательно глобальный.

Идея алгоритма

Делим отрезок на три части двумя точками m1 и m2:

left -------- m1 -------- m2 -------- right

Сравниваем f(m1) и f(m2) (ищем максимум):

• f(m1) < f(m2) — максимум точно правее m1, отбрасываем левую треть: left = m1;
• f(m1) > f(m2) — максимум левее m2, отбрасываем правую треть: right = m2.

Почему это верно: если бы максимум был левее m1 при f(m1) < f(m2), функция должна была бы убывать после него, и f(m2) не могло бы оказаться больше. Противоречие с унимодальностью.

Каждая итерация уменьшает отрезок на треть, поэтому шагов O(log n).

Вещественный случай

Для непрерывной функции делаем фиксированное число итераций.

def ternary_search_max(f, left: float, right: float, iterations: int = 200) -> float:
    for _ in range(iterations):
        m1 = left + (right - left) / 3
        m2 = right - (right - left) / 3

        if f(m1) < f(m2):
            left = m1        # максимум правее
        else:
            right = m2       # максимум левее

    return (left + right) / 2


# парабола с максимумом в точке x = 3
f = lambda x: -(x - 3) ** 2 + 10

x = ternary_search_max(f, -10, 10)
print(round(x, 6), round(f(x), 6))   # 3.0 10.0

Почему фиксированное число итераций, а не условие right - left > eps. С вещественными числами из-за ошибок округления условие может не выполниться никогда, и цикл зависнет. 200 итераций уменьшают отрезок в (2/3)²⁰⁰ раз — точность заведомо превышает возможности float.

Целочисленный случай

Здесь тернарный поиск ведёт себя коварно. Наивный перенос кода зацикливается: при малом отрезке m1 и m2 могут совпасть или не сдвинуть границы.

Надёжный приём — свести отрезок к нескольким элементам и добить перебором.

def ternary_search_int(f, left: int, right: int) -> int:
    while right - left > 2:
        m1 = left + (right - left) // 3
        m2 = right - (right - left) // 3

        if f(m1) < f(m2):
            left = m1 + 1
        else:
            right = m2

    # остался крошечный отрезок — проверяем перебором
    return max(range(left, right + 1), key=f)


values = [1, 3, 7, 12, 9, 4, 2]
best = ternary_search_int(lambda i: values[i], 0, len(values) - 1)
print(best, values[best])   # 3 12

Альтернатива для целых чисел — бинарный поиск по разности соседей. Функция f(i+1) - f(i) монотонно меняет знак в точке экстремума, и это уже задача для бинарного поиска:

def find_peak(values: list[int]) -> int:
    left, right = 0, len(values) - 1

    while left < right:
        mid = (left + right) // 2
        if values[mid] < values[mid + 1]:
            left = mid + 1       # растём — вершина правее
        else:
            right = mid          # падаем — вершина левее или здесь

    return left


print(find_peak([1, 3, 7, 12, 9, 4, 2]))   # 3

Этот вариант короче, надёжнее и работает за то же O(log n). Для целых чисел его стоит предпочитать — меньше шансов ошибиться с границами.

Практические задачи

Оптимальная точка на прямой. Есть точки на плоскости, нужно найти на оси X место для склада, минимизирующее сумму расстояний. Функция суммы расстояний унимодальна.

def optimal_position(points: list[tuple]) -> float:
    def total_distance(x: float) -> float:
        return sum(((px - x) ** 2 + py ** 2) ** 0.5 for px, py in points)

    # ищем минимум — меняем знак сравнения
    left, right = -1000.0, 1000.0
    for _ in range(200):
        m1 = left + (right - left) / 3
        m2 = right - (right - left) / 3
        if total_distance(m1) > total_distance(m2):
            left = m1
        else:
            right = m2

    return (left + right) / 2


print(round(optimal_position([(0, 1), (4, 1), (2, 3)]), 3))

Максимум параболы в физических задачах — дальность броска, оптимальная скорость.

Пик в массиве — классическая задача с собеседований: найти элемент, который больше обоих соседей.

Оптимизация параметра. Например, подобрать размер буфера или частоту синхронизации, где слишком мало и слишком много одинаково плохо.

Сравнение с бинарным поиском

Обратите внимание на последнюю строку: тернарный поиск делает два вычисления функции на итерацию против одного у бинарного. Если функция дорогая, это заметно.

Поэтому на практике для целых чисел почти всегда выгоднее свести задачу к бинарному поиску по разности, как показано выше.

Частые ошибки

Применение к неунимодальной функции. Алгоритм вернёт какой-то локальный экстремум и не сообщит об ошибке. Унимодальность нужно доказывать, а не предполагать.

Зацикливание на целых числах. При right - left <= 2 точки m1 и m2 перестают разделять отрезок. Обязательно добивайте перебором.

Условие выхода по точности с вещественными. Может не сработать из-за округления.

Перепутанный знак при поиске минимума. Для минимума сравнение переворачивается: if f(m1) > f(m2): left = m1.

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

Что запомнить

• Тернарный поиск находит экстремум унимодальной функции за O(log n).
• Отрезок делится на три части, отбрасывается треть на основе сравнения двух точек.
• Для вещественных чисел делайте фиксированное число итераций, а не проверку точности.
• Для целых чисел надёжнее бинарный поиск по разности соседних элементов.
• Унимодальность обязательна — при нескольких экстремумах результат непредсказуем.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→