Тернарный поиск можно использовать только для функций, которые строго возрастают и строго убывают. Здесь и далее мы будем рассматривать дискретную версию тернарного поиска (когда аргумент функции задается целым числом), но все рассуждения легко переносятся на вещественные функции.
Пускай у нас есть функция \(f(x)\), определенная на промежутке неотрицательных чисел \([0,n-1]\). Чтобы тернарный поиск работал, необходимо условие \(f(x) \ne f(x+1), x < n-1\).
И вот это условие часто ломает все возможности засунуть в задачу тернарный поиск, так как функция может где-то неубывать.
Мы рассмотрим алгоритм TOF, позволяющий производить поиск экстремума битонической функции при возможности неубывания и невозрастания ее на участках. К сожалению, автор слышал о нем, только благодаря этому блогу, если вы знаете какие-то источники еще, пожалуйста, сообщите об этом tg:@alexok2006/email:alexok2006@gmail.com.
Давайте разделим всю функцию на блоки, каждый по \(S\) элементов. Всего будет \(\lceil \frac{n}{S} \rceil \) блоков. Это похоже на разбиение, как в корневой декомпозиции.
Теперь определим \(g(y)\), как минимум по \(y\)-му блоку, то есть \(min({f(y \times S), f(y \times S + 1)...f(y \times S + S-1)})\)
А теперь просто произведем тернарный поиск по \(g(y)\). При достаточно большом \(S\) функция будет строго возрастающей/убывающей, чего будет достаточно для тернарного поиска.
Итоговая асимптотика: \(O( log_{3/2}{(\frac{n}{S})} \times S)\). Нужно выбрать такое \(S\), чтобы \(g(y)\) строго возрастало и строго убывало.
Во-первых, в худшем случае (\(f(x)\) не изменяется на больших промежутках) придется делать \(S = n\). Во-вторых, достаточно редко необходим именно такой тернарный поиск.
Благодаря такому "сжатию" можно делать тернарный поиск даже для функций, у которых могут быть небольшие "неровности".
В любом случае метод интересен для ознакомления.