BitNeBolt
@BitNeBolt

Как найти наибольшее значение у такой функции?

61defd29bfa8a271411731.png
Ответ должен находиться на [lo; hi]

Как можно адаптировать под неё бинпоиск? Как проверять, слева или справа от mid находится наибольшее значение?
  • Вопрос задан
  • 91 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Если ваша функция унимодальная (сначала возрастающая, потом убывающая), то можно применить троичный поиск.

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

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

Войдите, чтобы написать ответ

Похожие вопросы