说一下二分查找的一种理解方式

二分查找，确实是很难考虑到各个细节的，各种各样的模板。理解起来可以从区间的角度，左闭右开区间，两边闭区间等等。
但是其实有时候会发现，按照如下的代码，有时候好像既可以解决左闭右开，又可以解决两边闭区间的情况。
这个帖子将从lower bound函数的意义讲起，提供一种全新的理解方式。当然，这种方式不一定是最好的，但是个人觉得是可以帮助理解的。


先看一下lower bound的代码。

1. while (left < right) {
   
2.     int mid = left + (right - left) / 2;
   
3.     if (arr[mid] < target) {
   
4.        left = mid + 1;
   
5.     } else {
   
6.         right = mid;
   
7.     }
   
8. }
   
9. return left;

复制代码

其实理解binary search先要理解binary search到底是干什么的，这个lower bound到底又是什么的下界。
二分查找其实是这样的，一个区间可以分成左右两个部分，右边满足某个条件，而左边不满足这个条件。

如图所示，lower bound要找的其实就是满足条件的红色区域的左侧端点，也就是i + 1这个点。
把上面的代码改写一下，

1. 
   
2. while (left != right) {
   
3.     int mid = left + (right - left) / 2;
   
4.     if (arr[mid] >= target) {
   
5.         right = mid;
   
6.     } else {
   
7.         left = mid + 1;
   
8.     }
   
9. }
   
10. return left;

复制代码

这时候红色区域代表的条件就是arr[j] >= target.
当mid位于红色区域的时候，我们查询的右侧端点可以移动到mid，注意这时候是不能减一的，因为mid有可能就是最终的答案。
也就是mid是处于红色区域内的。
如果不满足当前条件，那么mid一定位于蓝色区域，此时mid一定不会是我们所要求的lower bound，因为lower bound一定是属于红色区域的。
所以，我们可以让left = mid + 1。
当循环退出的时候，此时left == right，这个点就是我们要求的红色区域左端点。因为不论何时，left - 1一定是在蓝色区域内（如果整个arr都是红色，我们把左边当作蓝色）。
只有mid落在蓝色区域内，left = mid + 1才会发生，所以left - 1一定在蓝色区域内，而right一定在红色区域内（当然这里有一个corner case， 就是整张图全蓝，这时候可以把right放在n而不是n - 1，相当于有一个红色的哨兵节点，这也就是很多时候可以看作左闭右开的原因，这样可以不用特判这种corner case）。
而最终退出的时候，left和right是相等的，所以一定是i + 1这个点。因为只有这个点满足左侧是蓝色，自己及右侧都是红色。
如果把-1和n两个点当作哨兵节点，-1这个点是蓝色区域，n这个点是红色区域的话，那么，整个loop有一个invariant，即left - 1一定在蓝色区域，而right一定在红色区域。
这样的话，当left和right相等的话，就只能是i + 1这个节点了。因为while循环的退出条件即left == right，上面的小于号其实等价于下面的不等号，不等号的另一面即等号。





补充内容 (2020-8-16 02:48):
其实求这个lower bound，就等价于求一个点i，使得i - 1在蓝色区域，而i本身在红色区域。

个人更喜欢left ≤ right, 然后maintain一个res记录你上次查找到的结果.（对于解决第一个＞xxx 或者第一个＜xxx很管用） 里面是对三种情况分别讨论, 可以合并的再合并

喜欢楼主的钻研和分享精神！

zhangzitong001 发表于 2020-08-15 08:08:59
个人更喜欢left ≤ right, 然后maintain一个res记录你上次查找到的结果.（对于解决第一个＞xxx 或者第一个＜xxx很管用） 里面是对三种情况分别讨论, 可以合并的再合并

这个写法肯定也可以啊。二分本来就有很多种写法。不过像我这样子写的话好处就是不需要特判，而且最后输出left/right都可以。最后怎么写还是看自己顺手吧，

ethan1987 发表于 2020-8-15 23:37
喜欢楼主的钻研和分享精神！

我就是觉得这样理解比较好，而且对我来说更简单一些。我喜欢把基础整明白了再去刷题。

这个二分法的理解太赞啦