二分查找

一句话算法

二分查找是在“左边都不满足、右边都满足”的空间里，每次丢掉一半，找到分界点。

问题模型

给定一个有序序列：

a1 <= a2 <= ... <= an

有 $m$ 次询问。每次给定一个数 $x$，要求找到第一个满足：

的位置 i。如果不存在，输出 not found。

这个问题也就是手写 lower_bound。

核心直觉

对固定的 $x$，每个位置只有两种状态：

a[i] < x      false
a[i] >= x     true

因为原数组有序，所以这些状态一定长成：

false false false true true true

答案就是第一个 true 的位置。

二分查找每次检查中点 mid：

• 如果 a[mid] >= x，说明答案在左半边或就是 mid。
• 如果 a[mid] < x，说明 mid 和它左边都不可能是答案。

算法步骤

1. 设置查找区间 [l, r]。
2. 让 r = n + 1 作为哨兵位置，表示“没有找到”。
3. 当 l < r：
   • 取 mid = l + (r-l)/2。
   • 若 check(mid) 为真，令 r = mid。
   • 否则令 l = mid + 1。
4. 循环结束时 l == r，这个位置就是第一个满足条件的位置。

`n+1` 不是真实元素位置。它的作用是保证“答案一定存在”：如果真实数组里没有满足条件的位置，就返回这个虚拟位置。

算法证明

关键不变量： 每次循环开始时，答案一定在当前闭区间 [l,r] 内。

1. 初始时，[1,n+1] 包含所有真实位置和哨兵位置，所以答案在区间内。
2. 若 check(mid) 为真，第一个真位置不可能在 mid 右侧的必要部分之外，保留 [l,mid] 不丢答案。
3. 若 check(mid) 为假，由单调性可知 mid 以及左侧都为假，答案只能在 [mid+1,r]。
4. 每轮区间长度都会变小，最终只剩一个位置。

剩下的唯一位置既没有被排除，又必须包含答案，所以它就是第一个满足条件的位置。

复杂度分析

每次询问把区间长度减半。

• 单次询问时间复杂度：$O(\log n)$。
• $m$ 次询问总时间复杂度：$O(m\log n)$。
• 空间复杂度：$O(1)$，不计输入数组。

作为对照，暴力线性扫描单次询问是 $O(n)$，总复杂度是 $O(nm)$。

代码实现

暴力对照

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

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

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    while (m--) {
        int x;
        cin >> x;

        int pos = n + 1;
        for (int i = 1; i <= n; ++i) {
            if (a[i] >= x) {
                pos = i;
                break;
            }
        }

        if (pos == n + 1) cout << "not found\n";
        else cout << a[pos] << ' ' << pos << '\n';
    }

    return 0;
}
    

二分模板

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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

// 在 [l, r] 中查找第一个满足 check(pos) 的位置。
// 要求 check 单调：false false ... false true true ... true。
// 调用时要保证 r 是一个真实或虚拟的可行位置。
template <typename Check>
int first_true(int l, int r, Check check) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

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

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 哨兵位置 n+1：表示不存在 >= x 的元素。
    a[n + 1] = INT_MAX;

    while (m--) {
        int x;
        cin >> x;

        int pos = first_true(1, n + 1, [&](int i) {
            return a[i] >= x;
        });

        if (pos == n + 1) cout << "not found\n";
        else cout << a[pos] << ' ' << pos << '\n';
    }

    return 0;
}
    

测试用例

输入：

5 4
1 2 5 9 100
2
3
20
200

输出：

2 2
5 3
100 5
not found

应用分类详解

二分查找的本质是在具有单调性的空间中快速定位分界点。

一、有序序列边界

典型模式： 数组已经有序，需要找某个值的位置、前驱后继或出现次数。 识别信号： 题面出现“有序序列”“第一个大于等于”“最后一个小于等于”。 核心建模： 把每个位置转成 check(pos)，找到真假分界点。

二、二分答案

典型模式： 直接求最优值很难，但给定一个答案可以检查是否可行。 识别信号： 题面问“最大化最小值”“最小化最大值”“最少需要多少”。 核心建模： 让 check(ans) 表示答案是否可行，在答案范围上二分。

三、特殊结构查找

典型模式： 整体不完全有序，但局部性质能判断答案方向。 识别信号： 旋转数组、山脉数组、峰值、单峰函数。 核心建模： 用局部比较构造单调判断。

四、数值解

典型模式： 在实数或整数范围内求满足精度的解。 识别信号： 题面要求“误差不超过”“方程近似根”“平方根/三次方根”。 核心建模： 在连续区间上二分，直到区间长度满足精度。

五、其他算法的加速组件

典型模式： 主算法维护一个单调数组或单调结构，需要快速定位插入/查询位置。 识别信号： 出现 lower_bound、排名、离散化、LIS 贪心数组。 核心建模： 二分只是子过程，负责把线性查找降到对数。

经典例题

1. luogu-P2249 标准 lower_bound 练习题，适合验证边界处理。

2. luogu-P1182 典型“最小化最大值”二分答案模型。

3. luogu-P2678 典型“最大化最小值”二分答案模型。

参考

• 本目录旧材料：problem.md、summary.md、proof.md
• C++ 标准库：lower_bound