Binary search for math function

Question

I have an increasing math function, for example y = x + 5*x^3 + x^7 + 11*ln x and I want to find first (positive) x such that y(x) >= 1478. Can I use binary search algorithm from stl to solve this problem?

Answer 1

The problem is, that STL algorithms (std::lower_bound is probably your candidate of choice) work on collections. Or more specific: on iterators of collections. One way to use them for your problem is an adapter: You write an 'iterator' that simply returns the functions value on dereferencing.

The code for this might be pretty big as you need to satisfy all requirements of a RandomAccessIterator. However you can templatize it on your function. Example:

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;

Again: That iterator is more complex than show here, but you should get further from here. You need some defines, and possible traits. But you need to define it only once and can reuse it for any function. It gets more generic, if you use the std traits to deduce the type of the param and result of F.

Final note: Binary search only searches a range! So you must decide on this range when calling std::lower_bound. It cannot find 'the first value x with F(x)>=y' for any x but only for any x in a given range.