9 二分查找

GESP C++ 五级：二分查找精讲

核心目标：理解二分查找的折半思想与适用前提，掌握整数二分的两种区间写法和边界处理，理解 lower_bound/upper_bound 的返回值语义与 STL 用法，能分析二分查找的复杂度。
二分查找像查字典——每次翻到中间，根据大小排除一半；前提是数据有序；全闭和半开两种写法，边界“+1”“-1”不能乱；mid 用 left + (right - left) / 2 防溢出。

一、考纲定位

根据 CCF 官方考纲，五级知识点第（6）条明确要求：“掌握二分查找和二分答案算法（也称二分枚举法）的基本原理，能够在有序数组中快速定位目标值。 ”考核目标进一步要求：“熟悉二分法、分治法、贪心算法和递归算法的算法思想，能够根据实际情况选择合适的算法并完成解决相应的问题”。

五级考纲还同时包含“算法复杂度估算方法（含多项式、对数）”，这为理解二分查找的对数级复杂度提供了理论基础。

二分查找在五级考试中的考查分布：

考点	重要程度	典型考法
二分查找基本原理	★★★★★	选择题、程序阅读
代码填空（mid 计算、边界更新）	★★★★★	代码填空高频
复杂度分析（O(log n)）	★★★★☆	选择题
lower_bound/upper_bound 语义		选择题
STL 二分函数使用		编程题
二分查找综合应用		编程题

二、二分查找的基本原理

2.1 前提条件

二分查找要求数据序列是有序的（升序或降序）。只有在有序数组中，才能通过比较中间值来判断目标值应该落在左半部分还是右半部分。

2.2 折半思想

二分查找的核心操作是“每次将查找区间缩小一半”：取中间元素与目标比较，排除不可能的一半，在剩余一半中继续查找，直到找到目标或区间为空。

执行过程示例：在升序数组 [1, 3, 5, 7, 9, 11] 中查找 7：

初始区间 [0, 5]，mid = 2，a[2] = 5 < 7 → 目标在右半
区间 [3, 5]，mid = 4，a[4] = 9 > 7 → 目标在左半
区间 [3, 3]，mid = 3，a[3] = 7 == 7 → 找到！返回下标 3

2.3 时间复杂度

每次比较将搜索区间减半，最多比较 ⌈log₂n⌉ 次，时间复杂度为 O(log n)。以 n = 10⁶ 为例，最多比较约 20 次，远优于顺序查找的 10⁶ 次。

空间复杂度：迭代版本为 O(1)，递归版本为 O(log n)。

三、整数二分的两种写法

整数二分的边界处理是五级最高频的易错点。根据区间定义的不同，有两种主要写法。

3.1 写法一：全闭区间 [left, right]

int left = 0, right = n - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;

要点：

初始 right = n - 1，区间包含两端。
循环条件 left <= right，当 left == right 时区间仍有效。
a[mid] < target 时 left = mid + 1；a[mid] > target 时 right = mid - 1。
如果目标不存在，最终 left > right，循环结束。

3.2 写法二：半开区间 [left, right)

int left = 0, right = n;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (a[mid] >= target) right = mid;
    else left = mid + 1;
}
return left;   // 第一个 >= target 的位置

要点：

初始 right = n，区间不包含右端点。
循环条件 left < right。
这种写法常用于求“第一个满足条件的位置”（即 lower_bound）。

3.3 两种写法对比

对比项	全闭区间	半开区间
初始区间	[0, n-1]	[0, n)
循环条件	`left <= right`	`left < right`
更新方式	mid ± 1	一侧为 mid
适用场景	查找确定值	查找边界/插入位置
返回值	找到返回下标，否则 -1	返回第一个满足条件的位置

四、避免死循环与溢出

4.1 mid 计算溢出

错误写法：mid = (left + right) / 2;

当 left 和 right 都很大时，left + right 可能超出 int 范围，导致溢出，mid 变成负数。例如 left = right = 1073741824 时，left + right = 2147483648 超出 int 最大值，结果为负数。

