力扣.34以及二分法两种方法的区别

力扣34题解及思路

力扣链接

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回?[-1, -1]。

进阶：你可以设计并实现时间复杂度为?$O(\log n)$?的算法解决此问题吗？

示例 1：

• 输入：nums = [5,7,7,8,8,10], target = 8
• 输出：[3,4]

示例?2：

• 输入：nums = [5,7,7,8,8,10], target = 6
• 输出：[-1,-1]

示例 3：

• 输入：nums = [], target = 0
• 输出：[-1,-1]

思路:分析题目,该数组为有序数组,我们可以采用二分查找划分左右边界,一共有以下三种情况

• 情况一:traget在数组范围的右边或者左边,例如nums[2,3,4],traget=1,或者traget=5;
• 情况二:traget在数组范围内,但不是数组里的数,见示例2.
• 情况三:traget在数组范围内,且是数组里的数,见示例1.

明白了三种情况之后,就需要开始去找左右边界了.

代码如下?

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};

二分查找

二分查找的前提是数组为有序数组,涉及较多的边界条件,逻辑较为简单,二分法主要有两种写法,

第一种写法

第一种写法是while(right>=left),我们称之为左闭右闭区间,if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

第二种写法

第二种写法是while(right>left),我们称之为左闭右开区间,if (nums[middle] > target) right 要赋值为 middle ，因为当前这个nums[middle]有可能是target，那么接下来要查找的左区间结束下标位置就是 middle .

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

总结

我也是一开始想不明白为什么左闭右开区间,right指向middle的下标,所以我写了这篇博客,后面我发现,在第二种方法下,如果right=middle,可能会错过target.这样只是我个人的看法,我在b站up代码随想录<力扣704讲解>中找到了答案

当nums[middle]>traget时,说明traget在数组的左区间(递增数组中),traget所在的左区间,是不包括右边界的(前面我们说查找区间是个左闭右开),而nums[middle]也不等于traget,所以right是可以等于middle的.

要注意的是因为两种方法固定区间的取值不同,所以导致right指针刚开始的位置也不同

• 方法一:right=nums.size()-1;
• 方法二:right=nums.size();