イテレータを返す二分探索アルゴリズムを C で実装するにはどうすればよいですか?

C で反復子を返すバイナリ検索アルゴリズム

C では、 std::binary_search アルゴリズムが便利な方法を提供しますソートされたコンテナーに対して二分検索を実行します。ただし、要素が存在するかどうかを示すブール値のみが返されるため、一部のアプリケーションでは十分ではない可能性があります。

反復子を返すアルゴリズムの要件

必要性が生じます。ブール値ではなく結果を指す反復子を返す二分探索アルゴリズム。これにより、開発者は、見つかった実際の要素にアクセスしたり、コンテナ内に要素が存在しないかどうかを判断したりできます。

カスタム二分探索アルゴリズムの実装

そのような関数は存在しないため、標準ライブラリで利用可能ですが、std:: lower_bound、std::upper_bound、または std::equal_range などの他の STL 関数を使用してカスタム実装を作成できます。 .

サンプル実装

ここでは、std:: lower_bound:

<code class="cpp">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 &amp;&amp; !(val < *i))
        return i; // found
    else
        return end; // not found
}</code>

あるいは、std::set を使用する

もう 1 つのオプションは、並べ替えられた要素を維持し、指定された項目にイテレータを返すメソッド find(T key) を提供する std::set を使用することです。 。ただし、コンテナ内で同じ要素の複数のインスタンスが必要な場合、このアプローチは適切ではない可能性があります。

以上がイテレータを返す二分探索アルゴリズムを C で実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。