专题: 二分搜索总结

作者 Lucyyang 日期 2020-03-29
专题: 二分搜索总结

二分算法主要容易在边界问题上出错,这次先对常见的二分写法进行总结,之后进行题目练习。

二分写法总结

lower_bound

在有序数组中找到第一个大于等于给定值的位置,先看代码:

//lower_bound
int L = 0;
int R = size; //注意,如果没找到的话,这里返回的是数组的end
while(L < R) {
int mid = L + (R-L)/2;
if(array[mid] >= V)
R = mid;
else L = mid+1;
}
return L;

下面做一一解释,R 从size处开始,是为了保证如果没有找到大于等于给定数的话能够返回数组的end。如果R是从size-1开始,如果对于给定的[1,2,3]想找到5的lower_bound,R = 2开始,L会一直加1直到L=R=2,这时返回的结果3明显没有大于等于5,因此R要从数组的末尾+1开始返回。

L < R表明,我们要找的区间是[L, R],当L=R时,循环停止在我们要找的数上。

判断条件中array[mid] >= V表示,当条件大于等于V时,数组mid右边的数一定是大于V的,数组mid左边的数(包含mid本身)才有可能是V的下边界,因此R = mid。注意R不等于mid-1是因为,在判断条件中,如果array[mid] = V,则R=mid可以正好取到。

对于else分支,既array[mid] < V,则mid左边的数都小于V,因此L=mid+1。

最后循环停止条件是L=R>=V,返回L和R中任意一个即可。

upper_bound

在有序数组找到第一个大于给定值的位置。

代码:

//upper_bound
int L = 0;
int R = size; //注意,如果没找到的话,这里返回的是数组的end
while(L < R) {
int mid = L + (R-L)/2;
if(array[mid] > V) //注意判断upper_bound的判断条件为>V
R = mid;
else L = mid+1;
}
return L;

upper_bound的写法和lower_bound基本相似,但由于upper_bound判断的是>V的数,因此相应的判断条件也为array[mid] > V,R=mid的原因是,此时的mid有可能是第一个大于V的数,因此应该取上。

二分搜索相关题目

下面就选取一些经典的题目进行辅助理解。

Find Minimum in Rotated Sorted Array

题目:LC153,找到旋转数组中最小的数,也可以认为是旋转点,注意数组也有可能没有旋转,既nums[0]是最小的。

方法:由于这道题没有重复数字,我们可以将问题转换为第一个比nums[0]小的数。如果数组并没有旋转,那么就无法找到比nums[0]小的数,r会停留在nums.size()。

代码:

class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0;
int r = nums.size();
while(l<r){
int mid = l + (r-l)/2;
printf("l=%d, r=%d, nums[%d]=%d\n",l,r,mid,nums[mid]);
if(nums[mid] < nums[0])
r = mid;
else l = mid+1;
}
if(r==nums.size()) r=0;
return nums[r];
}
};

Search in Rotated Sorted Array

题目:LC33,原数组为增序,经过一次旋转后,请在O(logN)的时间复杂度下求出给定的target的位置。

方法:采用二分数组的关键是针对有序数组,针对这道题,先参考求旋转点的方法,求出旋转点。在求得了旋转点后,可以将数组分为增序的两端,如果所求值大于等于nums[0],则必在左半段,否则就在右半段。可以根据这个选择有序数组并进行二分查找。注意最后要确认下target == nums[r]。如果在左半段但没有这个数时,r会停在左半段的end处,既旋转点上。

class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size();
if(nums.size() == 0)
return -1;
while(l<r){
int mid = l + (r-l)/2;
printf("l=%d, r=%d, nums[%d]=%d\n",l,r,mid,nums[mid]);
if(nums[mid] < nums[0])
r = mid;
else l = mid+1;
}
//判断在哪个区间
if(target >= nums[0]){
l = 0;
r = r;
}else{
l = r;
r = nums.size();
}
//在对应区间找target
while(l < r){
int mid = l + (r-l)/2;
if(nums[mid]>=target)
r = mid;
else l = mid+1;
}
//确认nums[r]是target,有可能停在旋转点上但不相等或者停在end处
if(r!=nums.size() && nums[r]==target)
return r;
else return -1;
}
};

方法二:在二分的时候判断mid和left的相对位置,可以先划分为两种情况:一种是mid和left都在左右区间,这时nums[mid] >= nums[left];一种是left在左区间,mid在右区间,nums[mid] < nums[left]。对于第一种情况,又可分为target在[left, mid)的区间和不在的两种情况。 如果在[left, mid)区间(之前已经排除了nums[mid] = target情况),则必有 nums[left] <= target < nums[mid],此时将right缩小到mid-1;如果不在[left, mid)区间,则必在(mid, right]区间,此时left = mid +1。 再讨论nums[mid] < nums[left]的情况,既mid在旋转点的右边,left在旋转点的左边。此时(mid, right]为增序区间,判断target是否在该区间,如果在则left=mid+1;否则right = mid-1。

class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() -1;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target) return mid;
else if(nums[mid] >= nums[left]) { //优先判断mid所在位置:第一种情况
if(target >= nums[left] && target < nums[mid])
right = mid -1;
else left = mid + 1;
} else if (nums[mid] < nums[left]) {
if(target <= nums[right] && target > nums[mid]) //注意取等于号
left = mid +1;
else right = mid -1;
}
}
return -1;
}
};