XZXZZXBlog

Article

二分

二分最重要的不是代码，而是这句话：只要答案满足单调性，就可能可以二分。

约 8 分钟

文章目录

二分最重要的不是代码，而是这句话：

  • 只要答案满足单调性，就可能可以二分

先把最重要的提醒写在最前面：

  • 没有单调性，就不要用二分
  • 不管是二分查找、二分答案还是小数二分，本质都依赖“左边和右边能被单调地分开”
  • 如果 check(mid) 不是单调变化的，代码模板写得再漂亮也是错的

你平时用的是：

  • while (l + 1 < r)
  • 红绿灯标记法

那这篇笔记就完全按这套体系来写，不混别的模板。

1. 红绿灯二分是什么

红绿灯写法的核心是：

  • l 表示一个“红灯位置”：一定不合法
  • r 表示一个“绿灯位置”：一定合法

然后不断二分：

C++
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) r = mid;  // mid 是绿灯
    else l = mid;             // mid 是红灯
}

循环结束时：

  • l 和 r 相邻
  • l 是最后一个红灯
  • r 是第一个绿灯

这就是最标准的“找第一个合法位置”的写法。

2. 这套写法为什么好用

它的优点很明显：

  • 不容易死循环
  • 边界语义很清楚
  • 左边界、右边界、二分答案都能统一

你只需要每次先想清楚：

  1. 谁是红灯
  2. 谁是绿灯
  3. check(mid) 返回真时，mid 应该归到哪边

如果这三件事想清楚了，代码就很稳。

mid⁡=l+⌊r−l2⌋\operatorname{mid} = l + \left\lfloor \frac{r-l}{2} \right\rfloor

3. 二分查找

二分查找的前提通常是：

  • 数组有序

但真正写代码时，不要只记“找数”，而是记：

  • 找第一个满足条件的位置
  • 找最后一个满足条件的位置

这才是竞赛里更常见的用法。

4. 找第一个大于等于 x 的位置

这个就是典型的左边界。

定义：

  • 红灯：a[mid] < x
  • 绿灯：a[mid] >= x

那么模板写成：

C++
int l = -1, r = n;  // l 红，r 绿
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] >= x) r = mid;
    else l = mid;
}

最后：

  • r 就是第一个满足 a[i] >= x 的位置

注意：

  • 如果 r == n，说明不存在这样的元素

5. 找第一个大于 x 的位置

定义：

  • 红灯：a[mid] <= x
  • 绿灯：a[mid] > x

模板：

C++
int l = -1, r = n;
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] > x) r = mid;
    else l = mid;
}

最后：

  • r 就是第一个满足 a[i] > x 的位置

6. 找最后一个小于等于 x 的位置

这次把语义反过来：

  • 绿灯：a[mid] <= x
  • 红灯：a[mid] > x

模板：

C++
int l = -1, r = n;  // l 绿，r 红
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] <= x) l = mid;
    else r = mid;
}

最后：

  • l 就是最后一个满足 a[i] <= x 的位置

注意：

  • 如果 l == -1，说明不存在这样的元素

表格保持真实的行列语义和可辨认的列宽；窄屏放不下时只在表格区域滚动。

表格较宽时可在此区域横向滑动。

红绿灯边界更新
边界状态check(mid)下一步区间最终位置
l 为红，r 为绿真[l, mid]第一处绿色位置 r
l 为绿，r 为红真[mid, r]最后一处绿色位置 l

7. 找最后一个小于 x 的位置

定义：

  • 绿灯：a[mid] < x
  • 红灯：a[mid] >= x

模板：

C++
int l = -1, r = n;
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] < x) l = mid;
    else r = mid;
}

最后：

  • l 就是最后一个满足 a[i] < x 的位置

8. 二分查找怎么理解

红绿灯写法本质上是在找“分界线”。

例如：

Text
红 红 红 红 绿 绿 绿 绿

