Очень большие ограничения — это вряд ли, Вы правы, зато может понадобиться делать это много раз. Я делал миллирд раз (1000 раз на миллионе рандомных чисел), и времена получались для первого метода порядка 0.8 секунды, для следующих двух — порядка 3 секунд.
Я согласен, в работе это может пригодиться, если только очень повезёт. Не могу сказать, что я в работе не использовал битовые операции и не хранил сразу много данных в одном числе, но у меня работа в данный момент спецэфическая, надо чтобы сложный алгоритм распознавания образов работал очень-очень быстро, вот и оптимизирую, как только могу.
Это, скорее, может быть интересно олимпиадным программистам. Мне на олимпиадах, по-моему, один раз приходилось это делать.
Но суть-то не в этом — просто задачка интересная, и методы решения тоже)
Вы правы. Однако, надо заметить, что тот же недостаток имеется и у тернарного поиска (правда, в меньшей степени), и у метода золотого сечения. Кроме того надо заметить, что этот метод допускает и нерекурсивную реализацию (что, опять же, в равной степени касается и тернарного поиска и поиска золотого сечения):
о да, Вы правы. Спасибо за замечание.
Правда, мой метод использует для этого не 2 вызова функции, а, в среднем, несколько меньше. Но, вероятно, метод золотого сечения действительно быстрее — там та же идея, которая является ключевой в моём методе, использована ещё лучше.
Я согласен, в работе это может пригодиться, если только очень повезёт. Не могу сказать, что я в работе не использовал битовые операции и не хранил сразу много данных в одном числе, но у меня работа в данный момент спецэфическая, надо чтобы сложный алгоритм распознавания образов работал очень-очень быстро, вот и оптимизирую, как только могу.
Это, скорее, может быть интересно олимпиадным программистам. Мне на олимпиадах, по-моему, один раз приходилось это делать.
Но суть-то не в этом — просто задачка интересная, и методы решения тоже)
double quadSearch(double L, double R) { double midValue = f((L + R)/2); double leftValue; double rightValue; while (R - L > eps) { leftValue = f((3*L + R)/4); if (leftValue < midValue) { midValue = leftValue; R = (L + R)/2; } else { rightValue = f((L + 3*R)/2); if (rightValue > midValue) { midValue = rightValue; L = (R + L)/2; } else { L = (3*L + R)/4; R = (L + 3*R)/4; } } } return (R + L) / 2; }Правда, мой метод использует для этого не 2 вызова функции, а, в среднем, несколько меньше. Но, вероятно, метод золотого сечения действительно быстрее — там та же идея, которая является ключевой в моём методе, использована ещё лучше.