【例73.1】 找球号

解题思路

将球号排序，对每个查询使用binary_search判断是否存在。允许重复编号，无需删除重复也能正确查找。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

m可以为0，空数组查询全部NO。

复杂度

时间O(m log m+n log(m+1))，空间O(m)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<long long> a(m);
    for (auto &x : a)
        cin >> x;
    sort(a.begin(), a.end());
    while (n--) {
        long long k;
        cin >> k;
        cout << (binary_search(a.begin(), a.end(), k) ? "YES" : "NO") << "\n";
    }
    return 0;
}