你要找的就是：

  • 最后一个红
  • 或第一个绿

这比死背“左边界模板”“右边界模板”更稳，因为你是真的在理解边界。

9. 二分答案

二分答案和二分查找的区别是：

  • 你不是在有序数组里找位置
  • 你是在答案空间里找最优值

最常见的是：

  • 最小可行值
  • 最大可行值

只要 check(x) 满足单调性，就能用红绿灯来写。

10. 二分答案的核心条件

二分答案一定要有三样东西：

10.1 答案区间

例如：

  • [0, 1e9]
  • [max(a), sum(a)]

10.2 check(x)

也就是：

  • 假设答案是 x
  • 问“能不能做到”

10.3 单调性

例如：

  • 如果 x 能做到，那么更大的 x 也能做到
  • 或者反过来

没有单调性，就不能二分。

11. 最小可行值

这是最常见的二分答案类型。

定义：

  • 红灯：x 不可行
  • 绿灯：x 可行

模板：

C++
int l = L - 1, r = R;  // l 红，r 绿
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}
cout << r << '\n';

最后：

  • r 就是最小可行值

12. 最大可行值

定义：

  • 绿灯：x 可行
  • 红灯：x 不可行

模板：

C++
int l = L, r = R + 1;  // l 绿，r 红
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}
cout << l << '\n';

最后：

  • l 就是最大可行值

13. 二分答案怎么定边界

这一步很关键。

13.1 最小化最大值类

常见边界：

C++
l = max(a[i]) - 1;   // 红灯
r = sum(a[i]);       // 绿灯

因为：

  • 比最大元素还小，一定不行
  • 取总和，一定可行

13.2 最大化最小值类

常见做法：

  • 找一个一定可行的左边界
  • 找一个一定不行的右边界

关键不是边界多漂亮，而是：

  • 必须保证红绿语义成立

14. 小数二分

小数二分用于：

  • 答案是实数
  • 条件仍然满足单调性

例如：

  • 求方程根
  • 求贷款利率
  • 求某个实数最优解

15. 小数二分模板

小数二分虽然不太讲“相邻”，但思想还是一样：

  • 一边红
  • 一边绿
  • 不断逼近

模板：

C++
double l = L, r = R;
while (r - l > eps) {
    double mid = (l + r) / 2.0;
    if (check(mid)) r = mid;
    else l = mid;
}

如果你想固定循环次数，也可以：

C++
for (int i = 0; i < 100; ++i) {
    double mid = (l + r) / 2.0;
    if (check(mid)) r = mid;
    else l = mid;
}

16. 小数二分的关键点

16.1 eps

eps 表示精度要求。

例如：

C++
const double eps = 1e-7;

16.2 输出精度

通常配合：

C++
cout << fixed << setprecision(6) << ans << '\n';

16.3 不要拿浮点数判完全相等

小数二分的停止条件一般都是：

C++
r - l > eps

而不是判断某个值是否“刚好等于”答案。

17. 三类二分怎么区分

17.1 二分查找

  • 在有序数组里找边界或位置

17.2 二分答案

  • 在整数答案空间里找最优值

17.3 小数二分

  • 在实数答案空间里逼近结果

你可以这样记：

  • 查位置 -> 二分查找
  • 查整数最优解 -> 二分答案
  • 查实数最优解 -> 小数二分

18. STL 里的二分函数

除了手写二分，STL 里还有一整套现成的二分函数。

最常用的是：

  • lower_bound
  • upper_bound
  • binary_search
  • equal_range

它们最常用于：

  • 已排序数组
  • vector
  • deque
  • 普通区间迭代器

19. lower_bound

19.1 含义

C++
lower_bound(first, last, x)

返回：

  • 区间里第一个 大于等于 x 的位置

19.2 例子

C++
vector<int> a = {1, 2, 2, 4, 6};
auto it = lower_bound(a.begin(), a.end(), 2);
cout << it - a.begin() << '\n';  // 1

