深入理解二分算法算法

二分这个算法，刚开始的时候看起来感觉很简单，但其实很多人都没有理解透二分的本质。
我最开始学二分的时候，觉得这个挺简单的，很容易理解，但是在写代码的时候总是要考虑半天什么情况下 l 等于什么，什么情况下 r 等于什么，然后还总是 corner case 想不清楚。
后来就看书系统性地学了一遍二分，看着书里的二分模板在那理解半天，绞尽脑汁地想为什么有的模板这里要是 l = mid + 1，为什么那里是 r = mid，为什么这个模板 while 循环里写的不是 l <= r，然后也刷了很多二分的题，自以为弄懂了二分，但其实依旧没有看清楚二分的本质。
其实我的关注点就错了，注意力全放在二分的模板上了，根本没有想清楚什么情况下能用二分以及怎么用二分，只是以为学会了二分的模板就会写二分的题了，导致后面有时候碰到二分的题，还是要考虑半天，还是要去看一下笔记里的二分模板，要套上模板才会写。
直到后面，我真正系统性地又学了一遍二分，并且刷了大量二分的题，我才真正理解透了二分的本质。而下面，我会结合二分的题深入讲解二分的本质，带你们看清二分这个算法最核心的东西。
二分的模板这里先给出两个二分模板，我见过一些不同的二分模板，但是这两个模板是我认为使用起来最方便也最容易理解二分本质的，它们出自 AcWing @yxc。这里需要说明一下，二分的不同模板只是实现，其本质才是关键，这里我会先解释下面的二分模板，然后再结合例子阐述二分的本质，与模板结合起来讲解会更容易掌握二分。
注意：l, r 是初始化成闭区间，即 [l, r]。循环结束的条件是 l == r，所以 l, r 都一样，都是最后的结果所在位置。

while (l < r) { int mid = (l + r) >> 1; if (check()) r = mid; else l = mid + 1; }

如果把 check() 替换成 a[mid] >= target，则二分的结果是第一个大于等于 target 的数的位置。

while (l < r) { int mid = (l + r + 1) >> 1; if (check()) l = mid; else r = mid - 1; }

如果把 check() 替换成 a[mid] <= target，则二分的结果是最后一个小于等于 target 的数的位置。

模板里的 check() 表示的是是否满足某种性质（后面二分的本质里会详细介绍），如果是查找普通的有序数组中的一个数 target，那么对于第一个模板，可以把性质定义为“大于等于 target”，然后用 a[mid] >= target 替换掉 check()，则第一个模板可以查找到第一个大于等于 target 的数的位置。对于第二个模板，可以把性质定义为“小于等于 target”，然后用 a[mid] <= target 替换掉 check()，则第二个模板可以查找到最后一个小于等于 target 的数的位置。
讲完了最关键的 check()，接下来就开始讲 l, r, mid 的取值以及这样取值的用意。l, r 初始化成闭区间 [l, r] 是因为这样可以省去一些判断边界情况的麻烦，比较好处理边界情况，而对于你想要的答案不在数组内的情况，二分结束后直接判断即可 if (a[l] != target)。
对于第一个模板，缩小区间时 r = mid，是因为 mid 也满足性质，所以 mid 也有可能是答案，所以 r 可以等于 mid；而 l = mid + 1，是因为 mid 不满足条件，所以缩小的区间可以不用包括 mid，其次，当 r - l = 1，也就是只剩下两个元素的时候，如果 l 不加上 +1，那么有可能死循环（mid == l）。
当数组中存在相同的元素时也不用担心，因为 check() 那里写着 a[mid] >= target，有等于的情况，而 mid = (l + r) >> 1 相当于是二分之 (l + r) 向下取整，所以 mid 会偏向于往左取值，所以只要满足性质，r = mid 会自动向左逼近。
对于第二个模板同理，mid = (l + r + 1) >> 1 相当于是二分之 (l + r) 向上取整，所以 mid 会偏向于往右取值，当满足性质的时候，l = mid 会自动向右逼近；不满足性质时，r = mid 还要再 +1。
二分的本质二分真正的本质是：对于一个初始区间来说，如果存在某种性质，可以使得这个区间一分为二，其中一个区间满足这个性质，另一个区间不满足这个性质。这个时候就可以使用二分，来找到满足这个性质的区间的边界。
比如 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置这题。

首先看查找元素的第一个位置。

文章图片

首先定义性质为“大于等于 target 的数”（后面会解释为什么这么定义），可以把区间一分为二，右边蓝色的区间满足这个性质，而另一边不满足这个性质，所以可以用二分找到满足性质的蓝色区间的边界（这就是二分的作用），即图上标记的地方。
这个边界就是第一个满足“大于等于 target”的位置，如果这个边界位置的元素不等于 target，那么说明数组中不存在 target；如果这个边界位置的元素等于 target，那么这就是我们要找的 target 的第一个位置。
这也就是为什么性质的定义里要有等于 target，因为我们这就是我们要查找的。而为什么定义大于 target，因为这样定义才能把区间一分为二，最后求得满足性质的区间的边界。那不能定义成“小于等于 target”吗？不能，因为定义成这个，求到的边界就应该是小于等于 target 的区间的边界，而这也就是用来求我们第二个问题的：

