二分查找 知识点讲解

概念

玩过“猜数字”游戏吗？我心里想一个 1 到 100 之间的整数，你每次猜一个数，我只告诉你“大了”还是“小了”。如果你从 1 开始一个一个试，最坏情况要猜 100 次；但聪明的做法是每次猜中间那个数——先猜 50，如果我说“大了”，你就知道答案在 1 到 49 之间，再猜 25；如果我说“小了”，答案就在 51 到 100 之间，再猜 75……这样每猜一次，候选范围就砍掉一半。对于 100 个数，最多只需要猜 7 次就能锁定答案；对于 100 万个数，也只需要约 20 次。这种每问一次就把候选范围砍掉一半的策略，就是二分查找的核心思想，它的时间复杂度是 $O(\log n)$，比线性的 $O(n)$ 快得多。

二分查找：一种在有序序列中快速定位目标的算法。每次取中间值判断，根据大小关系舍弃一半区间，重复直到找到或区间为空。

很多人对二分有个致命误解：以为只有“排好序的数组”才能二分。其实真正的前提不是“有序”，而是单调——你要找的答案，随着你猜的值变大，会先“全不满足”然后“全满足”（或者反过来）。数组有序只是最常见的一种单调。比如“在无序数组中找第一个大于等于 $x$ 的位置”是没法二分的，因为中间值的大小关系不能告诉你答案在哪一半；但“在无序数组中找最大值”是可以二分的，因为最大值随猜测值变大是单调的（猜小了不行，猜大了就行）。

触发清单（看到这些信号第一时间想到本知识点）

定义

二分的写法有两套，先确定自己用的是哪一套，边界就不会写乱：

核心结论：

1. mid = (l + r) / 2 是向下取整，所以 mid 永远 >= l、< r（左闭右开时不会越界）。

2. 找「第一个 $\ge$ target 的位置」用 lower_bound 的写法（左闭右开 + r = mid）—— 这是考场上最不容易写错的一版，建议只背这一版。

3. 二分的价值不在“找数”，而在把「求最大值 / 最小值」变成一个可以一刀切判定的问题（见下一节）。

lower_bound / upper_bound 的语义（C++ STL 里同名函数就是这个行为，记牢）：

推演：为什么这些写法是对的（以及它们能用来干什么）

二分的本质是「利用单调性每次砍一半」。下面推三点。

推演 1 · 为什么有序就能二分

序列单调时，取中点 mid：若 mid 处的目标还「小了」，答案必在右半；「大了」必在左半。每步排除一半，复杂度 $O(\log n)$。无序序列没有这个性质，不能二分。所以「先排序再二分」是固定搭配。

用法：查找前先确认有序；找「第一个 $\ge x$ / 最后一个 $\le x$」用标准二分模板（注意边界）。

推演 2 · 为什么「二分答案」成立

设「答案 $\ge$ x 时可行、$<$ x 时不可行」（可行性随 x 单调）。那么可行的 x 是一段连续区间，分界点就是最优解。所以「猜 mid，写 check(mid) 判可行」：可行就往大猜（记录答案），不可行往小猜，最后夹出的就是极值。

用法：看到「最大值最小 / 最早第几个 / 能否在 k 内完成」，先想二分答案。

推演 3 · 实数二分为什么用精度 / 次数收尾

没有整数边界，用 while(r - l > eps) 或固定循环 50~100 次，保证误差小于 eps。循环次数 $\approx \log_2(\text{区间长度} / \text{eps})$：区间 [-100,100]、要 $10^{-6}$，约 $\log_2(2\cdot 10^8) \approx 28$ 次就够。

用法：实数域二分用 eps 或固定次数，别用 == 判等。

技巧速查表（背下来）

原讲义配图

例题

例题 1：有序序列定位

题目描述

