我在哪里可以得到一个“有用的”C ++二进制searchalgorithm?

我需要一个与C ++ STL容器兼容的二进制searchalgorithm,就像标准库的<algorithm>标题中的std::binary_search ,但是我需要它返回指向结果的迭代器,而不是一个简单的布尔值来告诉我如果元素存在。

(在旁注中,当他们为binary_search定义API时,标准委员会在想什么?)

我主要关心的是,我需要二进制search的速度,所以虽然我可以用其他algorithmfind数据,但是我想利用这个事实:我的数据被sorting以获得二进制的好处search,而不是一个线性search。

到目前为止,如果数据丢失, lower_boundupper_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_boundstd::upper_boundstd::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; }