binary_search

[機能]

　　ソート済みの系列に対して，指定した範囲で，二分探索法によって指定した要素を探します．2 引数の比較関数を指定することも可能です（下の表現，sort 参照）．

[形式]

#include <algorithm>

template <class ForwardIterator, class T>
    bool binary_search(ForwardIterator first, ForwardIterator last,
                       const T& value);
template <class ForwardIterator, class T, class Compare>
    bool binary_search(ForwardIterator first, ForwardIterator last,
                       const T& value, Compare comp);		

[使用例]

1. binary_search， lower_bound， upper_bound，equal_range の使用方法です．

   #include <stdio.h>
   #include <iostream>
   #include <vector>
   #include <algorithm>
   
   using namespace std;
   
   int main()
   {
   					// 初期設定
   	printf("初期状態 v1 :");
   	vector<int> v1 {21, 67, 93, 73, 88, 73, 84, 53, 44, 43, 73, 72};
   	for (auto x : v1)
   		printf("  %d", x);
   	printf("\n");
   					// 小さい順にソート
   	printf("sort 後 v1 :");
   	sort(v1.begin(), v1.end());
   	for (auto x : v1)
   		printf("  %d", x);
   	printf("\n");
   					// 73 以上の最初の要素
   	printf("73 以上の最初の要素\n");
   	vector<int>::iterator it = lower_bound(v1.begin(), v1.end(), 73);
   	if (it != v1.end())
   		printf("  %d が見つかりました\n", *it);
   					// 73 より大きい最初の要素
   	printf("73 より大きい最初の要素\n");
   	it = upper_bound(v1.begin(), v1.end(), 73);
   	if (it != v1.end())
   		printf("  %d が見つかりました\n", *it);
   					// 73 以上，かつ，73 より大きい要素の位置
   	printf("73 以上，かつ，73 より大きい要素の位置\n");
   	pair <vector<int>::iterator, vector<int>::iterator> p;
   	p = equal_range(v1.begin(), v1.end(), 73);
   	printf("  73 以上の要素: %d， 73 より大きい要素: %d\n", *(p.first), *(p.second));
   					// 73 と等しい要素を探す
   	printf("73 と等しい要素を探す\n");
   	bool b = binary_search(v1.begin(), v1.end(), 73);
   	cout << boolalpha << "  result : " << b << endl;
   
   	return 0;
   }
   			

   （出力）

   初期状態 v1 :  21  67  93  73  88  73  84  53  44  43  73  72
   sort 後 v1 :  21  43  44  53  67  72  73  73  73  84  88  93
   73 以上の最初の要素
     73 が見つかりました
   73 より大きい最初の要素
     84 が見つかりました
   73 以上，かつ，73 より大きい要素の位置
     73 以上の要素: 73， 73 より大きい要素: 84
   73 と等しい要素を探す
     result : true
   			

[参照]

lower_bound， upper_bound， equal_range， sort