二分查找及其扩展专题
题目
- 排序数组中查找数字是否存在
- 排序数组中查找某数左右边界
- 排序数组中查找某数出现的次数
- 局部极小值问题
- 旋转排序数组中最小值
二分查找的坑
真尼玛!!!思路很简单，细节是魔鬼
- 写代码的时候,要定好你的搜索区间, [L,R] 还是 [L,R),不同情况的细节也不一样
R = array.size() / R = arr.size()-1 ;while(L < R) / while(L <= R)R = mid; / R= mid +1;
| [L,R] | [L,R) |
|---|---|
R = array.size(); |
R = arr.size()-1 ; |
while(L < R) |
while(L <= R) |
R = mid; |
R= mid +1; |
题目1 二分查找
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size();
while ( l <r )
{
int mid = l + ((r-l)>>1) ;
if (nums[mid] == target )
return mid;
if (nums[mid] > target)
{
r = mid ;
}else if (nums[mid] < target)
{
l = mid + 1;
}
}
return -1;
}
};
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size()-1;
while ( l <=r )
{
int mid = l + ((r-l)>>1) ;
if (nums[mid] == target )
return mid;
if (nums[mid] > target)
{
r = mid - 1 ;
}else if ( nums[mid] < target )
{
l = mid + 1;
}
}
return -1;
}
};
题目2 在有序数组中查找target的左右边界/求target的数量
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = find_left(nums,target);
int r = find_right(nums,target);
if ( l < 0 || r < 0 || l > r )
return 0;
return r - l +1 ;
}
// 找到target的左边界[L,R]
int find_left(vector<int>& nums ,int target)
{
if(nums.size()==0)
return -1 ;
int ans = -1 ;
int L = 0 ;
// 注意1
int R = nums.size();
// 注意2
while( L < R )
{
int mid = L + (( R - L ) >>1);
if( nums[mid] >= target )
{
// 注意3
R = mid;
ans = mid;
}else{
L = mid + 1;
}
}
return ans;
}
// 找到target的右边界
int find_right(vector<int>& nums , int target)
{
if(nums.size() == 0 )
return -1;
int L = 0;
int R = nums.size() ;
int ans = -1;
while (L < R)
{
int mid = L+ ( (R - L) >> 1) ;
if ( nums[mid] <= target )
{
L = mid + 1 ;
ans = mid;
}else{
R = mid ;
}
}
return ans;
}
// 找到target的左边界
int find_left2(vector<int>& nums ,int target)
{
if(nums.size()==0)
return -1 ;
int ans = -1 ;
int L = 0 ;
int R = nums.size()-1;
while( L <= R )
{
int mid = L + (( R - L ) >>1);
if( nums[mid] >= target )
{
R = mid -1 ;
ans = mid;
}else{
L = mid + 1;
}
}
return ans;
}
// 找到target的右边界
int find_right2(vector<int>& nums , int target)
{
if(nums.size() == 0 )
return -1;
int L = 0;
int R = nums.size()-1 ;
int ans = -1;
while (L <= R)
{
int mid = L+ ( (R - L) >> 1) ;
if ( nums[mid] <= target )
{
L = mid + 1 ;
ans = mid;
}else{
R = mid -1 ;
}
}
return ans;
}
};
};
题目3 旋转数组的最小值(二分法的扩展)
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素 。
例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1
class Solution {
public:
int minArray(vector<int>& numbers) {
// 原数组为空的情况
if( numbers.empty() )
{
return -1;
}
// 原数组只有一个元素的情况
if (numbers.size() == 1)
{
return numbers[0];
}
int l = 0 ;
int r = numbers.size()-1;
int mid = 0;
// 原数组没有旋转的情况
if ( numbers[l] < numbers[r] )
{
return numbers[l];
}
// 一般情况
// l 和 r 分别在大数区域和小数区域
// 小数区域的最大值是numbers[r]
// 中位数比这个数大,就是在大于区域,中位数比这个数小,就是在小于区域
// 中位数等于numbers[r] , 是没办法判断的. 就把 r 往前移动一位
// 当l移动到大数区的最右边,r移动到小数区的最左边,返回numbers[r]就可以了
while ( r > l+1 )
{
mid = l + ((r-l)>>1) ;
// 根据三种情况 判断最小值的区域
if ( numbers[mid] == numbers[r]){
r--;
}else if (numbers[mid] > numbers[r] ){
l = mid;
}else if (numbers[mid] < numbers[r]){
r = mid;
}
}
return numbers[r];
}
};