C での効率的な二分探索アルゴリズムの検索

プログラマーは、対数時間計算量の利点を提供する効率的な二分探索アルゴリズムの実装を求めることがよくあります。 。一般的な要件の 1 つは、アルゴリズムが検索結果の存在を示す単純なブール値ではなく、検索結果を指す反復子を返すことです。

C 標準ライブラリでは ヘッダーで std::binary_search が提供されていますが、それは単にブール値を返します。質問者が指摘したように、バイナリ検索の速度が望まれ、データが並べ替えられることがわかっている状況では、これはイライラする可能性があります。

幸いなことに、必要な機能を提供する利用可能な代替実装があります。一般的なオプションの 1 つは、std:: lower_bound、std::upper_bound、または std::equal_range 関数を利用するカスタム アルゴリズムを使用することです。このような実装の簡略版は次のとおりです:

template
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val 
代わりに、要素の順序を保証し、目的の項目への反復子を返す find メソッドを提供する std::set を使用することもできます。ただし、特に同じ要素の複数のインスタンスを保存する必要がある場合、要件がセットの使用と互換性があるかどうかを考慮することが重要です。