P2249 【深基13.例1】查找 二分

1. 这题的数据量比较大，如果直接暴力，时间复杂度O(nm)，会超时；题目上说了，给出的序列是有序的，，所哟我们要直接想到二分查找，复杂度O(nlogm)，那么就可以A了这个题；
2. 由于此题的输入的数据量比较大，题目也说了用cin慢，容易超时，但有的题目没提醒，所以我们要记住当输入的数据量比较大的时候，要考虑scanf；
3. c++有二分的封装好的方法，我这里手写了一个find方法，查找形参t这个值，然后返回值为所查找元素的索引。（数组索引从1开始的）l 表示所查找区间的左边元素的索引，r 表示右边那个元素的索引，用一个循环，只要l<=r，那么都在查找区间内，然后分析可能会出现的三种情况，比较易懂，见注释。

#include "bits/stdc++.h"

using namespace std;

int a[1000010];
int n, m;

int find(int t) {
    int res = -1;
    int l = 1, r = n, mid;
    while (l <= r) {
        //mid=(l+r)/2;
        mid = l + (r - l) / 2;//可以优化，避免有的题l+r直接爆
        if (a[mid] == t) {//找到了，记录一下，向左再找(因为找第一个出现的)
            res = mid;
            r = mid - 1;
        } else if (a[mid] > t) {//大了，向左找
            r = mid - 1;
        } else {//小了，向右找
            l = mid + 1;
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    while (m--) {
        int t;
        scanf("%d", &t);
        cout << find(t) << " ";
    }
    return 0;
}