2

鉴于：

typedef .../*some type*/ SomeValue;

SomeValue someFunction(int arg){
     return /*some calculation involving arg that produces SomeValue*/
}

int firstCandidate = 0, lastCandidate = 101;
SomeValue desiredValue = SomeValue();

我想找到使用二进制搜索（ ）int产生desiredValue（当传递给）的参数。 ,是要赋予 的参数。对于搜索，候选人应调用并将结果与​​ . 因为是真的。someFunctionstd::lower_boundfirstCandidatelastCandidatesomeFunctionstd::lower_boundsomeFunction(currentArgument)desiredValueSomeValue someFunction(x) < someFunction(x + 1)

即它应该产生与此相同的结果：

int findArgLowerbound(int first, int last, SomeValue refVal){
     for (int i = first; i < last; i++){
          if (someFunction(i) >= refVal)
               return i;
     }
     return last;
}

仅使用标准函数+二分查找算法。

在有和没有提升的情况下 ，我怎样才能轻松地做到这一点（无需编写我自己的二进制搜索函数）？不是迭代器，在这种情况下int我还没有弄清楚如何制作。boost::make_transform_iterator

限制：

  1. c++03标准。
  2. boost 没问题，但我真的更喜欢没有它的解决方案。

- 编辑 -

我想知道如何使用内置函数或已经可用的函数（std::lower_bound 和类似函数）来做我想做的事。我可以编写专门的二进制搜索函数，但我认为这不是“正确”的方法。

4

2 回答 2

0

这就是我的处理方式：

假装你有一个vector<SomeValue>排序好的。该向量可使用 访问someFunction(index)。

现在，看看这个。那是二进制搜索的伪代码。继续上面的思考过程，替换A[imid]为someFunction(imid)并制作key一个SomeValue. 确保SomeValue有一个有效的operator <（或你用来代替它的比较器函数）。

这当然只适用someFunction(x) < someFunction(x + 1)于所有人x。你说这是真的，所以它应该是好的。

我建议使用迭代方法，因为它们具有相同的渐近运行时间，并且迭代版本更容易报告未找到的密钥，并且往往使用更少的内存。

编辑我不知道使用这些std东西的简单方法。正如您上面提到的，int它不能用作迭代器，并且您可能想要使用的所有函数都采用迭代器。但从技术上讲，这些函数中的迭代器是模板类型，因此您可以编写自己的IntIter类或类似的东西。使用std::lower_bound将需要operator *(),operator ++()和operator +(int). operator *()可能会返回someFunction(n)，与 .n关联的 int 值在哪里IntIter。但是，我不知道这是否真的有效，并且可能需要更多时间和编码。如果您想采用这种方法，您应该查看std::lower_boundand std::advance（调用 in ）。lower_bound

于 2013-08-02T15:51:24.410 回答
0

想通了（享受宏+模板巫毒）。

#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/irange.hpp>
#include <boost/typeof/std/utility.hpp>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <sstream>

std::string convertArgs(int arg1, int arg2){
    std::stringstream out;
    out << std::setfill('0') << std::setw(8) << arg1*arg2;
    return out.str();
}

void boostTest(){
    int first = 0, last = 42;
    int arg = 2;
    std::string desiredValue = "00000007";
    BOOST_AUTO(range, boost::irange(first, last));
    BOOST_AUTO(start, boost::make_transform_iterator(range.begin(), std::bind1st(std::ptr_fun(convertArgs), arg)));
    BOOST_AUTO(end, boost::make_transform_iterator(range.end(), std::bind1st(std::ptr_fun(convertArgs), arg)));
    BOOST_AUTO(found, std::lower_bound(start, end, desiredValue));
    if (found != end){
        std::cout << "str:" << *found << "\nval: " << *(found.base());
    }
}

int main(int argc, char** argv){
    boostTest();
    return 0;
}

除非您生成具有所有可能值的数组，自己制作包装器迭代器或类似的东西，否则很可能在没有 boost 的情况下无法轻松完成。

于 2013-08-02T16:31:39.370 回答