P2249 有序序列中查找元素题解

题目传送门

#include 

using namespace std;
int n, m, k;

const int N = 1e6 + 10;
int a[N];

bool check(int mid) {
    return a[mid] >= k;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //排序，而且是升序，但本题输出的数据就规定是不降序列，所以，这句话可以没有
    sort(a + 1, a + n + 1);

    //进行 m 次询问
    while (m--) {
        cin >> k;
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid; //因为找左手边第一个出现的数字,所以r=mid,这是是向左逼近
            else l = mid + 1;
        }
        //如果发现这个位置不是我们要找的值，说明没有结果存在于数组中
        if (a[l] != k)printf("%d ", -1);
        else printf("%d ", l);
    }
    return 0;
}