二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，可以在数据规模的对数时间复杂度内完成查找。

写二分查找中最复杂的地方莫过于细节部分，包括是采用小于号还是小于等于号，是否需要+1或者-1等等。为方便起见，建议直接参考博主labuladong的博客我写了首诗，把二分搜索算法变成了默写题，采用左闭右闭的写法，所有+1和-1都需要。同时作者还提供了查找左边界和右边界的写法（左边界指连续一串数等于target，则返回最左边的索引）。强烈建议阅读。

当然，除了手撸二分查找的写法，我们还可以直接调用C++的库函数实现。参考CSDN博主「brandong」博客

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

因此，通常我们可以使用如下写法

1
2
3
int pos = lower_bound(nums.begin(),nums.end(),target)-nums.begin();
if(pos==nums.size()||nums[pos]!=target)return -1;//找不到target数字
else return pos;

因此lower_bound同样可以用来得到target的左边界，而upper_bound可以用来得到target的右边界

1
2
int left_bound=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
int right_bound=upper_bound(nums.begin(),nums.end(),target)-nums.begin()-1;

以下列举部分经典二分查找的题目

  1. 74. Search a 2D Matrix

img

直观地想，二分查找会先搜索哪一行，再搜索哪一列，但是有一种简单的做法是直接把pos在[0,m*n-1]上进行二分查找。具体定位到矩阵里的位置时采用matrix[mid/n][mid%n]的写法。

参考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(),n=matrix[0].size();
        int left=0,right=m*n-1;
        while(left<=right){
            int mid =left+(right-left)/2;
            int x = matrix[mid/n][mid%n];
            if(x<target)left=mid+1;
            else if(x>target)right=mid-1;
            else if(x==target)return true;
        }
        return false;
    }
};
  1. 33. Search in Rotated Sorted Array
1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target)return mid;
            if(nums[left]==target)return left;//此处建议直接把所有相等的地方都考虑进去，防止后续出现遗漏的情况
            if(nums[right]==target)return right;

            if(nums[left]<nums[mid]){
                if(target>nums[left]&&target<nums[mid])right=mid-1;
                else left=mid+1;
            }
            else{
                if(target>nums[mid]&&target<nums[right])left=mid+1;
                else right=mid-1;
            }
        }
        return -1;
    }
};
  1. 153. Find Minimum in Rotated Sorted Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        int ans=INT_MAX;
        if(nums[left]<nums[right])return nums[left];
        while(left<=right){
            int mid=left+(right-left)/2;
            ans=min(ans,nums[mid]);
            if(nums[left]<=nums[mid]){
                if(nums[mid]>=nums[right])left=mid+1;//1⃣️
                else right=mid-1;
            }
            else{
                right=mid-1;
            }
        }
        return ans;
    }
};

此题需要注意的是在算完mid之后，left..mid..right有可能重新成为正序排列，因此需要加入判断1⃣️处的判断语句