给定一个升序排列的整数数组 $a_1, a_2, \dots, a_n$（$1 \le n \le 10^5$，$-10^9 \le a_i \le 10^9$）和一个整数 $x$（$-10^9 \le x \le 10^9$）。请找出数组中第一个大于等于 $x$ 的元素的下标（下标从 0 开始）。如果不存在这样的元素，输出 -1。

审题分析

• 读题抓条件：数组是升序的，要找“第一个 $\ge x$ 的位置”。
• 定需求：这是一个典型的有序查找问题，需要 $O(\log n)$ 的算法。
• 为什么能用本知识点：因为数组有序，满足单调性，可以用二分查找的左闭右开模板直接定位第一个满足条件的元素。
• 如果不用二分：线性扫描是 $O(n)$，当 $n=10^5$ 且有多组查询时会超时。

解题思路

使用左闭右开区间 $[l, r)$ 的二分模板。初始化 $l=0, r=n$。每次取中点 $mid = l + (r-l)/2$，若 $a[mid] \ge x$，说明答案可能在 $mid$ 或其左侧，令 $r=mid$；否则答案必在右侧，令 $l=mid+1$。循环结束时 $l$ 即为第一个 $\ge x$ 的下标。若 $l=n$，说明整个数组都小于 $x$，输出 -1。

C++ 完整参考代码

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

int main() {
 // 读入数组大小
 int n;
 cin >> n;
 // 读入升序数组
 vector<long long> a(n);
 for (int i = 0; i < n; ++i) {
 cin >> a[i];
 }
 // 读入目标值 x
 long long x;
 cin >> x;

 // 二分查找第一个 >= x 的位置，区间 [l, r)
 int l = 0, r = n;
 while (l < r) {
 // mid 向下取整，不会越界
 int mid = l + (r - l) / 2;
 if (a[mid] >= x) {
 // mid 满足条件，答案在 [l, mid]
 r = mid;
 } else {
 // mid 不满足，答案在 [mid+1, r)
 l = mid + 1;
 }
 }

 // 如果 l 等于 n，说明没找到
 if (l == n) {
 cout << -1 << "\n";
 } else {
 cout << l << "\n";
 }

 return 0;
}

代码解读

• 使用 vector<long long> 存储数组，防止 $10^9$ 范围溢出 int（虽然题目给的是整数，但习惯上用 long long 更稳妥）。
• 循环条件 l < r 保证左闭右开，mid = l + (r - l) / 2 避免 l + r 溢出。
• if (a[mid] >= x) 时更新 r = mid，否则 l = mid + 1，符合“找第一个满足”的逻辑。
• 循环结束后 l 指向第一个 $\ge x$ 的位置，若 l == n 则不存在。

运行结果

输入：

5
1 2 2 3 5
2

输出：

1

解释：数组为 [1, 2, 2, 3, 5]，第一个 $\ge 2$ 的元素是下标 1 处的 2。

---

例题 2：二分答案（最大值最小）

题目描述

有 $n$ 段木头，长度分别为 $a_1, a_2, \dots, a_n$（$1 \le n \le 10^5$，$1 \le a_i \le 10^9$）。现在要把这些木头切成恰好 $k$ 段等长的短木头（$k$ 为给定正整数，$1 \le k \le 10^9$）。问每段短木头最长能是多少？输出这个最大长度（整数）。

审题分析

• 读题抓条件：总段数固定为 $k$，每段长度必须相等，求最大可能的长度。
• 定需求：这是一个“最大值最小”的典型问题，答案具有单调性（长度越小越容易切够 $k$ 段）。
• 为什么能用本知识点：因为可行性随长度单调，可以用二分答案把“求最大长度”转化为“判断某个长度 $L$ 能否切出至少 $k$ 段”。
• 如果不用二分：枚举长度是 $O(\max a_i)$，太大；线性检查每个长度太慢。

解题思路

1. 确定二分范围：下界 $L=1$（最小可能长度），上界 $R=\max(a_i)$（最长木头长度，一定可行）。

