binary_search

文法:

    #include <algorithm>
    bool binary_search( forward_iterator start, forward_iterator end, const T& val );
    bool binary_search( forward_iterator start, forward_iterator end, const T& val, Comp f );

binary_search()関数はstartとendの間のvalを検索します。 検索されるstartとendの間の要素は<オペレータで定義されるような昇順にする必要があります。 検索される要素が整列されていなければ、バイナリサーチは動作しないことに注意してください。

各々の値は<オペレータのみ定義されている必要があります。 a、bの2つの値は、!(a<b) && !(b<a)が真の場合、等しいと見なされます。

もしvalが見つかった場合、binary_search()はtrueを返し、そうでない場合はfalseを返します。 もし関数fが指定された場合、fは<オペレータに代わって要素を比較するために使われます。

引数

todo

返値

todo

例

以下のコードは、整数0-9がある整数配列の中に含まれるかどうか調べるためにbinary_search()を使用しています (nums[]は昇順でソートされている必要があります):

   int nums[] = { -242, -1, 0, 5, 8, 9, 11 };
   int start = 0;
   int end = 7;
 
   for( int i = 0; i < 10; i++ ) {
     if( binary_search( nums+start, nums+end, i ) ) {
       cout << "nums[] contains " << i << endl;
     } else {
       cout << "nums[] DOES NOT contain " << i << endl;
     }
   }

実行すると、このコードは以下の出力を表示します:

   nums[] contains 0
   nums[] DOES NOT contain 1
   nums[] DOES NOT contain 2
   nums[] DOES NOT contain 3
   nums[] DOES NOT contain 4
   nums[] contains 5
   nums[] DOES NOT contain 6
   nums[] DOES NOT contain 7
   nums[] contains 8
   nums[] contains 9

計算量

binary_search()は 対数時間で動作します。

関連トピック

equal_range, lower_bound, partial_sort, partial_sort_copy, sort, stable_sort, upper_bound