Бинарный поиск математической функции

Question

У меня есть возрастающая математическая функция, например y = x + 5*x^3 + x^7 + 11*ln x и я хочу найти первую (положительную) x такую, что y(x) >= 1478. Могу ли я использовать алгоритм бинарного поиска из stl для решения этой проблемы?

Answer 1

Проблема в том, что алгоритмы STL (std::lower_bound, вероятно, ваш кандидат на выбор) работают над коллекциями. Или более конкретно: на итераторах коллекций. Один из способов использования их для вашей проблемы - это адаптер: вы пишете «итератор», который просто возвращает значение функции при разыменовании.

Код для этого может быть довольно большим, так как вам необходимо удовлетворить все требования RandomAccessIterator. Однако вы можете запланировать его на своей функции. Пример:

template<class F> 
FuncIterator{ 
    typedef int ParamType; 
    typedef float ResultType; // Or better: result_of F 

    ParamType param_; 
    FuncIterator(ParamType param): param_(param){} 
    ResultType operator*(){ return F(param_); } 
    FuncIterator& operator+=(int diff){ param_ += diff; return *this; } 
    //... Other functions required for RandomAccessIterator 
} 

auto result = std::lower_bound(FuncIterator<MyFunc>(0), FuncIterator<MyFunc>(1000)); 
std::cout << "First x value is:" result.param_ << std::endl; 

Опять же: этот итератор более сложный, чем здесь, но вы должны получить отсюда. Вам нужны некоторые определения и возможные черты. Но вам нужно определить его только один раз и использовать его для любой функции. Он становится более общим, если вы используете std-признаки, чтобы вывести тип параметра и результат F.

Заключительное примечание: двоичный поиск выполняет поиск только в диапазоне! Поэтому вы должны решить этот диапазон при вызове std::lower_bound. Он не может найти «первое значение x с F(x)>=y» для любое x, но только для любого x в заданном диапазоне.