今天发文是今天在「力扣」看到一篇帖子:
这是 事件 1;
left = mid
,什么时候写 left = mid + 1
,帖子找不到了,当时很懒就没有回答;看来就「二分查找」我还是没有解释清楚的地方。我在今天的「二分查找不同实现方法细节困惑」这篇帖子里已经做了回复。
在这里就和大家再简单罗列一下我想和大家讲清楚的「二分查找」的各种话题。
二分查找最简单的样子是:在一个有序(升序) 整数 数组中查找一个 整数。这道题是「力扣」第 704 题,思路是:找到一个位于搜索区间中间位置的一个元素 nums[mid]
:
nums[mid]
恰好等于 target
,我们就可以说找到了目标元素;nums[mid] < target
,由于数组是升序的,target
如果在数组里存在,只能在 mid
的左边,因此下一轮在区间 nums[left..mid - 1]
里继续查找,此时设置 right = mid - 1
;nums[mid] > target
,由于数组是升序的,target
如果在数组里存在,只能在 mid
的右边,因此下一轮在区间 nums[mid + 1..right]
里继续查找,此时设置 left = mid + 1
。代码如下:
public class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
// 在区间 nums[left..right] 里查找目标元素
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 下一轮在区间 nums[mid + 1..right] 里搜索
left = mid + 1;
} else {
// 这种情况下,nums[mid] > target
// 下一轮在区间 nums[left..mid - 1] 里搜索
right = mid - 1;
}
}
return -1;
}
}
为什么说这是「二分查找」最简单的样子呢?因为:
这种写法就是我们都熟知的《幸运 52》猜价格游戏:
如此往复下去,有限次猜测一定会猜中。
但实际上,我们还遇到过各种各样的问题。题目给出的 条件 变成:数组里有重复元素,要我们找的 答案 变成:
target
的位置(「力扣」第 34 题);target
的位置(「力扣」第 34 题);target
的第 1 个位置(「力扣」第 35 题、第 300 题);等等等等。这些问题有一个共同的特点:
如果当前猜的那个数
nums[mid]
符合某个性质,我们还不能确定它一定就是我们要找的元素,必须向左边(或者向右边)继续看下去,才能确定nums[mid]
是不是我们要找的元素。
例如:找有序整数数组里第 1 个等于 target
的位置(「力扣」第 34 题)。
一种常见的做法是:看到
以后,继续向左边「线性查找」,此时时间复杂度变成
,这里
是数组的长度。
实际上正确的做法是:在左边查找的时候 继续使用二分查找。
这里代码大家可以做一下「力扣」第 34 题,我们今天主要解释大家看到的几种写法的差别。
我知道二分查找常见有 3 种写法,是在「力扣」的「学习」板块的「LeetBook」里,有一本叫「二分查找」的 LeetBook。
如果你使用英文版的 LeetCode,「学习」版块叫「explore」。
我简单解释一下大家常见的三个模板,它们区分的标志是 while
里面写什么。
while (left <= right)
while (left < right)
while (left + 1 < right)
while (left <= right)
看到 while (left <= right)
这种写法的朋友们,你一定会看到「大佬」们这么用:声明一个 ans
变量,一定会出现在 if
和 else
分支里的其中一个。
以下是「力扣」第 35 题官方题解:
target
的元素的位置,当看到一个元素 nums[mid]
大于等于 target
的时候,nums[mid]
有可能就是我们要找的,所以把 ans
先保存为 mid
;n
,也就是数组的最后一个元素的下一个位置也有可能是答案,所以一开始的时候设置 ans = n
;if
和 else
里面,不管怎么样,left
和 right
的设置都需要 + 1 或者 -1。设置 left = mid + 1
,说明下一轮向右边找,设置 right = mid - 1
,说明下一轮向左边找。这是因为:mid
如果有可能是解的话,因为有了 ans
的设置,一定不会丢失最优解;left == right
重合的时候,left
位置的值还没有看到,所以要继续找下去,因此循环可以继续的条件是 while (left <= right)
;ans
哦,不是 left
或者 right
的任何一个。大家可以在回头看看本文第 2 大点,我复制下来,重要的事情讲 3 遍。
如果当前猜的那个数
nums[mid]
符合某个性质,我们还不能确定它一定就是我们要找的元素,必须向左边(或者向右边)继续看下去,才能确定nums[mid]
是不是我们要找的元素。
这种写法也叫带 ans
的「二分查找」,「力扣」的巨佬:零神(id:zerotrac)以前就经常用这种写法,现在我不刷题了,所以不知道他是不是还这样写。
while (left < right)
如果你看过我在第 35 题写的题解,就会知道我一直在用这种写法,所以我这里就不展开了。简单说一下:
while (left < right)
这种写法,我最喜欢的地方是退出循环以后 left
与 right
重合;叫「两边夹」是因为这个写法是:两个变量 left
和 right
向中间走,相遇的时候停下。相遇的时候是 left == right
,所以循环可以继续的条件是 while (left < right)
。
叫「排除法」是每一轮都把一定不是目标元素的值排除掉,下一轮只在有可能存在目标元素的区间里查找。
left = mid
的时候,取中间数需要加 。原因在于:整数除法是下取整,取 mid
的时候不能做到真正取到中间位置,例如 left = 3, right = 4
, mid = (left + right) / 2 = 3
,此时 mid
的值等于 left
,一旦进入 left = mid
这个分支,搜索区间不能缩小,因此会进入死循环。
这是很多朋友和我说最难理解的地方,我有两个办法:
left
、right
、mid
的值打印出来看一下,例如「力扣」第 69 题。public class Solution {
public int mySqrt(int x) {
// 特殊值判断
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
int left = 1;
int right = x / 2;
// 在区间 [left..right] 查找目标元素
while (left < right) {
// 取中间数 mid 下取整时
int mid = left + (right - left ) / 2;
// 调试语句开始
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("left = " + left + ", right = " + right + ", mid = " + mid);
// 调试语句结束
// 注意:这里为了避免乘法溢出,改用除法
if (mid > x / mid) {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
} else {
// 下一轮搜索区间是 [mid..right]
left = mid;
}
}
return left;
}
public static void main(String[] args) {
Solution solution = new Solution();
int x = 9;
int res = solution.mySqrt(x);
System.out.println(res);
}
}
这里有个小技巧,一般我会在注释里写上「下一轮搜索区间是什么」。如果下一轮搜索区间是
[mid..right]
,这个时候就设置left = mid
,这种情况的反面区间就是[left..mid - 1]
,那么else
就设置right = mid - 1
。区间[mid..right]
和[left..mid - 1]
组成了原来的整个区间[left..right]
不用记忆配对关系了。
「力扣」上很多大佬用的都是这种写法,例如宫水三叶(id:ac_oier),张晴川(id:qingczha)。
这种写法需要注意的地方:
mid
的时候一定要清楚两件事情:mid
是不是解;所以就会有「left = mid
与 right = mid - 1
」与「left = mid + 1
与 right = mid
」这两种区间设置,其实就是一个包含 mid
一个不包含 mid
的区别而已。
分成两个区间,如果分成三个区间,不一定退出循环以后 left
与 right
会重合。
怎么知道 mid
是不是解,下一轮向左边找,还是向右边找,答案是:看题目,重要的事情说三遍,看题目、看题目、看题目。
所以这里还有一个小技巧:分析清楚题目要找的元素需要符合什么性质。
if
写不符合这个性质,把 mid
排除掉;else
就恰好是这个性质。原因很简单:不符合性质的时候,把 mid
排除掉的逻辑不容易出错(这是个人感觉,评论区有和我一样有同感的朋友)。但是这一点不绝对,我做过的题目只有「力扣」第 287 题例外。
例如「力扣」第 35 题:题目要我们找:第一个大于等于 target
的元素的位置。
所以如果看到的元素 nums[mid]
的值 严格小于 target
,mid
肯定不是我们要找的,下一轮应该在右边继续查找,所以下一轮搜索区间是 [mid + 1..right]
,设置 left = mid = 1
,下面的代码 if
就是这么写出来的。
public class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
// 下一轮搜索区间是 [mid + 1..right]
left = mid + 1;
} else {
// 下一轮搜索区间是 [left..mid]
right = mid;
}
}
return left;
}
}
其它细节,由于篇幅的原因就不解释了。大家题目做多了,都能理解到。
while (left + 1 < right)
下面这段代码是我从 LeetBook 里面截图,把需要注意的地方加上了注释。
这种写法的提出者我也不知道是谁,我看蛮多人爱用这种写法的。设计这种写法的想法(好处)和不好的地方,我为大家罗列一下。
mid
是不是保留,把 left
和 right
的设置都写成:left = mid
和 right = mid
。表示的意思是都保留了 mid
位置的值,但是不能省去的判断是「下一轮向左走还是向右走」;while (left + 1 < right)
,但是不能省去的判断是「退出循环以后」,一定要再判断一下 left
和 right
哪一个才是题目要找的解,这一步有可能会增加一些本来不必要的逻辑(例如「力扣」第 34 题)。我不固定用哪一种写法,看问题:
while (lefy <= right)
,并且不设置 ans
,因为循环体内就可以返回,没有必要设置 ans
;while (lefy < right)
,因为只要仔细的判断,完全可以清楚 mid
是否排除和下一轮向左边走还是向右边走。出现死循环的原因和解决办法我已经完全理解。我写的题解绝大多数都是这种写法,因为「力扣」上的问题绝大多数都是下面这类问题:(重要的事情说三遍,这是本文第三次出现了)
如果当前猜的那个数
nums[mid]
符合某个性质,我们还不能确定它一定就是我们要找的元素,必须向左边(或者向右边)继续看下去,才能确定nums[mid]
是不是我们要找的元素。
因此其实重点在 if
和 else
怎么写,再强调一下这个小技巧:分析清楚题目要找的元素需要符合什么性质。
if
写不符合这个性质,把 mid
排除掉;else
就恰好是这个性质。「二分查找」的确是有很多需要细心的地方,但它不是完全不能掌握的,大家需要有一些耐心,题目做得多了,慢慢就理解了。
我短期之内不会频繁更新公众号了,很感谢大家的关注和支持。
我写这个公众号的原因是:以前我是干这个的,写写题解,录题解视频,写公众号补充了一种知识分享的形式。
我已经写了我认为足够多的题解,录制了我想录制的视频题解。如果以后有机会,有时间,或许我还会再写一些有意思的东西。
可能很多朋友做题是因为想要通过笔试、面试,等到有了好的工作机会以后,就不会再刷题了。
我以前写题解和录视频的原因很简单,就是记录下来,分享给大家。后来干这件事情成为了我的工作,我没有那么喜欢了。
很多看我题解的朋友们现在已经不需要刷题了,我为这些朋友感到高兴。在写题解、录视频、和大家交流的过程中,我得到了很多东西。除了金钱上的支持,还有各种肯定和鼓励,直到现在都有和我没事聊聊天的朋友,这已经足够了。
以后有想和大家分享的,我还会继续写下去。没有的话,就不写了。
再次感谢大家。