二分的思想很简单,但是代码的细节确很难理解,每次做算法遇到二分的变体,脑子里都是浆糊,当时理解了,后面又忘了,需要注意的细节太多太多了,网上有很多分析二分变体的博客,写的都很详细,但是总是阅后即忘。。。
今天碰巧又遇到了这类算法,痛定思痛,一定要解决这个问题。于是详细分析了下二分的思想,感觉豁然开朗,下面分享我认为最容易理解的解法:
想要写出正确的二分,必须明白以下几点:
Java
语言的除法结果,是直接截取整数的,比如(2+1)/2=1
,也就是说在二分中是偏向左边,需要明白这一点用来定位最后mid
到底在哪里。-
由于是二分查找,因此不一定需要明确的知道两边的收缩条件,可以通过排除法,只要能明确值一定不在这边,那么值就一定在另外一边。
-
注意两个数相加溢出的问题,有些时候可以参考
Arrays.binarySearch()
中对(left+right)/2
防止溢出的处理,使用(left+right)>>>1
表示,这样处理对于因为溢出而负的值,可以强制转换为正数。但是对于本就是负数的处理,却是存在陷阱的,比如-1>>>1
结果为Integer.MAX_VALUE
,已经不是除以2的效果了。所以最好使用right+(left-right)/2
代替 -
需要明白如果没有数组中确实不存在
target
, 那么最终mid,left,right
三个指标的位置应该在哪里。伪代码如下:
while(left<=right){ ... mid=(left+right)/2; }
可以看到 结束条件是
left>right
,mid=(left+right)/2
也就是说,对于数组
[2,3,4,6,7,8,9]
如果查找的是5,则最终left
会指向数组中最大小于5的数,也就是4,index
为2,right
会指向最小大于5的数,也就是6,index
为3,按照二分思想,此时mid
应该指向4
和5
的中间,也就是如果5存在,则5应该存在的位置,但是由于上面第一条mid
是偏向左边,因此mid
会指向4,index
为2。
明白上面的道理,就可以很好的运行二分以及各种二分变式。
标准二分
标准二分不用多说。
public int binarySearch(int[] nums,int target){
int left=0;
int right = nums.length-1;
int mid = right + (left - right)/2;
while(left<=right){
if(nums[mid]==target){
return mid;
}else if(nums[mid] < target){
left = mid +1;
}else{
right = mid -1;
}
}
return -1;
}
存在重复数据,查找第一次出现的坐标
标准二分虽然能查找到数据,但是有时候我们的需求是查找第一次出现的target
的位置,比如:
[1,2,2,2,3,3,4,5,6] target=2
,则返回index=1
。
如果通过标准二分查找,则在第二次折半的时候,就会直接返回,但是这并不是第一次出现的位置。
前面我们分析过,如果原数组中并不包含target
,则mid
会停留在左边比mid
小,右边比mid
大的偏左的位置。
如上图所示,基于这个特性,我们就可以解决上面的问题,虽然数字可能重复,但是只要我们即使查找到具体的值之后依然一直向左边收缩,最终指针的位置一定就会停留在目前最大的小于target
的位置。
如上图,我们查找target
为5,但是我们在查找到5之后,继续以5>target
处理,此时区间则会继续向左边收缩,最终指针就会停留在4的位置,此时我们返回mid+1
即可。
代码如下:
public int binarySearchFirst(int[] nums,int target){
int left=0;
int right = nums.length-1;
int mid = right + (left - right)/2;
while(left<=right){
//查找到具体的值,继续向左收缩
if(nums[mid]==target){
right=mid-1;
}else if(nums[mid] < target){
left = mid +1;
}else{
right = mid -1;
}
mid = right + (left - right)/2;
}
//此时mid指向了最大小于target的左边,但是需要注意如果target比数组中所有的元素都大,则mid=nums.length-1,则mid+1会越界
if(mid==nums.length-1){
return -1;
}
//再判断mid+1是否为target,如果不是,说明数组中不存在这个元素
return nums[mid+1]==target?mid+1:-1;
}
存在重复数据,查找最后一次出现的坐标
和上题有个对称的问题,就是如果存在重复的数据,则返回最后一次出现的坐标。比如:
[1,2,2,2,3,3,4,5,6] target=2
,则返回index=3
。
其实,只要明白了上面的原理,我想代码应该很快就能写出来。刚刚我们处理当查找到5之后,将5做大于target
处理,使得指针继续向左收缩,当需要查找最后一个出现的坐标时,就应该向6靠近,此时只需要将5做小于target
处理,使得指针向右变收缩即可。
也就是当nums[mid]==target
时,做和nums[mid]<target
相同的处理。同时需要注意,由于mid
依然是靠左的,因此如果存在目标值,则它一定在6
的左边,可能直接指向目标值5
,也有可能指向4
(5不存在的时候就会指向4)。
代码如下:
public int binarySearchLast(int[] nums,int target){
int left=0;
int right = nums.length-1;
int mid = right + (left - right)/2;
while(left<=right){
//查找到具体的值,继续向右边收缩
if(nums[mid]==target){
left = mid +1;
}else if(nums[mid] < target){
left = mid +1;
}else{
right = mid -1;
}
mid = right + (left - right)/2;
}
//此时mid指向了最小大于target的左边,但是需要注意如果target比数组中所有的元素都小,则mid=-1,则nums[mid]会越界
if(mid==-1){
return -1;
}
//再判断mid是否为target,如果不是,说明数组中不存在这个元素
return nums[mid]==target?mid:-1;
}
部分有序的二分查找
LeetCode
上有个题,讲的是旋转数组的查找,一个原本有序的数组,经过旋转后,形成了一个新的数组,需要在这个数组上查找是否存在某个值。
比如:[4,5,6,7,1,2,3]
或 [8,1,2,3,4,5,6,7]
其实只要记得最开始所说的二分注意事项第二点,即可解答这个问题:
由于是二分查找,因此不一定需要明确的知道两边的收缩条件,可以通过排除法,只要能明确值一定不在这边,那么值就一定在另外一边。
仔细观察上面的数组可以发现,nums[mid]
的左边或右边一定是有序的,只要判断出哪边是有序的,即可通过排查法找到target
是否在有序的哪边,如果没在,那就一定是在另外一边,二分即可完成,无非是要多一些细节的处理而已。
总结
二分还有很多变体,但是万变不离其宗。一定需要理解如果二分一直运行到whlie
条件结束的时候,三个关键位置的坐标在哪里,通过这三个坐标的特性,就能解决大部分问题。