【模板】二分题解

题目大意

给定一个长度为 n 的不下降（即非严格递增）正整数序列 a_1, a_2, \dots, a_n，以及 q 次询问。
每次询问给出一个正整数 x，求最小的下标 i 使得 a_i > x。
如果不存在这样的 i，输出 -1。

样例解释

序列：1 2 3 4 5

查询 x = 3：第一个大于 3 的数是 4，下标为 4，输出 4。
查询 x = 5：没有大于 5 的数，输出 -1。

思路分析

因为序列是不下降的，所以具有单调性：
对于任意 i < j，有 a_i \le a_j。
因此我们可以使用二分查找在 O(\log n) 时间内回答每个询问。

我们要找的是 第一个满足 a_i > x 的位置，这等价于 C++ 中的 upper_bound 函数。

二分实现细节

我们维护两个指针 l 和 r，初始时：

l = 1（第一个位置）
r = n + 1（一个“哨兵”位置，表示超出数组范围）

循环条件 l < r：

计算中点 mid = (l + r) / 2（下取整）
如果 a[mid] > x，说明答案在 [l, mid] 中，令 r = mid
否则（a[mid] <= x），说明答案在 [mid+1, r] 中，令 l = mid + 1

循环结束后，l 就是第一个大于 x 的位置。
如果 l == n + 1，说明不存在，输出 -1。

代码实现

C++ 代码（使用手写二分）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1); // 1-indexed
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    while (q--) {
        int x;
        cin >> x;
        int l = 1, r = n + 1; // 注意右边界是 n+1
        while (l < r) {
            int mid = (l + r) / 2;
            if (a[mid] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l == n + 1) {
            cout << "-1\n";
        } else {
            cout << l << '\n';
        }
    }
    return 0;
}

C++ 代码（使用 STL）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    while (q--) {
        int x;
        cin >> x;
        int pos = upper_bound(a.begin(), a.end(), x) - a.begin() + 1; // 转成 1-indexed
        if (pos > n) {
            cout << "-1\n";
        } else {
            cout << pos << '\n';
        }
    }
    return 0;
}

复杂度分析

时间复杂度：预处理 O(n)，每次询问 O(\log n)，总复杂度 O(n + q \log n)。
空间复杂度：O(n)。

注意事项

下标问题：题目要求输出最小的下标（从 1 开始），在代码中注意转换。
边界处理：如果所有元素都 \le x，那么最终 l 会停在 n+1，此时输出 -1。
数据类型：题目中序列和询问值都是正整数，用 int 足够（根据数据范围最大 10^9 左右，32 位 int 可存）。
不下降序列：严格递增也是一种特殊情况，算法同样适用。

扩展思考

如果题目要求找第一个大于等于 x 的位置（即 lower_bound），该如何修改？
如果序列不是单调的，还能用二分吗？——不能，二分要求单调性。

本题是二分查找的模板题，熟练掌握二分边界写法非常重要。

【模板】二分 题解