ソートされた C コンテナーにイテレーターベースの二分探索アルゴリズムを実装するにはどうすればよいですか?

C コンテナのイテレータリターンを使用したバイナリ検索アルゴリズム

STL の std::binary_search アルゴリズムは、並べ替えられたコンテナ内の要素の存在を効率的に識別します。コンテナですが、ブール値のみを返します。要素の正確な位置が重要なシナリオでは、反復子ベースの検索アルゴリズムが必要になる場合があります。

このニーズに対処するには、次のカスタム バイナリ検索アルゴリズムを使用できます:

<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:: lower_bound を利用して、コンテナー内の値の挿入ポイントを見つけます (値が挿入される場合)。値が存在する場合はイテレータが返されます。それ以外の場合は、終了イテレータが返されます。このアプローチにより、速度と精度の両方が保証されます

また、指定された項目を指すイテレータを直接返すイテレータ find(T key) 関数を提供する std::set の使用を検討することもできます。ただし、これは重複した要素が必要な場合には適さない可能性があります。

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