我需要一个与C STL容器兼容的二进制搜索算法,比如标准库的 <algorithm>
头中的 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
Note: I 'm also fine using an algorithm that doesn' t属于std命名空间,只要它与容器兼容即可 . 比方说, boost::binary_search
.
9 回答
没有这样的功能,但您可以使用std::lower_bound,std::upper_bound或std::equal_range编写一个简单的功能 .
一个简单的实现可能是
另一个解决方案是使用
std::set
,它保证元素的排序,并提供一个方法iterator find(T key)
,它返回给定项的迭代器 . 但是,您的要求可能与集合的使用不兼容(例如,如果您需要多次存储相同的元素) .你应该看一下
std::equal_range
. 它将返回一对迭代器到所有结果的范围 .有一组:
http://www.sgi.com/tech/stl/table_of_contents.html
搜索:
lower_bound
upper_bound
equal_range
binary_search
另请注意:
他们可能认为搜索容器可能会产生不止一个结果 . 但在奇怪的场合,你只需要测试存在,优化版本也会很好 .
如果你喜欢std :: lower_bound太低级别,你可能想检查boost::container::flat_multiset . 它是使用二进制搜索实现为排序向量的std :: multiset的替代品 .
std :: lower_bound():)
检查此功能,qBinaryFind:
QVector <int> :: iterator i =
qBinaryFind(vect.begin(),vect.end(),6);
// i == vect.begin()2(或3或4)
该函数包含在
<QtAlgorithms>
标头中,该标头是Qt库的一部分 .返回范围内的位置的解决方案可能是这样的,只使用迭代器上的操作(即使迭代器不算术也应该工作):
示例:考虑一个数组,A = [1,2,3,4,5,6,7,8,9]假设您要搜索索引3最初,start = 0和end = 9-1 = 8现在,自从开始<=结束;中期= 4; (array [mid]是5)!= 3现在,3位于mid的左边,因为它小于5.因此,我们只搜索数组的左边部分因此,现在start = 0和end = 3; mid = 2.Since array [mid] == 3,因此我们得到了我们要搜索的数字 . 因此,我们返回其等于mid的索引 .
最短的实现,想知道它为什么不包含在标准库中:
从https://en.cppreference.com/w/cpp/algorithm/lower_bound