我在哪里可以获得"有用的"C++二进制搜索算法？

Question

我需要一个与C++ STL容器兼容的二进制搜索算法,类似于std::binary_search标准库的<algorithm>头文件,但我需要它返回指向结果的迭代器,而不是一个简单的布尔值告诉我元素是否存在.

(另一方面,当他们为binary_search定义API时,标准委员会在想什么？!)

我主要担心的是我需要二进制搜索的速度,所以尽管我可以用其他算法找到数据,如下所述,我想利用我的数据被排序以获得二进制的好处这一事实搜索,而不是线性搜索.

到目前为止lower_bound,upper_bound如果缺少基准则失败:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

注意:我也可以使用不属于std命名空间的算法,只要它与容器兼容即可.就像说,boost::binary_search.

Answer 1

有没有这样的功能,但你可以用写一个简单的一个std::lower_bound,std::upper_bound或std::equal_range.

一个简单的实现可能是

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

另一种解决方案是使用a std::set,它保证了元素的排序,并提供了一个iterator find(T key)将迭代器返回给定项的方法.但是,您的要求可能与集合的使用不兼容(例如,如果您需要多次存储相同的元素).

Answer 2

你应该看看std::equal_range.它将返回一对迭代器到所有结果的范围.

Answer 3

有一组:

http://www.sgi.com/tech/stl/table_of_contents.html

搜索:

• LOWER_BOUND
• UPPER_BOUND
• equal_range
• binary_search

另请注意:

他们可能认为搜索容器可能会产生不止一个结果.但在奇怪的情况下,你只需要测试存在,优化版本也会很好.