704 二分查找
二分查找适用条件:
- 升序
- 元素不重复
解题思路
二分查找的本质是对数组进行区间的划分,每次取当前区间的中点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)