UVa10474 Where is the Marble ? 有序数组二分找值 lower_bound / upper_bound

题意：

给出n个数，先把各数从小到大排序，然后q次询问xi在数组中的位置，不存在则输出相应信息。

输入样例：

4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0

输出样例：

CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3

//=======================================

数组从小到大有序。

lower_bound ：查找“大于或者等于x”的第一个位置。

upper_bound：查找“大于x”的第一个位置。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 5;
int a[maxn];

int main()
{
    int cas = 1, x;
    int n, q;
    while(~scanf("%d%d", &n, &q)) {
        if(n==0&&q==0) break;
        for(int i=1; i<=n; ++i) {
            scanf("%d", &a[i]);
        }
        sort(a+1, a+n+1);
        printf("CASE# %d:\n", cas++);
        while(q--){
            scanf("%d",&x);
            int p = lower_bound(a+1, a+n+1, x) - a;
            if(a[p]==x){ printf("%d found at %d\n", x, p);}
            else printf("%d not found\n", x);
        }
    }
    return 0;
}

UVa10474 Where is the Marble ? 有序数组二分找值 lower_bound / upper_bound

原文：http://blog.csdn.net/yew1eb/article/details/39475863