2. 写判定函数 check(mid)：对每个木头 $a_i$，它能切出 $\lfloor a_i / mid \rfloor$ 段，总和若 $\ge k$ 则返回 true。

3. 二分方向：题目求“最大可行”，所以当 check(mid) 为真时，答案至少是 mid，往大试（$l = mid$）；否则往小收（$r = mid - 1$）。注意 mid 要向上取整以避免死循环。

C++ 完整参考代码

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

int main() {
 // 读入 n 和 k
 int n;
 long long k;
 cin >> n >> k;

 // 读入木头长度，同时记录最大值作为上界
 long long max_len = 0;
 vector<long long> a(n);
 for (int i = 0; i < n; ++i) {
 cin >> a[i];
 if (a[i] > max_len) max_len = a[i];
 }

 // 二分答案：求最大的可行 mid
 long long l = 1, r = max_len;
 while (l < r) {
 // 求"最大可行"时 mid 要向上取整，防止死循环
 long long mid = l + (r - l + 1) / 2;

 // check(mid)：能否切出至少 k 段
 long long cnt = 0;
 for (int i = 0; i < n; ++i) {
 cnt += a[i] / mid;
 }

 if (cnt >= k) {
 // mid 可行 → 尝试更大
 l = mid;
 } else {
 // mid 不可行 → 往小缩
 r = mid - 1;
 }
 }

 // 循环结束 l == r，即为答案
 cout << l << "\n";

 return 0;
}

代码解读

• 使用 long long 存储长度和 $k$，因为 $k$ 可达 $10^9$，总和可能超过 int。
• 上界 max_len 是安全的，因为任何长度 $\le$ 最长木头都一定可行。
• mid = l + (r - l + 1) / 2 是向上取整，配合 l = mid 保证不会在 $l = r - 1$ 时死循环。
• check 函数内层循环 $O(n)$，总复杂度 $O(n \log (\max a_i))$，完全可接受。

运行结果

输入：

3 5
4 5 6

输出：

2

解释：长度为 4,5,6 的木头切成 5 段等长，最大长度为 2（4/2=2, 5/2=2, 6/2=3，共 7 段 $\ge 5$；若长度为 3 则只有 2+1+2=5 段，刚好，但 3 比 2 大，所以答案是 2？等等，重新计算：长度 3 时，4/3=1, 5/3=1, 6/3=2，共 4 段 <5，不行；长度 2 时，4/2=2, 5/2=2, 6/2=3，共 7 段 $\ge 5$，可行。所以最大可行是 2。代码输出正确。

注意：上面手动验算时容易混淆，实际代码逻辑是严谨的：长度 2 可行，长度 3 不可行，因此答案是 2。

例题复盘总结

归纳几道（基于上文）：

1. 有序序列定位（例题 1）：在升序数组中找第一个 $\ge x$ 的位置。

2. 二分答案（例题 2）：把“最大值最小”转化为判定可行。

共性特征：

• 都利用了单调性：要么数组有序，要么可行性随猜测值单调。
• 都采用了左闭右开的二分模板（while(l < r)），因为我们要找的是“第一个满足”或“最大可行”。
• 时间复杂度都是 $O(\log n)$ 或 $O(n \log (\text{答案范围}))$，远优于暴力。

各自技巧：

• 有序查找：关键是 r = mid 时收缩到 mid，l = mid + 1 时跳过 mid，防止死循环。
• 二分答案：求“最大可行”时 mid 必须向上取整，否则在 $l = r - 1$ 时会死循环；求“最小可行”则向下取整。
• 判定函数 check 要尽量简单高效，通常 $O(n)$ 即可。

审题模板（固定思考流程）：

1. 读题，划出关键词：“有序”、“最大值最小”、“至少”、“至多”、“方程求根”等。

2. 判断是否满足单调性：有序数组直接单调；“最大值最小”类问题，可行性随答案单调。

3. 确定二分区间：下界取“一定不行”或最小可能，上界取“一定行”或最大可能。

