我需要一个与 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
。