ホームページ > バックエンド開発 > C++ > C の二分探索で要素インデックスを見つけるにはどうすればよいですか?

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

Mary-Kate Olsen
リリース: 2024-10-24 04:32:31
オリジナル
917 人が閲覧しました

How to Find Element Index with Binary Search in 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 サイトの他の関連記事を参照してください。

ソース:php
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート