文字教学

这道题是二分查找左边界的经典应用。因为序列是单调不减的，我们可以用二分法快速定位目标数第一次出现的位置：

1. 初始化左指针 l=0，右指针 r=n-1（数组下标从0开始）。
2. 当 l < r 时，取中间位置 mid：
   • 若 a[mid] >= q，说明目标在左半部分，令 r=mid；
   • 否则目标在右半部分，令 l=mid+1。
3. 循环结束后检查 a[l] 是否等于 q，若是则返回 l+1（题目编号从1开始），否则返回 -1。

代码

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    while (m--) {
        int q;
        cin >> q;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (a[mid] >= q) r = mid;
            else l = mid + 1;
        }
        if (a[l] == q) cout << l + 1 << " ";
        else cout << -1 << " ";
    }
    cout << endl;
    return 0;
}