跳转至

704 二分查找

leetcode链接

二分查找适用条件:

  • 升序
  • 元素不重复

解题思路

二分查找的本质是对数组进行区间的划分,每次取当前区间的中点mid,将nums[mid]与target进行比较:

  • 如果nums[mid] > target,收缩区间为左区间
  • 如果nums[mid] < target,收缩区间为右区间
  • 如果nums[mid] == target,那么mid就是我们要找的索引

如果重复上述步骤直至收缩区间为最小区间,仍然没有找到target对应的索引,那么说明数组没有该索引

区间的选取

区间可以选择左闭右闭区间或者左闭右开区间,注意循环过程中区间的选择是不变的

Tip

二分查找可以对应二分搜索树查找节点

左闭右闭区间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右闭区间
        // Step 1 : 确定初始区间
        int left = 0, right = nums.size() - 1;
        // Step 2 : 循环进行二分查找
        while(left <= right){
            // Step 3 : 找出区间中点
            int mid = (left + right) >> 1;
            // Step 4 : 区间中点与target进行判断
            if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }
};

左闭右开区间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        // 定义搜索范围为左闭右开
        // 初始搜索范围为[o,n)
        int l = 0, r = n;
        // 因为是左闭右开,所以l == r时[l,r)没有意义
        // 因此是l < r 不是l <= r
        while(l < r){
            // 二分搜索核:取中间索引
            int mid = l + r >> 1;
            // 如果target < nums[mid] 说明右边界r需要更新,更新为mid
            // 不是r == mid - 1,因为这是左闭右开区间,target一定不在mid上
            if(nums[mid] > target) r = mid;
            // 如果target > nums[mid] 说明左边界l需要更新,更新为mid + 1
            // l == mid + 1,因为左闭右开区间,target可能为在mid + 1
            else if(nums[mid] < target) l = mid + 1;
            // 如果target == nums[mid],mid为我们需要的索引,返回
            else    return mid;
        }
        return -1;
    }
};

复杂度分析

  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)