正确写法：

int mid = left + (right - left) / 2;   // 推荐

或使用位运算：

int mid = left + ((right - left) >> 1);   // 了解即可

记忆口诀：加法会溢出，减法最安全。

4.2 死循环的两种情况

当区间大小为 2 时，mid = left + (right - left) / 2 偏左，如果更新 left = mid 而不加 1，可能死循环。
当区间大小为 2 时，mid = left + (right - left + 1) / 2 偏右，如果更新 right = mid 而不减 1，可能死循环。

防死循环规则：

如果更新 right = mid，则 mid 应偏左（用 left + (right - left) / 2）。
如果更新 left = mid，则 mid 应偏右（用 left + (right - left + 1) / 2）。

五、lower_bound 与 upper_bound

5.1 语义区别

对于有序数组：

函数	返回值	含义
`lower_bound`	第一个 ≥ target 的元素位置	最左侧的插入位置
`upper_bound`	第一个 > target 的元素位置	最右侧的插入位置

关键理解：

lower_bound 返回“第一个不小于 target 的位置”。
upper_bound 返回“第一个大于 target 的位置”。
两者仅在 target 不存在于序列中时才相同。

示例：数组 [1, 2, 2, 2, 3, 5]，target = 2

lower_bound(2) → 下标 1（第一个 2）
upper_bound(2) → 下标 4（第一个 > 2 的元素，即 3）

5.2 STL 用法

#include <algorithm>

int a[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;

// 查找第一个 >= target 的位置
int* p1 = lower_bound(a, a + n, target);
cout << p1 - a << endl;   // 输出 2

// 查找第一个 > target 的位置
int* p2 = upper_bound(a, a + n, target);
cout << p2 - a << endl;   // 输出 3

STL 二分的优势：代码简洁、经过高度优化、不容易出错。在五级编程题中，如果只需要判断存在性或查找位置，优先使用 STL 的 lower_bound/upper_bound/binary_search。

5.3 底层实现（了解）

lower_bound 的底层实现就是半开区间的二分：

// lower_bound 的简化实现
int lower_bound_impl(int a[], int n, int target) {
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

5.4 binary_search

if (binary_search(a, a + n, target)) {
    cout << "存在" << endl;
}

只返回 bool，不返回位置，适合只判断存在性的场景。

六、二分查找的递归实现

int binarySearch(int a[], int left, int right, int target) {
    if (left > right) return -1;              // 终止条件
    int mid = left + (right - left) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target)
        return binarySearch(a, mid + 1, right, target);
    else
        return binarySearch(a, left, mid - 1, target);
}

递归深度：O(log n)，空间复杂度 O(log n)。

七、GESP 五级二分查找真题精讲

真题1：找数（2026年3月）

题目描述：给定包含 n 个互不相同正整数的数组 A 与包含 m 个互不相同正整数的数组 B，计算有多少个数在数组 A 与数组 B 中均出现。

数据范围：n, m ≤ 10⁵，aᵢ, bᵢ ≤ 10⁹。

解题思路：先对 B 数组排序，然后遍历 A 数组，对 A 中的每个数在 B 中二分查找。

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int a[100005], b[100005];
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &b[i]);

    sort(b + 1, b + m + 1);   // 二分查找要求有序

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int l = 1, r = m;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (b[mid] >= a[i]) r = mid - 1;
            else l = mid + 1;
        }
        if (l <= m && b[l] == a[i]) cnt++;
    }
    printf("%d", cnt);
    return 0;
}

关键点：排序后二分查找，时间复杂度 O(m log m + n log m)，远优于 O(nm) 的暴力比较。

真题2：二分查找代码填空

下面代码实现二分查找，横线处应填入（）。
int binarySearch(int a[], int n, int target) {
 int left = 0, right = n - 1;
 while (left <= right) {
     int mid = ______;
     if (a[mid] == target) return mid;
     else if (a[mid] < target) left = mid + 1;
     else right = mid - 1;
 }
 return -1;
}
A. (left + right) / 2
B. left + (right - left) / 2
C. (left + right) >> 1
D. left + right / 2
答案：B

