binary_search

[機能]

  ソート済みの系列に対して,指定した範囲で,指定した要素を探します.2 引数の比較関数を指定することも可能です(下の表現).

[形式]
	#include <algorithm>
	#include <functional>

	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 <vector>
    #include <algorithm>
    #include <functional>
    using namespace std;
    
    bool eq_a(int a, int b)
    {
    	return (bool)((a%10 == b%10) ? 1 : 0);
    };
    
    class eq_b : public binary_function<int, int, bool>
    {
    	public:
    		result_type operator() (first_argument_type a, second_argument_type b)
    		{
    			return (result_type)((a%10 == b%10) ? 1 : 0);
    		}
    };
    
    bool less_a(int a, int b)
    {
    	return (bool)((a%10 < b%10) ? 1 : 0);
    };
    
    class less_b : public binary_function<int, int, bool>
    {
    	public:
    		result_type operator() (first_argument_type a, second_argument_type b)
    		{
    			return (result_type)((a%10 < b%10) ? 1 : 0);
    		}
    };
    
    int main()
    {
    	vector<int> v1;
    	vector<int>::iterator it, s;
    	pair <vector<int>::iterator, vector<int>::iterator> p;
    					// 初期設定
    	printf("**初期状態 v1**\n");
    	v1.push_back(52);
    	v1.push_back(21);
    	v1.push_back(67);
    	v1.push_back(93);
    	v1.push_back(88);
    	v1.push_back(84);
    	v1.push_back(53);
    	v1.push_back(44);
    	v1.push_back(43);
    	v1.push_back(72);
    	for (it = v1.begin(); it != v1.end(); it++)
    		printf("  %d", *it);
    	printf("\n");
    					// 小さい順にソート
    	printf("小さい順にソート\n");
    	sort(v1.begin(), v1.end(), less_a);
    							// 以下の方法でも可能
    //	sort(v1.begin(), v1.end(), less_b());
    	for (it = v1.begin(); it != v1.end(); it++)
    		printf("  %d", *it);
    	printf("\n");
    					// 73 以上の最初の要素
    	printf("73 以上の最初の要素\n");
    	s = lower_bound(v1.begin(), v1.end(), 73, less_a);
    							// 以下の方法でも可能
    //	s = lower_bound(v1.begin(), v1.end(), 73, less_b());
    	if (s != v1.end())
    		printf("  %d が見つかりました\n", *s);
    	else
    		printf("  見つかりませんでした\n");
    					// 73 より大きい最初の要素
    	printf("73 より大きい最初の要素\n");
    	s = upper_bound(v1.begin(), v1.end(), 73, less_a);
    							// 以下の方法でも可能
    //	s = upper_bound(v1.begin(), v1.end(), 73, less_b());
    	if (s != v1.end())
    		printf("  %d が見つかりました\n", *s);
    	else
    		printf("  見つかりませんでした\n");
    					// 73 を挿入できる箇所
    	printf("73 を挿入できる箇所\n");
    //	p = equal_range(v1.begin(), v1.end(), 73, less_a);
    							// 以下の方法でも可能
    	p = equal_range(v1.begin(), v1.end(), 73, less_b());
    	printf("  %d から %d の間へ挿入できます\n", *(p.first), *(p.second));
    					// 73 と等しい要素を探す
    	printf("73 と等しい要素を探す\n");
    	bool b = binary_search(v1.begin(), v1.end(), 73, eq_a);
    							// 以下の方法でも可能
    //	bool b = binary_search(v1.begin(), v1.end(), 73, eq_b());
    	if (b)
    		printf("  見つかりました\n");
    	else
    		printf("  見つかりませんでした\n");
    
    	return 0;
    }
    			
    (出力)
    **初期状態 v1**
      52  21  67  93  88  84  53  44  43  72
    小さい順にソート
      21  52  72  93  53  43  84  44  67  88
    73 以上の最初の要素
      93 が見つかりました
    73 より大きい最初の要素
      84 が見つかりました
    73 を挿入できる箇所
      93 から 84 の間へ挿入できます
    73 と等しい要素を探す
      見つかりました
    			
[参照]

findfind_ifsearchlower_boundupper_boundequal_range

菅沼ホーム 本文目次 演習問題解答例 付録目次 索引