C++ STL 二分探索

Harshit Jindal 2023年10月12日

C++ C++ Algorithm

C++ STL binary_search() 概要
C++ 二分探索プログラム

注意

二分探索について詳しく理解したい場合は、二分探索アルゴリズムの記事を参照してください。

C++ では、すぐに使える関数 binary_search() が用意されているので、自分で関数を実装する必要はありません。この関数は非常に使いやすく効率的に実装されており、エラーが発生することもありません。

C++ STL `binary_search()` 概要

構文

DEFAULT
    : template <class ForwardIterator, class T>
      bool
      binary_search(ForwardIterator first, ForwardIterator last, const T& val);

CUSTOM COMPARISON FUNCTION
    : template <class ForwardIterator, class T, class Compare>
      bool
      binary_search(ForwardIterator first, ForwardIterator last, const T& val,
                    Compare comp);

ここで、T は以下のいずれかです。int、float、short、long、byte、char、double, さらにはユーザ定義の Object も同様です。

これは、二分探索アルゴリズムを用いて [first, last) 内の要素が対象の要素 X にマッチするかどうかをチェックします。デフォルトでは、要素の比較に less-than 演算子を用いますが、上述の 2 番目のテンプレートで説明したように、独自のカスタム comp を指定することもできます。

パラメータ


`first`	与えられた配列範囲の最初の要素を指す前方のイテレータ。
`last`	与えられた配列範囲の最後の要素を指す前方のイテレータ。
`comp`	2つの前方イテレータを引数として受け取り、2つの引数が正しい順序で存在する場合は `true` を返すユーザー定義の 2 値述語関数です。この関数は引数を変更せず、要素の順序を厳密な弱い順序に従う。
`val`	指定された配列の範囲内で検索対象の要素を指定します。

戻り値

対象の要素が見つかった場合は true を返し、そうでない場合は false を返します。

C++ 二分探索プログラム

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = {1, 2, 3, 4, 5, 6};

  if (binary_search(v.begin(), v.end(), 5)) {
    cout << "Element found" << endl;
  } else {
    cout << "Element not found" << endl;
  }

  return 0;
}

著者： Harshit Jindal

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

C++ STL binary_search() 概要

構文

パラメータ

戻り値

C++ 二分探索プログラム

関連記事 - C++ Algorithm

C++ STL `binary_search()` 概要