Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение тернарного поиска

Тернарный поиск - метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.

---

Принцип работы алгоритма

Тернарный поиск  определяет, что минимум или максимум не может лежать либо в первой, либо в последней трети области, и затем повторяет поиск на оставшихся двух третях.

Пояснение:

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

---

Схематическая работа алгоритма

Есть некоторая функция $f(x) = x^2$:

Необходимо найти минимум или максимум функции

Шаг первый

Необходимо разделить исследуемый диапазон на 3 области для поиска минимума или максимума функции:

## Шаг второй

Нужно сравнить границы областей:

$f(\frac{2L+R}3) < f(\frac{L+2R}3)$

Шаг третий

На основе сравнения отсекается меньшая треть - то есть первая:

Шаг четвёртый

Совершается та же последовательность действий, пока не достигается установленная точность:

---

Вычислительная сложность

Вычислительная сложность алгоритма равна $O(\frac{log(\frac{3}2)((r-l)}e)$, где e - необходимая точность, l - левая граница, r - правая граница.

---

Псевдокод

Функция тернарный_поиск(функция, правая_граница, левая_граница, погрешность)
    Пока правая_граница - левая_граница > погрешность
        первая_треть = (2 * левая_граница + правая_граница) // 3
        третья_треть = (левая_граница + 2 * правая_граница) // 3
        Если функция(первая треть) < функция(третья треть)
            правая_граница = третья_треть
        Иначе
            левая_граница = первая_треть
    Вернуть (левая_граница + правая_граница) // 2

---

Реализация на Python

Аннотация:
ternarySearch - алгоритм тернарного поиска
func - минимум функции, который нужно найти
left - левая граница отрезка поиска
right - правая граница отрезка поиска
eps - точность поиска

def ternary_search(func, left: float, right: float, eps: float) -> float:
    while right - left > eps:
        m1 = left + (right - left) / 3
        m2 = right - (right - left) / 3
        if func(m1) < func(m2):
            right = m2
        else:
            left = m1
    return (left + right) / 2

def ternary_search_array(array, left: int, right: int) -> int:
    while right - left > 1:
        m1 = left + (right - left) // 3
        m2 = right - (right - left) // 3
        if array[m1] < array[m2]:
            right = m2
        else:
            left = m1
    return left if array[left] < array[right] else right

---

Олимпиадная реализация на C++

Аннотация:
ternary_search - алгоритм тернарного поиска
f - указатель на функцию, для которой необходимо найти экстремум
l - левая граница отрезка поиска
r - правая граница отрезка поиска
e - точность поиска

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

double ternary_search(function<double(double)> f, double l, double r, double e) {
    while (r - l > e) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) < f(m2))
            r = m2;
        else
            l = m1;
    }
    return (l + r) / 2;
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
ternary_search - алгоритм тернарного поиска
func - функция, для которой ищем минимум
left - левая граница отрезка
right - правая граница отрезка
eps - точность поиска

#include <iostream>
#include <vector>
#include <functional>

template <typename T, typename Func>
T ternary_search(Func func, T left, T right, T eps) {
    while (right - left > eps) {
        T m1 = left + (right - left) / 3;
        T m2 = right - (right - left) / 3;
        if (func(m1) < func(m2))
            right = m2;
        else
            left = m1;
    }
    return (left + right) / 2;
}