【例83.2】二分查找

解题思路

每次查询用lower_bound找首个≥key的位置，若等于key，输出下标+1，否则-1。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

重复值需最小位置；结果一行空格分隔。

复杂度

时间O(n+T log n)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int key;
        cin >> key;
        auto it = lower_bound(a.begin(), a.end(), key);
        int ans = it != a.end() && *it == key ? int(it - a.begin()) + 1 : -1;
        if (i)
            cout << " ";
        cout << ans;
    }
    cout << "\n";
    return 0;
}