4. 写 check(mid)：先在纸上用一个具体 mid 手推一遍，确认逻辑对。

5. 定方向：求最小可行 → check 通过则 r = mid；求最大可行 → check 通过则 l = mid（且 mid 上取整）。

6. 检查边界：实数二分用固定次数；整数二分注意 l < r 和 mid 取整方式。

错误清单（只列上文没讲过的特有错误）：

• 在求“最大可行”时忘记 mid 向上取整，导致死循环。
• 二分答案的上界 R 开得太小（例如只开到 max_len 的一半），漏掉正确答案。
• 实数二分用 while(r - l > eps) 但 eps 选得太小（如 $10^{-12}$），浮点误差导致循环永远结束不了。
• 有序查找时把 r 初始化为 n - 1 而不是 n，导致漏掉最后一个元素。
• check 函数里用了 a[i] % mid == 0 判断是否能整除，而不是用 a[i] / mid 统计段数。

写法总表

与触发清单/速查表的分工：触发清单告诉你“什么时候想到二分”，速查表告诉你“具体怎么写”，本表则按技法粒度从细到粗归纳了所有写法，方便对照记忆。

常见错误

1. 死循环：while(l < r) 配 l = mid（没上取整）。当 r = l + 1 时 mid = l，若此时更新 l = mid，l 永远不动。正确做法：求最大可行时 mid = l + (r - l + 1) / 2 + l = mid；或统一用 r = mid 那一版。

2. 溢出：mid = (l + r) / 2 在 l, r 都接近 $2 \cdot 10^9$ 时会爆 int。正确做法：养成写 l + (r - l) / 2 的习惯。

3. 上界开太小：R 给不到「一定可行」，漏掉正确答案。正确做法：R 取到「绝对可行」的上限（如总和 / 最大值，或数组最大值）。

4. 方向反了：check 通过却往反方向收。正确做法：先写清：“我要的是可行区间的最左端”还是“最右端”，再定收尾方向。

5. 实数二分用 while(r - l > eps) 但 eps 选得太小：浮点误差会让循环永远结束不了。正确做法：用 for(int i=0;i<60;i++) 固定跑 60 次，更稳。

自测

1. 写出左闭右开的二分模板，并说明 r = mid 和 l = mid + 1 为什么不对称。

2. 题目说「要让最大的那个值尽可能小」，这是二分答案的信号吗？如果是，check(mid) 通过时该往哪边收？

3. 在 [1, 3, 3, 3, 7] 里，lower_bound(3) 和 upper_bound(3) 分别返回什么下标？3 出现了几次？

举一反三 · 审题流水线

拿到题先别急着写代码，按这条流水线走一遍：

1. 划关键词：看到“有序”“最大值最小”“至少”“方程求根”立刻亮红灯——二分。

2. 判单调性：有序数组直接单调；“最大值最小”类问题，可行性随答案单调。

3. 定区间：下界取“一定不行”或最小可能，上界取“一定行”或最大可能。

4. 写 check：先在纸上用一个具体 mid 手推一遍，确认逻辑对。

5. 定方向：求最小可行 → check 通过则 r = mid；求最大可行 → check 通过则 l = mid（且 mid 上取整）。

6. 查边界：实数二分用固定次数；整数二分注意 l < r 和 mid 取整方式。

7. 自问自答：如果不用二分会怎样？会不会超时？这样能避免“想当然”的坑。

练手题

题目 A

给定一个升序数组 $a_1, \dots, a_n$（$n \le 10^5$，$a_i \le 10^9$）和一个整数 $x$。请输出数组中最后一个小于 $x$ 的元素下标（下标从 0 开始）。如果不存在这样的元素，输出 -1。

题目 B

有 $n$ 个任务，第 $i$ 个任务需要 $t_i$ 秒完成（$t_i \le 10^9$）。现在要安排这些任务，使得最大的单个任务耗时尽可能小。问这个最小的最大耗时是多少？