P4780 在数组中找数（基础）

解题思路

第一步，弄清楚题目要干什么。 题目先给出 N 个整数，就像一本只有数字的“字典”，然后有 M 次询问，每次问一个数 d 在这本“字典”里出现过没有。出现过输出 Yes，没出现过输出 No。

第二步，先想一个最笨的办法。 每次询问都把 N 个数从头到尾扫一遍，遇到相等的数就说明找到了。这个方法虽然简单，但如果 N 和 M 都很大，最坏要做 M 乘 N 次比较，非常慢，就像查一本没有目录的字典，每次都要翻完整本书，太浪费时间了。

第三步，想到“先排序，再二分查找”。 我们先把 N 个数从小到大排好序，这样数组就有了大小顺序。有了顺序，就能用二分查找快速判断一个数在不在数组里。

第四步，理解二分查找。 二分查找就像猜数字游戏：对方心里想一个 1 到 100 之间的数，你猜 50，对方说“大了”，你就知道答案在 1 到 49 之间，再猜 25……每猜一次，可能的范围就缩小一半。查找也一样：每次看当前范围正中间的数 nums[mid]，如果它正好等于 d，就找到了；如果它比 d 小，说明 d 一定在右半边，把左边界 left 挪到 mid+1；如果它比 d 大，说明 d 在左半边，把右边界 right 挪到 mid-1。

第五步，处理找不到的情况。 如果范围不断缩小，最后 left 已经大于 right，说明整个数组都找遍了也没有 d，此时输出 No。

第六步，举一个例子。 数组是 1 2 3，要查 1。第一次看中间位置 nums[1]=2，比 1 大，只看左半边；再看 nums[0]=1，正好相等，输出 Yes。要查 4：范围越缩越小，最后 left 大于 right，输出 No。

参考代码

// 在数组中找数：先把 N 个整数排序，再对每个询问用二分查找判断该数是否出现过
#include <iostream>
#include <algorithm>
using namespace std;

int nums[2000005];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    // 先从小到大排序，之后才能用二分查找
    sort(nums, nums + n);
    for (int query = 0; query < m; query++) {
        int d;
        scanf("%d", &d);
        // 在有序数组 nums 中二分查找 d 是否存在
        int left = 0, right = n - 1;
        bool found = false;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == d) {
                found = true;
                break;
            } else if (nums[mid] < d) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (found) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

复杂度分析

排序需要 O(N log N) 的时间；每次询问二分查找只需要比较 O(log N) 个数，M 次询问一共 O(M log N)。所以总时间复杂度是 O(N log N + M log N)，即使 N、M 都达到 10 万也很快。空间上只需要存 N 个数的数组，是 O(N)。