二分查找常见套路与分析
注：
二分查找的思路很简单，但具体写起来，很容易在细节上搞错，本文目标是总结常见的二分查找写法细节的套路
为了标明二分法代码中每种情况的业务逻辑和可读性，大部分代码没有做逻辑合并和代码优化
本文默认nums数组是按升序排列的
随着对二分查找理解的深入，本文内容不定期更新，也会补充算法题来做练手
文中代码较多，建议电脑端阅读
1. 思路和代码框架
这就是所谓简单的部分，二分查找无非是对于一个排好序的数组，通过检查数组中间位置元素值与target的大小，缩小数组的长度范围，直到找到target，或达到循环退出条件后，做近一步判断并返回结果。
其代码框架如下：
public int binarySearch(int[] nums, int target) {
int left = ..., right = ...;
while(...) {
int mid = (left + right) / 2;
if(nums[mid] == target) {
...
} else if (nums[mid] > target) {
right = ...;
...
} else if (nums[mid] < target) {
left = ...;
...
}
}
}
二分查找容易出错的地方，是上述代码中省略号处应该怎么写才合适，比如到底是<=还是<，是left = mid 还是left = mid + 1，是right = mid还是right = mid - 1等，正确的写法是这几个语句恰当的组合，否则都没法通过全部用例测试。
本文将从最基本的在一个有序数组中找到target出发，说明几种常见的正确组合写法。
2. 如何在一个有序数组中找到target
2.1 经典写法
最经典的写法如下：
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return -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]后，继续往下执行代码的结果为：
mid = (left + right) / 2 = left,
nums[mid] = nums[left] < target,
left = mid = left
所以如果不是left = mid + 1的话，范围会定格在[left, right]两个元素上，且在循环到条件范围内，会一直死循环下去；
<2> 对于right = mid，可能会出现bug的情况为，如果target不在数组中，且target 在nums数组区间范围内，那么代码还是会执行到只剩left, right两个元素，此时nums[left] < target < nums[right]，这样还会有下一轮循环到执行，即：
left = mid + 1 = right,
mid = (left + right) / 2 = right,
nums[mid] = nums[right] > target,
right = mid = right
所以如果不是right = mid - 1，也会死循环下去(循环条件：while(left <= right))
2. 若循环退出条件写成 left < right，有什么问题？
如果条件为left < right，则当left = right时就退出了，这样就少查了一个元素，如果这个元素就是target的话，出bug了
另外，明白了这一点，其实循环退出条件写成left < right也没关系，此时漏掉的元素就是left（也是right），再加几行代码对这个元素单独处理就好了，如：
//...
while(left < right) {
// ...
}
return nums[left] == target ? left : -1;
3. 经典写法有什么局限？
如果数组中有重复元素，且target就是重复的元素，该写法找到的只是其中某个，如果我们需要明确找到第一个或最后一个的话，就搞不定了
2.2 更巧妙的写法
注：这里所谓“更巧妙”的写法，只是为了说明这是另一种思路，在本节的经典场景下，与经典写法本质区别不大
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length; // #1
while(left < right) { // #2
int mid = (left + right) / 2;
if(nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid; // #3
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return -1;
}
说明：
这段代码与上一节有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 即可。代码如下：
public int binarySearchFirst(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
if (mid == 0 || nums[mid - 1] < target) {
return mid;
} else {
right = mid - 1;
}
}
}
return -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，可以与上一种情况合并
因此，最终算法为：
public int binarySearchFirst(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 循环结束后，按照上面分析的left的情况，返回恰当结果
if (left == nums.length) {
return -1;
} else if (nums[left] != target) {
return -1;
} else {
return left;
}
// 把上面坏味道的代码写到一行中更好
// return left == nums.length ? -1 : (nums[left] == target ? left : -1 );
}
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打底，这个写法可能更难想清楚。
public int binarySearchFirst(int[] nums, int target) {
int left = 0, right = nums.length;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = left + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
right = mid - 1;
}
}
/*
if (left == nums.length) {
return -1;
} else if (nums[left] != target) {
return -1;
} else {
return left;
}
*/
return left == nums.length ? -1 : (nums[left] == target ? left : -1);
}
4. 找数组中重复数字target最后一个？
4.1 基于经典写法
与3.1 思路完成一致，代码如下：
public int binarySearchLast(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
if (mid == nums.length - 1 || nums[mid + 1] > target) {
return mid;
} else {
left = mid + 1;
}
}
}
return -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
最后，算法代码如下：
public int binarySearchLast(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left == 0 ? -1 : (nums[left - 1] == target ? left - 1 : -1);
}
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）经典写法
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (mid == 0 || nums[mid - 1] < target) {
return mid;
} else {
right = mid - 1;
}
}
return -1;
}
(2) 巧妙写法
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return right == nums.length ? -1 : (nums[right] == target ? right : -1);
}
5.2.2 查找最后一个小于等于target的元素
（1）经典写法
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (mid == nums.length - 1 || nums[mid + 1] > target) {
return mid;
} else {
left = mid + 1;
}
}
return -1;
}
(2)巧妙写法
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left == 0 ? -1 : (nums[left - 1] == target ? left - 1 : -1);
}
6. 算法题
后续补充，以后请到博客原文查阅
7. 参考资料
本文主要借鉴了以下内容，部分代码也源自于此：
详解二分查找算法（博客原文可见链接）
极客时间，王争老师的《数据结构与算法之美》专栏，可以扫下面的二维码购买阅读