二分查找常见套路与分析
注：
二分查找的思路很简单，但具体写起来，很容易在细节上搞错，本文目标是总结常见的二分查找写法细节的套路
本文代码 Java 写的，为了标明二分法代码中每种情况的业务逻辑和可读性，大部分代码没有做逻辑合并和代码优化
本文默认 nums 数组是按升序排列的
随着对二分查找理解的深入，本文内容不定期更新，也会补充算法题来做练手
本文同步发表于我的公众号（年更）
1. 思路和代码框架
这就是所谓简单的部分，二分查找无非是对于一个排好序的数组，通过检查数组中间位置元素值与 target 的大小，缩小数组的长度范围，直到找到 target，或达到循环退出条件后，做近一步判断并返回结果。
其代码框架如下：
二分查找容易出错的地方，是上述代码中省略号处应该怎么写才合适，比如到底是<=还是<，是left = mid 还是left = mid + 1，是right = mid还是right = mid - 1等，正确的写法是这几个语句恰当的组合，否则都没法通过全部用例测试。
本文将从最基本的在一个有序数组中找到 target 出发，说明几种常见的正确组合写法。
2. 如何在一个有序数组中找到 target
2.1 经典写法
最经典的写法如下：
经典的写法由于大家都熟悉，所以会忽视条件细节，所以这里再对细节做一个说明：
查询的区间范围是[0, nums.length - 1]，左右全闭
每次缩小范围时，由于 mid 已经检查过了，所以缩小范围时可以把 mid 去掉，且缩小后的范围，不论是[left, mid - 1]还是[mid + 1, right]，也都是左右全闭
退出条件是
left <= right，即退出时，left = right + 1，且每个元素都已经检查过一遍
FAQ：
1. 缩小范围时，写成 left = mid 或 right = mid，有没有问题？
不行，可能会出现死循环的 bug。
二分查找，如果一直没找到 target，那么最后范围会缩小到 2 个元素，即[left, right]，且 num[left] < num[right]。
<1> 对于 left = mid 会出现 bug 的情况是，如果 target 就是 nums 的最后一个元素，那么范围缩小到[left, right]后，继续往下执行代码的结果为：
所以如果不是 left = mid + 1 的话，范围会定格在[left, right]两个元素上，且在循环到条件范围内，会一直死循环下去；
<2> 对于 right = mid，可能会出现 bug 的情况为，如果 target 不在数组中，且 target 在 nums 数组区间范围内，那么代码还是会执行到只剩 left, right 两个元素，此时 nums[left] < target < nums[right]，这样还会有下一轮循环到执行，即：
所以如果不是 right = mid - 1，也会死循环下去(循环条件：while(left <= right))
2. 若循环退出条件写成 left < right，有什么问题？
如果条件为left < right，则当 left = right 时就退出了，这样就少查了一个元素，如果这个元素就是 target 的话，出 bug 了
另外，明白了这一点，其实循环退出条件写成left < right也没关系，此时漏掉的元素就是 left（也是 right），再加几行代码对这个元素单独处理就好了，如：
3. 经典写法有什么局限？
如果数组中有重复元素，且 target 就是重复的元素，该写法找到的只是其中某个，如果我们需要明确找到第一个或最后一个的话，就搞不定了
2.2 更巧妙的写法
注：这里所谓“更巧妙”的写法，只是为了说明这是另一种思路，在本节的经典场景下，与经典写法本质区别不大
说明：
这段代码与上一节有 3 个区别，分别在
#1、#2和#3处这里
right = nums.length而非right = nums.length - 1，且循环退出条件是left < right，意味着这里的搜索区间为[0, nums.length)，左闭右开，而后面right = mid，同样是左闭右开，既没把已经查过的 mid 包含到新范围中，也保证了新范围没有漏掉未查的元素循环退出条件是
left < right，即left == right时就退出了，由于 right 是“右开”的位置，此时其实已经到达右边界了，这里如果写的是left <= right，则可能代码执行到循环条件边界时，数组已经越界了，这里不用死记硬背由于“右开”，每轮循环时，都不会检索 nums[right]的数据，而 nums[right]其实一直是被本来循环之前的循环处理的
问题
1. 能不能写right = mid - 1？
不建议，因为“右开”，若right = mid - 1，会丢失对 mid - 1 元素的检查，这样还得对这个元素单独检查处理
2. 能不能写left = mid？
不能，因为“左闭”，直觉上就不合适，而且如果出现 target 比 nums 数组最后一个元素还大的情况，会出现上一节分析过的 bug
2.3 两种方法的对比总结
循环条件
left <= right意味着左右全闭，其搜索范围始终是[left, right]，初始值分别为 left = 0, right = nums.length - 1，搜索到最后只剩 left, right 两个元素时，会进行最后一轮搜索（left==right）确认最后一个元素 nums[right]是否为 target；循环条件
left < right意味着左闭右开，其搜索范围始终是[left, right)，初始值分别为 left = 0, right = nums.length，搜索到最后只剩 left, right 两个元素时，其实只有 left 一个元素未检查了，此时执行mid=(left + right)/2后，nums[mid]=nums[left]完成对 left 的检查，循环就结束循环代码块内二分的逻辑中，必须是
left = mid + 1，否则搜索范围缩小到只有 left、right 两个元素时，可能会进入死循环两个循环条件都可以，关键是下面二分代码中匹配恰当的逻辑，左右全闭时，必须
right = mid - 1；左闭右开时，最好right = mid，避免额外的处理逻辑
3. 找数组中重复数字 target 第一个？
3.1 基于经典写法
在经典的写法中，当 nums[mid] == target 时，就退出了，此时无非判断 mid 位置是否为 target 的第一个，修改起来也很简单，只要再判断nums[mid - 1] == target就好了，如果nums[mid - 1] < target，则 mid 就是第一个，否则向左收缩搜索范围，即right = mid - 1 即可。代码如下：
3.2 基于更巧妙的写法
2.2 节的算法，由于nums[mid] == target时，执行 right = mid，且循环终止条件时left == right，所以如果 target 在 nums 数组中，按该算法找到的 target，就是重复数字的第一个。因此，我们只需额外处理一下 target 不在 nums 数字中的情况，这个分三种情况考虑：
target 大于 nums 中最后一个元素，此时 target 不在数组中，二分查找结束后，left = right = nums.length
target 在 nums 的区间范围之内，此时 target 在数组中，二分查找结束后，nums[left] != target
target 小雨 nums 中第一个元素，此时 target 不在数组中，二分查找结束后，left = 0，且 nums[left] != target，可以与上一种情况合并
因此，最终算法为：
3.3 问题探讨
3.2 的思路，能否借鉴到经典写法里去？
不建议，思路不太顺，坑填不上就是 bug。
3.2 的思路，是基于左闭右开区间范围的，如果借鉴过去，在左右全闭的区间范围内，循环条件得写成while(left <= right)，我们第 2 章节也探讨了在经典写法里right = mid可能存在的 bug，所以right = mid - 1也不能改，只能当nums[mid] == target时，把收缩范围也改成right = mid - 1，但这时，收缩的范围中不能保证还有 target，这已经与 3.2 的思路不太一致了。不过可以继续填坑：
如果收缩范围中不包含 target，我们在几轮查询并跳出后，此时 left = right + 1，这时，如果 nums[left] == target，则 left 就是第一个，另外，对于 target 不在 nums 区间范围内的情况，也要单独处理一下
如果收缩范围中包含 target，则经过几轮循环后，无非 2 中情况：
2.1 收缩的范围中不包含 target，回归情况 1
2.2 收缩范围后，left = mid， right = mid - 1 < left，直接到达退出循环的条件，也回归到情况 1
由此，填坑后的代码如下，看上去与 3.2 的代码有点像，但逻辑却不完全一致，而且如果没有 3.2 打底，这个写法可能更难想清楚。
4. 找数组中重复数字 target 最后一个？
4.1 基于经典写法
与 3.1 思路完成一致，代码如下：
4.2 基于更巧妙的写法
继续沿用 3.2 的思路反过来就可以了。找 target 的最后一个，把顺着 mid 左移改成右移即可，对查找结果的处理也类似，不过处理细节上要绕一些，再单独说明一下：
要注意跳出循环时，left = right = mid + 1 了，所以结果要返回 target 索引为 left - 1
target 比 nums 第一个元素还小，则跳出循环时，left == 0，target 的实际索引
left - 1超出左界target 比 nums 最后一个元素还大时，跳出循环时，left = right = nums.length，nums[left - 1] != target
target 在 nums 的区间范围内且 target 不在 nums 中时，跳出循环时，nums[left - 1] != target
最后，算法代码如下：
4.3 问题探讨
4.2 的思路，能否借鉴到经典写法里去？
也不建议，硬写的话，思路可以参考 3.3 章节，代码略。
5. 总结与扩展
5.1 总结
以上内容写了很多细节，为便于理解和记忆，总结如下：
1. 二分查找的数据区间范围有左右全闭和左闭右开两种，其范围和循环条件如下，不能混搭：
(1)左右全闭，[0, nums.length - 1], while(left <= right)
(2)左闭右开，[0, nums.length], while(left < right)
2. 对于右边界的收缩，对于左闭右开，必须 right = mid，对于左右全闭，建议 right = mid - 1，这不仅是在逻辑上保持一致，而且是避免不必要的 bug
3. 对于左边界的扩张，同样的，需要写 left = mid + 1
4. 对于最简单的二分查找，由于 nums[mid] == target 时就退出了，最简单最不易写错，而其他复杂情况，都会执行到只剩 left、right 两个元素后，再做最后一次 mid 的计算、判断才结束，这里是容易出错的地方
5. mid 的取值是偏向 left 一侧的，一轮循环结束后，由于 left = mid + 1，所以左右全闭，退出循环时，left = right + 1，左闭右开时，left = right，找最后一个等于 target 的元素时，由于 nums[mid] = target，所以这里要返回 left - 1，即 mid，这个也是容易出错的地方
6. 搞清楚了二分查找的特点和容易出错的地方，两种写法是可以相互借鉴的
5.2 扩展
二分查找还有两类常见的查询需求，在搞明白两种写法的基础上，也都可以写出经典、巧妙和混搭三种写法了。本文不在提供全部写法，大家可以自己练练手。
5.2.1 查找第一个大于等于 target 的元素
（1）经典写法
(2) 巧妙写法
5.2.2 查找最后一个小于等于 target 的元素
（1）经典写法
(2)巧妙写法
6. 算法题
后续补充
7. 参考资料
本文主要借鉴了以下内容，部分代码也源自于此：
极客时间，王争老师的《数据结构与算法之美》专栏，可以扫下面的二维码购买阅读
版权声明: 本文为 InfoQ 作者【gevin】的原创文章。
原文链接:【http://xie.infoq.cn/article/51bfbfda0b1ef43f36d2c6de5】。文章转载请联系作者。
还未添加个人签名 2013.07.26 加入
还未添加个人简介
评论