C の二分探索で要素インデックスを見つけるにはどうすればよいですか?

C での効率的な二分探索の実装

ソートされたコンテナ内の要素のインデックスまたはイテレータを見つけることは、C の基本的な操作です。ただし、標準ライブラリの std::binary_search アルゴリズムは、要素の位置ではなく、要素の存在を示すブール値のみを返します。

コンテナがソートされている場合を考えてみましょう。効率上の理由からバイナリ検索アルゴリズムが推奨されます。 。このニーズに対応する実装が必要です。

カスタム反復二分探索

1 つのアプローチは、カスタム反復二分探索アルゴリズムを実装することです。以下に実装例を示します。

<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 を使用して、検索された要素を指す反復子を効率的に見つけます。見つかった値が val と一致しない場合は、end() イテレータを返します。

代替ソリューション

別のオプションは、std::set を使用することです。要素の順序付けを行い、指定された項目のイテレータを返す find(T key) メソッドを提供します。ただし、これは重複した要素が必要な場合には適さない可能性があります。

以上がC の二分探索で要素インデックスを見つけるにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。