Тернарный поиск (троичный поиск)

Четвертое видео из серии, посвященной олимпиадным алгоритмам.
Начало здесь:
• Метод двух указателей.... -- метод двух указателей;
• Бинарный поиск (двоичн... -- бинарный поиск, бинарный поиск по ответу;
• Вещественный двоичный ... -- вещественный бинарный поиск.
Троичный (тернарный) поиск -- алгоритм, позволяющий найти минимум или максимум функции на некотором отрезке.
Исходники:
disk.yandex.ru...
Тренируйтесь с нами: t.me/+8KWl7n_T...
По воскресеньям мы проводим тренировки по программированию для школьников:
1. Решаем задачи, как на олимпиаде (обычно это задачи реальных олимпиад прошлых лет различных регионов).
2. Разбираем задачи (рассказываем идеи решения задач, показываем удачные решения участников, иногда пишем куски кода).
3. Дорешиваем задачи (реализуем озвученные идеи решения, сдаем в тестирующую систему).
Участие в тренировках бесплатное, посещение свободное. Мы верим, что это полезно и делает мир лучше. Если согласны - присоединяйтесь :)
Можно участвовать очно (если вы рядом) или онлайн.
Платформы: codeforces.com, informatics.ms...
Чтобы участвовать онлайн, добавляйтесь в группу codeforces.com... и следите за анонсами в чате t.me/+8KWl7n_T....
#информатика #программирование #олимпиада #информатикарулит

[@tochechka3_3]

Спасибо за объяснение, четко и понятно

[@Рамко-о9з]

10:08 орнул

[@СалаватФайзуллин-щ3д]

Здравствуйте, на 5:09 появился вопрос, ведь может быть такое что на отрезке 1 наша функция сильно убывает и на отрезке 2 тоже очень сильно убывает, и тогда минимум находится в отрезке 3. Подскажите пожалуйста, где я неправ(

[@binom-education]

Добрый день, Салават. Тернарный поиск корректно работает, если функция на отрезке [L;R] имеет один минимум. То есть до некоторой точки убывает, а потом возрастает. Если функция убывает все время, ответ будет в R (тоже корректно). Если минимумов несколько, будет найден какой-то (случайный) из них.
Если минимум один и находится на отрезке 3, то f(m1) > f(m2), и алгоритм будет двигать левую границу.

[@СалаватФайзуллин-щ3д]

@@binom-education Ясно, спасибо большое за объяснение