查找元素的最后一个位置。

文章图片

这里定义性质为“小于等于 target 的数”，同样可以把区间一分为二，左边蓝色的区间满足这个性质，最后二分求得的边界就会是这个蓝色区间的边界，而另一边是不满足这个性质的。边界的位置是小于等于 target 的最后一个位置，然后我们判断一下边界位置的元素是否等于 target，等于的话，则就是我们要找到的位置。
我们再来看一个题 LeetCode 153. 寻找旋转排序数组中的最小值。
这个题让我们求最小值，但是数组在旋转之后可能会产生一段大一点的有序区间，一段小一点的有序区间，也就是一大一小两个区间，这个能直接套二分吗？等等，一大一小两个区间，然后要求小区间的最小值（边界），这不就是二分的本质作用吗。
我们首先定义性质为：小于等于“数组末尾那个数”的数，则可以将初始区间一分为二，如图所示。

文章图片

蓝色的区间就是满足性质的区间，这个区间的边界也就是我们要求的答案。使用第一个模板即可求得这个满足性质的区间的边界。代码如下：

int l = 0, r = a.size() - 1; while (l < r) { int mid = (l + r) >> 1; if (a[mid] <= a[r]) r = mid; else l = mid + 1; } return a[l];

有些人可能会认为二分的本质是单调性，其实并不是。我们可以发现这道题的区间是不满足单调性的，但是也可以使用二分。二分的本质其实并不是单调性，只是说存在单调性的话，那么可以采用二分；如果不存在单调性的话，但是可以根据某个性质，将区间一分为二，那么就可以采用二分。普通的在一个有序区间内使用二分查找只是二分的一种应用，根据性质划分区间，然后用二分寻找区间的边界才是二分真正的用法。
最后再来看一道题加深对二分本质的理解：LeetCode 1482. 制作 m 束花所需的最少天数。
这题可能有些人很容易想错，看到是求最少天数，也就是求最优值，直接开始 DP，而且给出来的数组是完全无序的，看不出来哪里能二分。但其实想清楚了二分的本质之后，就知道这题就应该用二分。二分和数组以及单调性并没有直接的关系，和二分有直接关系的是问题的解的所在区间。
对于制作 m 束花所需要的天数，只要花的数量够，那么天数多一点，就肯定可以制作 m 束花；如果天数少了，就不能制作 m 束花，这不正好把所有天数划分成两个区间了吗，然后要求的“制作 m 束花所需的最少天数”正好就是“所有可以制作 m 束花的天数的区间”的边界。嗯，那这个正好就是二分所擅长的事。

文章图片

由于边界在左边，所以我们采用能向左逼近求边界的第一个模板。然后由于性质是“可以制作 m 束花”，显然这个没法直接写在二分的 if 判断里，这就需要实现一个 check() 函数去检查当前二分的 mid 是否满足性质。

if (m > bloomDay.size() / k) return -1; int l = 1, r = 1e9 + 10; while (l < r) { int mid = (l + r) >> 1; if (check(bloomDay, m, k, mid)) r = mid; else l = mid + 1; } return l;

这种类型的题也被称为二分答案，但本质都是一样的，不论是二分查找还是二分答案，都是关注问题的解的所在区间能否根据某个性质一分为二，然后采用二分即可求得边界（解）。
总结前面的内容主要深入讲解了理解二分的本质以及怎么使用二分求解，但是碰到一个问题该如何判断能不能用二分来求解。这里，我来做一个二分整体的总结：

首先看问题的解的所在区间能否根据某个性质一分为二，如果能，则可以使用二分。
实现这个性质（check()）。
如果边界在区间的左边，则使用第一个模板：向左逼近求边界。
如果边界在区间的右边，则使用第二个模板：向右逼近求边界。

练习题下面是一些二分的基础算法题。如果没有彻底掌握二分的话，一定要多刷一些题来加深自己对二分的理解。如果做完某道题的时候觉得还不熟练，那么就删掉代码多做几次，重复思考的过程会让自己有更深的理解。
LeetCode 35. 搜索插入位置
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
LeetCode 153. 寻找旋转排序数组中的最小值
LeetCode 154. 寻找旋转排序数组中的最小值 II
LeetCode 33. 搜索旋转排序数组
LeetCode 81. 搜索旋转排序数组 II
LeetCode 69. x 的平方根（浮点数二分）
LeetCode 1011. 在 D 天内送达包裹的能力（二分答案）
LeetCode 1482. 制作 m 束花所需的最少天数（二分答案）
【深入理解二分算法】洛谷的官方二分题单【算法1-6】二分查找与二分答案