19.3 如果找不到

会返回：

C++
a.end()

所以要先判：

C++
if (it != a.end()) {
    cout << *it << '\n';
}

20. upper_bound

20.1 含义

C++
upper_bound(first, last, x)

返回：

  • 区间里第一个 大于 x 的位置

20.2 例子

C++
vector<int> a = {1, 2, 2, 4, 6};
auto it = upper_bound(a.begin(), a.end(), 2);
cout << it - a.begin() << '\n';  // 3

因为下标 1, 2 都是 2，第一个大于 2 的是 4。

21.1 含义

C++
binary_search(first, last, x)

返回：

  • true / false
  • 表示 x 是否存在

21.2 例子

C++
vector<int> a = {1, 2, 2, 4, 6};
cout << binary_search(a.begin(), a.end(), 4) << '\n';  // 1
cout << binary_search(a.begin(), a.end(), 3) << '\n';  // 0

21.3 什么时候用它

如果你只关心：

  • 某个值在不在

那它最省事。

如果你还要位置，通常还是用：

  • lower_bound
  • upper_bound

22. equal_range

22.1 含义

C++
equal_range(first, last, x)

返回一个 pair：

  • .first 是 lower_bound
  • .second 是 upper_bound

也就是：

  • 等于 x 的那一段区间

22.2 例子

C++
vector<int> a = {1, 2, 2, 2, 4, 6};
auto p = equal_range(a.begin(), a.end(), 2);

cout << p.first - a.begin() << '\n';   // 1
cout << p.second - a.begin() << '\n';  // 4

说明：

  • 下标 [1, 4) 这一段都是 2

23. 用 STL 二分函数的前提

这些算法版二分函数有一个硬前提：

  • 区间必须按同一比较规则排好序

例如：

C++
sort(a.begin(), a.end());
auto it = lower_bound(a.begin(), a.end(), x);

如果区间没排好序，结果是错的。

24. set.lower_bound() 为什么更该优先想到

这点非常重要。

对于 set、multiset、map、multimap 这种关联容器：

  • 优先用成员函数版
  • 不要优先想算法版 lower_bound(begin, end, x)

也就是写：

C++
s.lower_bound(x)

而不是：

C++
lower_bound(s.begin(), s.end(), x)

25. 为什么 set.lower_bound() 更好

因为：

  • set 底层是平衡树
  • 成员函数会直接沿树查找
  • 复杂度是 O(log n)

而算法版：

C++
lower_bound(s.begin(), s.end(), x)

虽然语法上能写，但对非随机访问迭代器来说：

  • 移动迭代器本身要花代价
  • 常数和实现都不如成员函数自然

所以结论直接记：

  • vector / 数组 / deque：优先想算法版 lower_bound
  • 关联容器里这些常用的都优先想成员函数版：
    • set.lower_bound()
    • multiset.lower_bound()
    • map.lower_bound()
    • multimap.lower_bound()

26. set / multiset / map 常见二分函数

26.1 set.lower_bound(x)

返回：

  • 第一个 大于等于 x 的元素迭代器
C++
set<int> s = {1, 3, 5, 7};
auto it = s.lower_bound(4);
if (it != s.end()) cout << *it << '\n';  // 5

26.2 set.upper_bound(x)

返回：

  • 第一个 大于 x 的元素迭代器
C++
auto it = s.upper_bound(5);
if (it != s.end()) cout << *it << '\n';  // 7

26.3 multiset.lower_bound(x) / multiset.upper_bound(x)

和 set 含义相同，但：

  • multiset 允许重复

所以它们经常搭配起来求某个值的出现区间。

C++
multiset<int> s = {1, 2, 2, 2, 5};
auto L = s.lower_bound(2);
auto R = s.upper_bound(2);

26.4 map.lower_bound(x)

返回：

  • 键值 key >= x 的第一个键值对迭代器
