二进制搜索数学函数

Question

我有一个递增的数学函数，例如 y = x + 5*x^3 + x^7 + 11*ln x，我想找到第一个（正）x 使得 y(x) >= 1478。我可以使用stl中的二进制搜索算法来解决这个问题吗？

Answer 1

问题是，STL 算法（std::lower_bound 可能是您的选择）适用于集合。或者更具体地说：关于集合的迭代器。将它们用于您的问题的一种方法是使用适配器：您编写一个 'iterator'，它只是 returns 取消引用时的函数值。

因为您需要满足 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的时候一定要决定这个范围。它无法为 any x 找到 'the first value x with F(x)>=y'，但只能为给定范围内的任何 x 找到 'the first value x with F(x)>=y'。

二进制搜索数学函数

Binary search for math function

c++

stl

binary-search

numerical-methods