您现在的位置是:首页 >其他 >【LeetCode】704.二分查找网站首页其他

【LeetCode】704.二分查找

不 良 2024-06-13 18:01:02
简介【LeetCode】704.二分查找

704.二分查找

在这里插入图片描述

解析:

思路一:暴力解法,直接遍历,从头开始查找,如果找到直接返回下标,找不到返回-1。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] == target)
                return i;
        }
        return -1;
    }
};

思路二:二分查找;

使用二分查找的前提条件是:

1.数组为有序数组;

2.数组中无重复元素(一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的)。

二分查找中,最容易搞混的两点为:

1.while循环里面的条件应该是while(left < right)还是while(left <= right)

2.right再次赋值的时候应该是right = middle还是right = middle - 1

二分查找分析:

首先我们要对区间的定义进行明确,即确定这个区间是左闭右闭([left,right],区间包含leftright)还是左闭右开([left,right),区间包含left,但是不包含right),一般情况下都是这两种情况;然后针对不同区间的定义,进行边界条件的处理(即while循环条件)。

对于区间的定义不一样,是直接影响边界条件的处理的(即while循环条件)。

第一种情况:左闭右闭

当我们使用左闭右闭区间的时候,while(left <= right)是合法的,即leftright能够满足这个条件;

right再次赋值时我们已经判断middle不等于target了,要控制好边界条件,所以要让right = middle-1;当我们写成right = middle时,区间不明确,边界处理的不对,会出问题;left再次赋值时,也不能等于middle,更新右区间里的左边界。
在这里插入图片描述

左闭右闭代码如下:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int right = nums.size() - 1; //左闭右闭要包含right,所以right = nums.size() - 1
        int left = 0;
        while(left <= right) //合法情况
        {
            int middle = (left + right) / 2;
            if(nums[middle] > target)
                right = middle - 1;//更新左区间里的右边界
            else if(nums[middle] < target)
                left = middle + 1;//更新右区间里的左边界
            else
                return middle;
        }
        return -1;
    }
};

第二种情况:左闭右开

左闭右开区间,left不能和right相等,所以循环条件应该是while(left < right),根据区间的定义来查询,因为右开不包含right,所以right = middle,更新左区间里的右边界,left更新的时候仍然是left = middle + 1
在这里插入图片描述

左闭右开代码如下:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int right = nums.size();//左闭右开不包含right,所以right = nums.size()
        int left = 0;
        while(left < right) //不能加等于
        {
            int middle = (left + right) / 2;
            if(nums[middle] > target)
                right = middle;//更新左区间里的右边界
            else if(nums[middle] < target)
                left = middle + 1;//更新右区间里的左边界
            else
                return middle;
        }
        return -1;
    }
};

总结:

左闭右闭区间时,while的循环条件为left <= right,且right = middle -1

左闭右开区间时,while的循环条件为left < right,且right = middle

两个区间的left都是left = middle + 1

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。