526互联

704二分查找

发布时间 2023-04-19 15:38:26作者: chuxin_jian

力扣刷题 704.二分查找--day1

解法

一、暴力解法

//暴力解法
int search(vector<int>& nums, int target) {
    for(int i = 0; i<nums.size(); i++){
        if(nums[i] == target)
            return i;
    }
    return -1;
}

二、二分查找

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

错误点:

  1. 二分查找中的截止条件判断错误
    where(left <= right) 中忘记相等的情况

小技巧：

  1. 计算 middle 时， 为了防止整数相加溢出
    可以将下列式子修改：
    int mid = (left + right) / 2;
    改为：
    int mid = left + (right - left)/2;