c++ - Where can I get a "useful" C++ binary search algorithm?

Question

I need a binary search algorithm that is compatible with the C++ STL containers, something like std::binary_search in the standard library's <algorithm> header, but I need it to return the iterator that points at the result, not a simple boolean telling me if the element exists.

(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search?!)

My main concern here is that I need the speed of a binary search, so although I can find the data with other algorithms, as mentioned below, I want to take advantage of the fact that my data is sorted to get the benefits of a binary search, not a linear search.

so far lower_bound and upper_bound fail if the datum is missing:

//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 belong to the std namespace as long as its compatible with containers. Like, say, boost::binary_search.

Answer 1

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
}

別の解決策はstd::set、要素の順序を保証iterator find(T key)し、指定されたアイテムに反復子を返すメソッドを提供する a を使用することです。ただし、要件がセットの使用と互換性がない場合があります (たとえば、同じ要素を複数回保存する必要がある場合)。

Answer 2

をご覧くださいstd::equal_range。すべての結果の範囲に反復子のペアを返します。

Answer 3

それらのセットがあります：

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

検索する：

• 下界
• 上界
• equal_range
• binary_search

別のメモで：

彼らはおそらく、コンテナを検索すると複数の結果が得られると考えていたのでしょう。しかし、存在をテストする必要があるという奇妙な機会には、最適化されたバージョンもいいでしょう.

Answer 4

std::lower_bound が好みに対して低レベルすぎる場合は、boost::container::flat_multisetを確認することをお勧めします。これは、バイナリ検索を使用して並べ替えられたベクトルとして実装された std::multiset のドロップイン置換です。

Answer 5

この関数qBinaryFindを確認してください:

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

範囲 [begin, end) のバイナリ検索を実行し、値の出現位置を返します。value が出現しない場合は、end を返します。

範囲 [begin, end) の項目は昇順で並べ替える必要があります。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>の一部であるヘッダーに含まれています。

Answer 6

std::lower_bound() :)