我在哪里可以得到一个“有用的”C ++二进制searchalgorithm？
我需要一个与C ++ STL容器兼容的二进制searchalgorithm，就像标准库的<algorithm>标题中的std::binary_search ，但是我需要它返回指向结果的迭代器，而不是一个简单的布尔值来告诉我如果元素存在。
（在旁注中，当他们为binary_search定义API时，标准委员会在想什么？）
我主要关心的是，我需要二进制search的速度，所以虽然我可以用其他algorithmfind数据，但是我想利用这个事实：我的数据被sorting以获得二进制的好处search，而不是一个线性search。
到目前为止，如果数据丢失， 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命名空间的algorithm。 就像boost::binary_search 。
没有这样的函数，但可以使用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 }
另一个解决scheme是使用std::set ，它保证了元素的sorting，并提供了一个iterator find(T key) ，它将一个迭代器返回给给定的项目。 但是，您的需求可能与使用集合不兼容（例如，如果您需要多次存储相同的元素）。
你应该看看std::equal_range 。 它将返回一对迭代器到所有结果的范围。
有一组：
http://www.sgi.com/tech/stl/table_of_contents.html
search：
- LOWER_BOUND
- UPPER_BOUND
- equal_range
- binary_search
在另一个注意：
他们可能认为search容器可能会取得不止一个结果。 但在奇怪的场合，你只需要testing存在的优化版本也会很好。
如果std :: lower_bound对你来说太低级，你可能想要检查boost :: container :: flat_multiset 。 它是std :: multiset的替代品，它使用二分search作为sorting向量实现。
std :: lower_bound（）:)
检查这个函数， qBinaryFind ：
RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )执行范围[开始，结束]的二进制search并返回值的出现位置。 如果没有价值的事件，则返回结束。
范围[开始，结束]中的项目必须按升序sorting; 看qSort（）。
如果有多次相同的值，则可以返回其中的任何一个。 如果您需要更好的控制，请使用qLowerBound（）或qUpperBound（）。
例：
QVector<int> vect; vect << 3 << 3 << 6 << 6 << 6 << 8; QVector<int>::iterator i = qBinaryFind(vect.begin(), vect.end(), 6); // i == vect.begin() + 2 (or 3 or 4)
该函数包含在Qt库的一部分<QtAlgorithms>头部。
返回范围内的位置的解决scheme可能是这样的，仅使用迭代器上的操作（即使迭代器不算术，它也应该工作）：
template <class InputIterator, typename T> size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val) { const InputIterator beginIt = first; InputIterator element = first; size_t p = 0; size_t shift = 0; while((first <= last)) { p = std::distance(beginIt, first); size_t u = std::distance(beginIt, last); size_t m = (p+u)/2; std::advance(element, m - shift); shift = m; if(*element == val) return m; // value found at position m if(val > *element) first = element++; else last = element--; } // if you are here the value is not present in the list, // however if there are the value should be at position u // (here p==u) return p; }
