题解 | 查找

法1：二分法，注意递归调用时把函数值return返回上一层

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

//二分法（折半查找）b是否在数组a中
bool isExist(vector<int>& a, int L, int R, int b) {
    if (L > R)return false;
    int Mid = (L + R) / 2;
    if (b == a[Mid])return true;
    if (b > a[Mid]) {
        //在右半部分找
        return isExist(a, Mid + 1, R, b);
    } else {
        //在左半部分找
        return isExist(a, L, Mid - 1, b);
    }
}
int main() {
    int n, m;
    while (scanf("%d", &n) != EOF) {
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        scanf("%d", &m);
        //二分法前先排好序
        sort(a.begin(), a.end());
        int b;
        for (int i = 0; i < m; i++) {
            scanf("%d", &b);
            if (isExist(a, 0, n - 1, b)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }

    }
    return 0;
}

法2：用map容器中中的成员方法find（）底层实现是红黑树，查找效率和二分法一样；注意和<algorithm>中的find（）是线性查找，底层实现是简单的循环遍历。

#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;

int main() {
    int n, m;
    while (scanf("%d", &n) != EOF) {
        //用集合存数组a和下标
       map<int,int> mapA;
       int a;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a);
            mapA.insert({a,i});
        }
        scanf("%d", &m);
        int b;
        for (int i = 0; i < m; i++) {
            scanf("%d", &b);
            //map中的find（）查找的时间效率和二分法一样
            //若find找到返回迭代器
            if (mapA.find(b)!=mapA.end()){
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }

    }
    return 0;
}