ZOJ 2029 The Intervals (二分查找)

ZOJ 2029 The Intervals

给出数组a，求的最小的一个[ a[i], a[j] )使得b[m]在这个区间内，简单的方法就是排序，然后查找范围。为了练习二分，我学习了lower_bound和upper_bound，哈哈stl好强大，以后做题时不能因为不会用二分而超时了。lower_bound(a.begin(),b.end(),x)返回一个迭代器，使得这个位置的元素>=x,用upper_bound则表示>x

#include<iostream>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstdio>
#define M 30
using namespace std;

int main(void)
{
    int n,m,x;
    while( cin >> n >> m )
    {
        vector<int> a;
        for( int i = 0; i < n; i++ ){
            cin >> x;
            a.push_back(x);
        }
        sort( a.begin() ,a.end() );
        while( m-- )
        {
            cin >> x;
            vector<int>::iterator start,end;
            start = lower_bound(a.begin(),a.end(),x);
            end   = upper_bound(a.begin(),a.end(),x);
            if( end == a.end() )
                cout << "no such interval" << endl;
            else if( start == a.begin() && *start != x )
                cout << "no such interval" << endl;
            else{
                if( *start != x ) start--;
                cout << '[' << *start << ',' << *end << ')' << endl;
            }
        }
        cout << endl;
    }
    return 0;
}