検索結果に反復子を返す効率的な二分検索アルゴリズムを C で実装できますか?

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

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

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

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

<code class="cpp">template<class Iter, class T>
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 < *i)) {
        return i;
    }

    // Otherwise, return the end iterator
    else {
        return end;
    }
}</code>

あるいは、要素の順序を保証し、目的の項目にイテレータを返す find メソッドを提供する std::set を使用することもできます。ただし、特に同じ要素の複数のインスタンスを保存する必要がある場合、要件がセットの使用と互換性があるかどうかを考慮することが重要です。

以上が検索結果に反復子を返す効率的な二分検索アルゴリズムを C で実装できますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。