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

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

(另一方面,当他们为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.

1> Luc Touraill..：

---

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

一个简单的实现可能是

template
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)将迭代器返回给定项的方法.但是,您的要求可能与集合的使用不兼容(例如,如果您需要多次存储相同的元素).

---

不要使用`*i == val`!而是使用`!(val <*i)`.原因是`lower_bound`使用`<`,而不是`==`(即`T`甚至不需要具有相等性).(有关_equality_和_equivalence_之间区别的解释,请参阅Scott Meyers的_Effective STL_.)

---

我不太明白你的评论,因为lower_bound只能用于排序数据.复杂性低于使用find(参见编辑).

---

为了补充Luc的答案,请查看Matt Austern的经典文章[为什么你不应该使用集合,以及你应该使用什么](http://lafstern.org/matt/col1.pdf)(C++报告12:4,2000年4月) )理解为什么带有排序向量的二进制搜索通常比std :: set更好,std :: set是一个基于树的关联容器.

2> Luc Hermitte..：

---

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

3> Martin York..：

---

有一组:

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

搜索:

LOWER_BOUND

UPPER_BOUND

equal_range

binary_search

另请注意:

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

---

正如STL中的许多其他内容一样,binary_search被命名为错误.我讨厌那个.存在的测试与搜索某些东西不同.

---

如前所述,binary_search没有返回迭代器,这就是为什么我在寻找替代方案.

---

如果您想知道要查找的元素的索引，这些二进制搜索功能将无用。我必须为此任务编写自己的递归函数。我希望将template <class T> int bindary_search（const T＆item）添加到下一个C ++版本中。