解析：B 选项 left + (right - left) / 2 是最安全的写法，避免了 left + right 的整数溢出问题。

真题3：lower_bound 语义判断

有序数组 a = [1, 3, 5, 7, 9]，调用 lower_bound(a, a+5, 5) 返回的下标是（）。
A. 1 B. 2 C. 3 D. 4
答案：B
解析：lower_bound 返回第一个 ≥ target 的位置，a[2] = 5，是第一个 ≥ 5 的元素，下标为 2。

八、易错点汇总

数组未排序就二分：二分查找的前提是有序，必须先排序。
mid 计算溢出：(left + right) / 2 可能溢出，应写 left + (right - left) / 2。
循环条件写错：全闭区间用 left <= right，半开区间用 left < right，混用会导致漏查或死循环。
边界更新错误：全闭区间中，a[mid] < target 时 left = mid + 1，a[mid] > target 时 right = mid - 1，不能写成 left = mid 或 right = mid。
死循环：更新 left = mid 时 mid 应偏右，更新 right = mid 时 mid 应偏左。
lower_bound/upper_bound 混淆：lower_bound 返回第一个 ≥ target 的位置，upper_bound 返回第一个 > target 的位置。
数组下标从 0 还是从 1 开始混用：STL 的 lower_bound 返回指针，需要减去首地址得到下标。
对无序数组使用 STL 二分：STL 二分要求输入区间已排序，否则结果未定义。
查找目标不存在时未判断：全闭写法最终 left > right，需要额外判断是否找到。
大数比较溢出：数据范围较大时，用 long long 防止溢出。

九、速查表

需求	写法	关键注意
全闭二分查找	`while(left<=right){ mid=left+(right-left)/2; ... }`	更新 mid±1
半开二分查找	`while(left<right){ mid=left+(right-left)/2; ... }`	一侧为 mid
防溢出 mid	`mid = left + (right - left) / 2;`	不要用 `(left+right)/2`
lower_bound（手写）	`if(a[mid]>=t) right=mid; else left=mid+1;`	第一个 ≥ t
upper_bound（手写）	`if(a[mid]>t) right=mid; else left=mid+1;`	第一个 > t
STL lower_bound	`lower_bound(a, a+n, target)`	返回指针
STL upper_bound	`upper_bound(a, a+n, target)`	返回指针
STL binary_search	`binary_search(a, a+n, target)`	返回 bool
二分查找复杂度	O(log n)	每次减半
递归版本	`binarySearch(a, left, right, target)`	空间 O(log n)

十、总结

二分查找是 GESP 五级算法模块的核心内容。

二分查找的前提是数据有序，核心是每次将区间缩小一半。
时间复杂度 O(log n)，远优于顺序查找的 O(n)。
mid 计算用 left + (right - left) / 2，防止整数溢出。
全闭区间用 left <= right，半开区间用 left < right，不要混用。
边界更新：a[mid] < target 时 left = mid + 1，a[mid] > target 时 right = mid - 1。
lower_bound 返回第一个 ≥ target 的位置，upper_bound 返回第一个 > target 的位置。
STL 的 lower_bound/upper_bound/binary_search 可以直接使用，无需手写。
二分查找也常用于“找数”类问题：排序 + 二分，将 O(nm) 降为 O(n log m)。
死循环的根源是 mid 偏左/偏右与边界更新不匹配。
多练“手写二分代码填空”“lower_bound/upper_bound 语义”“找数类综合应用”三类题。

复习建议：先把全闭区间的二分查找代码写熟，确保闭卷能默写且边界不出错；再掌握半开区间写法和 lower_bound/upper_bound 的语义；然后练习“找数”等综合应用题，体会排序 + 二分的解题套路。考试中先判断题目是查找确定值还是查找边界，再确定区间写法和边界更新方式，最后检查 mid 计算和循环条件。