练83.5 二分查找2

解题思路

用upper_bound找首个>key位置，再回退一格，若等于key则是最后出现位置，下标+1输出，否则-1。

正确性说明

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

易错点

回退前检查是否在begin，避免越界。

复杂度

时间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 = upper_bound(a.begin(), a.end(), key);
        int ans = -1;
        if (it != a.begin()) {
            it--;
            if (*it == key)
                ans = it - a.begin() + 1;
        }
        if (i)
            cout << " ";
        cout << ans;
    }
    cout << "\n";
    return 0;
}