代码随想录.力扣.数组.二分查找.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]

代码：

# C++
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int rightBorder = getRightBorder(nums, target);
        int leftBorder = getLeftBorder(nums, target);
        # 1
        if(leftBorder == -2 || rightBorder == -2){
            return {-1, -1};
        }
        # 2
        if(rightBorder - leftBorder > 1){
            return {leftBorder + 1, rightBorder - 1};
        }
        # 3
        return {-1, -1};
    }
 
private:
    int getRightBorder(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
 
    int getLeftBorder(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] >= target){
                right = mid - 1;
                leftBorder = right;        
            }else{
                left = mid + 1;
            }
        }
        return leftBorder;
    }
};

关键思路：

1. 首先可以考虑，解决这个问题就是找到重复元素的左右边界位置。按照二分法的思路，当nums[mid]=target时，左边右边可能依然会有target相同数值元素，求左边界的时候，就把right指针向左移动，right=mid-1，并同时用rightBorder标记right的位置，作为暂时的左边界，因而nums[mid]>target和nums[mid]=target时的结果都是左移right，找到左边界后，此时right，也就是rightBorder在边界元素的左边一个位置，因而return的rightBorder + 1才是边界的位置。同理，右边界也是如此。
2. 求得左右边界之后，按照严谨的思路来说，需要考虑所有不同的情况：
   1. target不存在于数组中，对于数组来说是最小或最大值，求左右边界的时候，rightBorder或leftBorder一直向右或向左以动，在if条件下，是不会被赋值的，其中一个会为-2。这个条件必须先判断，不然第二个条件无法完全成立。
   2. target存在于数组中，此时rightBorder-leftBorder>1。
   3. 而target不存在于数组中，但在区间内，这种情况下，rightBorder-leftBorder=0。
3. 这里还需要注意，左右边界的函数中，if else的顺序不太一样，经过实验，对速度有些影响，最好是把多条语句的放在上面，else后面尽量简单？