C++
map<int, int> mp;
mp[2] = 20;
mp[5] = 50;
mp[8] = 80;

auto it = mp.lower_bound(4);
if (it != mp.end()) {
    cout << it->first << ' ' << it->second << '\n';  // 5 50
}

27. 前驱和后继怎么结合 STL 二分函数

27.1 后继

后继通常就是：

  • 第一个大于等于 x 的数
  • 或第一个大于 x 的数

所以常用：

C++
auto it = s.lower_bound(x);
auto it = s.upper_bound(x);

27.2 前驱

前驱通常做法是：

C++
auto it = s.lower_bound(x);
if (it != s.begin()) {
    --it;
    cout << *it << '\n';
}

注意：

  • 先判 it != s.begin()
  • 否则不能 --it

28. vector 上 STL 二分的最常见用法

28.1 找值第一次出现的位置

C++
auto it = lower_bound(a.begin(), a.end(), x);
if (it != a.end() && *it == x) {
    cout << it - a.begin() << '\n';
}

28.2 统计某个值出现次数

C++
int cnt = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x);

28.3 查第一个不小于 x 的位置

C++
int pos = lower_bound(a.begin(), a.end(), x) - a.begin();

29. 高频坑点补充

29.1 忘了排序

C++
lower_bound
upper_bound
binary_search
equal_range

这些算法版函数都默认区间已经排好序。

29.2 set 上机械使用算法版 lower_bound

能写，不代表是你该优先想到的写法。

正确习惯是：

C++
s.lower_bound(x)
mp.lower_bound(x)

29.3 lower_bound 找到的不一定等于 x

它只保证：

  • 第一个 >= x

所以如果你想判断“是否真的存在 x”，要再判：

C++
if (it != a.end() && *it == x)

29.4 end() 不能解引用

这一条在 vector、set、map 上都一样重要。

30. 高频坑点

18.1 红绿语义没定义清楚

这是最常见 bug。

写之前必须先说清楚：

  • l 是红还是绿
  • r 是红还是绿
  • check(mid) 为真时，mid 应归哪边

18.2 边界本身不合法

如果你一开始的：

  • 红灯不是真的红
  • 绿灯不是真的绿

整套二分都会错。

18.3 check 没有单调性

没有单调性就不能二分。

18.4 小数二分精度不够

可能导致：

  • WA
  • 输出误差超限

18.5 普通找值和红绿灯写法混着写

可以混，但容易乱。

如果你已经习惯红绿灯，那最好：

  • 边界查找和二分答案统一用红绿灯
  • 普通“找某个值是否存在”保留朴素写法即可

31. 最小必背模板

19.1 找第一个合法位置

C++
int l = bad, r = good;
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}

最后：

  • r 是第一个合法位置

19.2 找最后一个合法位置

C++
int l = good, r = bad;
while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

最后：

  • l 是最后一个合法位置

19.3 小数二分

C++
while (r - l > eps) {
    double mid = (l + r) / 2.0;
    if (check(mid)) r = mid;
    else l = mid;
}

19.4 STL 二分函数

C++
lower_bound(a.begin(), a.end(), x);  // 第一个 >= x
upper_bound(a.begin(), a.end(), x);  // 第一个 > x
binary_search(a.begin(), a.end(), x);
s.lower_bound(x);                    // 关联容器优先用成员函数
ms.lower_bound(x);
mp.lower_bound(x);
mmp.lower_bound(x);

32. 一句话总结

对你来说，二分最应该背的不是“左边界模板”和“右边界模板”这几个词，而是：

  • 先找单调性
  • 再定义红绿灯
  • 最后用 while (l + 1 < r) 去夹边界

补一句 STL 层面的习惯：

  • 数组 / vector / deque 想算法版 lower_bound
  • set / multiset / map / multimap 优先想成员函数版 .lower_bound()

代码只是形式，红绿语义和容器习惯才是二分真正稳定的核心。