[解決済み] 役に立つ」C++のバイナリ検索アルゴリズムはどこで手に入りますか？

質問

C++のSTLコンテナと互換性のあるバイナリ検索アルゴリズムが必要で、以下のようなものです。 std::binary_search のような、標準ライブラリの <algorithm> ヘッダがありますが、要素が存在するかどうかを示す単純なブール値ではなく、結果を指し示すイテレータを返す必要があります。

(余談ですが、binary_searchのAPIを定義したとき、標準委員会は一体何を考えていたのでしょうか?!)

ここでの私の主な関心事は、バイナリ検索の速度が必要なことです。したがって、後述のように他のアルゴリズムでデータを見つけることができますが、線形検索ではなくバイナリ検索の利点を得るために、私のデータがソートされているという事実を利用したいと思います。

ここまで lower_bound と upper_bound は、datumが欠落している場合は失敗します。

//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 .

どのように解決するのですか？

このような関数はありませんが、簡単なものは 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) を提供し、与えられた項目へのイテレータを返します。しかし、あなたの要件はセットの使用と互換性がないかもしれません（例えば、同じ要素を複数回保存する必要がある場合など）。