Binary Search
二分在做什么
二分的本质不是"在有序数组里找数",而是:
在一个单调的判定函数上,用 次询问定位分界点。
把问题看成:有一个序列 [false, false, ..., false, true, true, ..., true](或反过来),要找最后一个 false / 第一个 true。
找第一个 true
▼
F F F F T T T T T
0 1 2 3 4 5 6 7 8
↑
答案这个视角统一了所有二分变体。
在有序数组中查找(lower_bound / upper_bound)
C++ STL 的两个语义,背下来:
| 函数 | 含义 | 返回 |
|---|---|---|
lower_bound(beg, end, v) | 第一个 的位置 | 若不存在则 end |
upper_bound(beg, end, v) | 第一个 的位置 | 若不存在则 end |
// a = [1, 2, 2, 2, 3]
lower_bound(a, 2) → 下标 1 (第一个 2)
upper_bound(a, 2) → 下标 4 (第一个 3)
// [lower, upper) 就是值为 2 的区间:[1, 4),共 3 个由此得到常用组合:
// 计数:有几个 v
int cnt = upper_bound(a, v) - lower_bound(a, v);
// 是否存在 v
bool exist = lower_bound(a, v) != a.end() && *lower_bound(a, v) == v;
// 前驱(< v 的最大值)
auto it = lower_bound(a, v);
if (it != a.begin()) --it; // 此时 *it < v
// 后继(> v 的最小值)
auto it = upper_bound(a, v); // *it > v手写的两种写法
写法一:闭区间 [l, r](推荐,最清晰)
// 找第一个 >= v 的位置(lower_bound)
int l = 0, r = n - 1, ans = n; // ans 初始为"不存在"
while (l <= r) {
int m = l + (r - l) / 2; // 防溢出,别写 (l+r)/2
if (a[m] >= v) {
ans = m; // m 可行,先记下来
r = m - 1; // 再往左找更优的
} else {
l = m + 1;
}
}要点:
- 循环条件
l <= r - 移动时
m ± 1(必须跨过 m,否则死循环) - 用
ans记录可行解,循环自然结束时ans就是答案 m = l + (r-l)/2而不是(l+r)/2,避免l+r溢出(虽然int场景下少见,但养成习惯)
写法二:左闭右开 [l, r)
// 找第一个 >= v 的位置
int l = 0, r = n; // r 是开区间端点,取 n
while (l < r) {
int m = l + (r - l) / 2;
if (a[m] >= v) r = m; // [l, m)
else l = m + 1; // [m+1, r)
}
// 循环结束时 l == r,就是答案要点:
- 循环条件
l < r - 缩右边界时
r = m(不减 1,因为右开) - 结束时
l == r,直接就是答案,不需要额外 ans
两种写法选一个用熟即可。混用是最常见的 bug 来源。
二分答案
当问题问"最大的最小值""最少需要多少时间""最多能装多少"时,考虑二分答案。
模板
// 求满足条件的最大 x
bool check(int x) {
// 判定 x 是否可行(通常是个贪心/模拟,O(n))
}
int l = lo, r = hi, ans = lo;
while (l <= r) {
int m = l + (r - l) / 2;
if (check(m)) {
ans = m;
l = m + 1; // 可行 → 试试更大的
} else {
r = m - 1; // 不可行 → 只能更小
}
}关键:check(x) 必须对 x 单调——x 可行则所有更小的也可行(或反过来)。
经典例子:木材切割
n 根木头,长度
L[i],要切出 k 段等长的小段,求最大长度。
bool check(int len) {
if (len == 0) return true;
long long cnt = 0;
for (int x : L) {
cnt += x / len;
if (cnt >= k) return true; // 提前退出,防溢出
}
return cnt >= k;
}
// 答案越大,能切出的段数越少 → 单调 → 可二分
int l = 1, r = *max_element(L.begin(), L.end()), ans = 0;
while (l <= r) {
int m = l + (r - l) / 2;
if (check(m)) ans = m, l = m + 1;
else r = m - 1;
}单调性: 增大 → 每段更长 → 切出的段数更少。所以"能切出 段"这个性质对 单调(小的时候成立,大的时候不成立)→ 找最大的满足条件的。
二分答案的识别信号
| 题目措辞 | 二分什么 |
|---|---|
| "最大值最小" / "最小化最大值" | 二分那个"值" |
| "最少需要几天" | 二分天数 |
| "最多能装多少" | 二分容量 |
| "第 k 小" | 有时可二分值(配合计数) |
二分查找的三类变体
1. 找精确值
int l = 0, r = n - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == v) return m;
else if (a[m] < v) l = m + 1;
else r = m - 1;
}
return -1;2. 找边界(lower/upper bound)
见上文。
3. 在答案上二分(实数域)
// 求 sqrt(2),精度 1e-8
double l = 0, r = 2;
for (int i = 0; i < 100; i++) { // 固定迭代次数,别用 while(l<r)
double m = (l + r) / 2;
if (m * m < 2) l = m;
else r = m;
}
printf("%.8f\n", l);实数二分不要用 while (l < r)——浮点比较会有精度问题导致死循环。用固定迭代次数(100 次足够把区间缩到,远超 double 精度)。
4. 旋转排序数组
[4,5,6,7,0,1,2](在某个点旋转过的有序数组)中查找。
int search(vector<int>& a, int target) {
int l = 0, r = a.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == target) return m;
if (a[l] <= a[m]) { // 左半有序
if (a[l] <= target && target < a[m]) r = m - 1;
else l = m + 1;
} else { // 右半有序
if (a[m] < target && target <= a[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}思路:m 把数组分成两半,必有一半是有序的,在有序的那一半里判断 target 是否落入。
有重复元素时([2,2,2,0,2,2]),a[l] <= a[m] 的判断会失效,需要 if (a[l] == a[m]) l++; 跳过,最坏退化到。
C++ 标准库相关
// 有序容器自带
std::set<int> s;
s.lower_bound(v); // 第一个 >= v 的迭代器
s.upper_bound(v); // 第一个 > v 的迭代器
// 无序数组要先排序
sort(a.begin(), a.end());
auto it = lower_bound(a.begin(), a.end(), v);
int idx = it - a.begin();
// 自定义比较(注意:比较函数必须和排序时用的一致)
lower_bound(v.begin(), v.end(), key,
[](const Item& a, int k) { return a.k < k; });复杂度
二分答案时总复杂度是:
例:值域,check 是, →,可接受。
注意:如果 check 是,二分答案可能比直接做还慢。先算总复杂度再决定。
常见坑
(l + r) / 2溢出:l、r接近INT_MAX时溢出。用l + (r - l) / 2- 死循环:
l = m而没+1,且m = (l+r)/2向下取整,当r = l+1时m = l→ 无限循环。必须保证区间每次都严格缩小 - 边界初始化错:
ans应该初始化为"确定不可行的值"还是"确定可行的值"?取决于你找的是最大还是最小 lower_boundvs 手写不一致:手写时用a[m] >= v才是 lower_bound,写成>就是 upper_bound 了- 忘了排序:对无序数组用二分,结果随机
- 单调性不成立就二分:比如"是否存在长度为 k 的上升子序列"对 k 是单调的,但"第 k 大的元素所在位置"就不一定
- 实数二分的终止条件:用固定迭代次数,不要
while (l < r)或while (r - l > eps)(后者在 eps 太小且 double 精度不够时死循环) - 二分答案的值域范围:
r取太小会漏解。宁可开大一点(比如取max_element而不是sum/n)
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/fbb0c1cd.html
更新于:2026年11月16日