HOWTO · C++
C++ STL 二分探索
このチュートリアルでは、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;
}
