紫书刷题进行中，题解系列【GitHub|CSDN】

例题5-1 UVA10474 Where is the Marble（17行AC代码）

题目大意

给定N个具有标号的小球，升序排列后，给定M个查询，若存在，输出位置（从1开始）；否则输出提示信息

算法设计

用一维数组存储N个小球，使用sort升序排列，使用lowerbound找到第一个大于等于x的值，因此找到的值有可能为最后一个元素的后面或大于x的值，因此要多一步判断，如下所示

p = lower_bound(a, a+n, q); // 找到>=q的第一个数
if (p - a != n && *p == q) printf("%d found at %d\n", q, p-a+1); // 存在且为q
else printf("%d not found\n", q); 

若不想用该函数，也可转换为n个成绩（含重复）进行排名处理问题，排序后一次遍历计数即可

AC代码（C++11，sort，lowerbound/成绩排名（含同分））

#include<bits/stdc++.h>
using namespace std;
int n, m, a[100010], q, *p, num=0;
int main() {
    while (cin >>n >>m && (n != 0 && m != 0)) {
        for (int i = 0; i < n; i ++) cin >>a[i];
        sort(a, a+n); // 升序排列
        printf("CASE# %d:\n", ++num);
        while (m --) {
            cin >>q;
            p = lower_bound(a, a+n, q); // 找到>=q的第一个数
            if (p - a != n && *p == q) printf("%d found at %d\n", q, p-a+1); // 存在且为q
            else printf("%d not found\n", q); 
        }
    }
    return 0;
}