704.二分查找

Problem: 704. 二分查找

思路

题目明确指定使用二分法进行查找

解题方法

二分法有两种解法,其一是使用递归,其二是使用循环,这里为了避免多次压栈保护现场,使用循环的解法

这里为什么要使用while(left<=right),可以举一个例子:

如图所示: 这里第一次循环后,left == right,但是由于while(left<right)的条件而结束了,返回了-1,却没有对比到正确答案。

脑瘫的错误

• 没有考虑到越界 mid = left + ((right - left) /2);

• 有边界错误写成 right = nums.size()

• while循环条件写成 while(left<right),这样在输入 nums =[5] 这样单个数组中会报错

复杂度

• 时间复杂度:

$O(log(n))$

• 空间复杂度:

$O(1)$

Code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0,right = nums.size()-1,mid;
        while(left<=right){
            mid = left + ((right - left) /2);
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) left = mid+1;
            else right = mid -1;
        }
        return -1;
    }
};