ホームページ > バックエンド開発 > C++ > イテレータを返す二分探索アルゴリズムを C で実装するにはどうすればよいですか?

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

Linda Hamilton
リリース: 2024-10-24 04:49:02
オリジナル
597 人が閲覧しました

How to Implement a Binary Search Algorithm That Returns an Iterator in C  ?

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

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

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

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

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

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

サンプル実装

ここでは、std:: lower_bound:

1

2

3

4

5

6

7

8

9

10

11

<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 サイトの他の関連記事を参照してください。

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