关于算法:深入理解二分算法

二分这个算法，刚开始的时候看起来感觉很简略，但其实很多人都没有了解透二分的实质。

我最开始学二分的时候，感觉这个挺简略的，很容易了解，然而在写代码的时候总是要思考半天什么状况下 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. 在排序数组中查找元素的第一个和最初一个地位 这题。

1. 首先看查找元素的第一个地位。

首先定义性质为“大于等于 target 的数”（前面会解释为什么这么定义），能够把区间一分为二，左边蓝色的区间满足这个性质，而另一边不满足这个性质，所以能够用二分找到满足性质的蓝色区间的边界（这就是二分的作用），即图上标记的中央。

这个边界就是第一个满足“大于等于 target”的地位，如果这个边界地位的元素不等于 target，那么阐明数组中不存在 target；如果这个边界地位的元素等于 target，那么这就是咱们要找的 target 的第一个地位。

这也就是为什么性质的定义里要有等于 target，因为咱们这就是咱们要查找的。而为什么定义大于 target，因为这样定义能力把区间一分为二，最初求得 满足性质的区间 的边界。那不能定义成“小于等于 target”吗？不能，因为定义成这个，求到的边界就应该是小于等于 target 的区间的边界，而这也就是用来求咱们第二个问题的：

2. 查找元素的最初一个地位。

这里定义性质为“小于等于 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;

这种类型的题也被称为二分答案，但实质都是一样的，不论是二分查找还是二分答案，都是关注 问题的解的所在区间是否依据某个性质一分为二，而后采纳二分即可求得边界（解）。

总结

后面的内容次要深刻解说了了解二分的实质以及怎么应用二分求解，然而碰到一个问题该如何判断能不能用二分来求解。这里，我来做一个二分整体的总结：

1. 首先看问题的解的所在区间是否依据某个性质一分为二，如果能，则能够应用二分。
2. 实现这个性质（check()）。
3. 如果边界在区间的右边，则应用第一个模板：向左迫近求边界。
4. 如果边界在区间的左边，则应用第二个模板：向右迫近求边界。

练习题

上面是一些二分的根底算法题。如果没有彻底把握二分的话，肯定要多刷一些题来加深本人对二分的了解。如果做完某道题的时候感觉还不纯熟，那么就删掉代码多做几次，反复思考的过程会让本人有更深的了解。

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】二分查找与二分答案