leetcode-34.在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回[-1, -1]。

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

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

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

class Solution 
{
public:
    vector searchRange(vector& nums, int target) 
    {   //情况一必须在情况三上面,因为若rb和lb其中一个是-2的话,就说明是情况一了
        //若情况三在情况一上面,rb-lb有可能大于一,则输出错误
        int leftBorder=getLeftBorder(nums,target);
        int rightBorder=getRightBorder(nums,target);
        //情况一
         if (rightBorder==-2||leftBorder==-2)
        return {-1,-1};
        //情况三
       
        if(rightBorder-leftBorder>1)
        return {leftBorder+1,rightBorder-1};
       //情况二
        return {-1,-1};
    }
private:
    //这道题的关键是找到target之后仍然不停止更新l r
    //而是找到target左边或右边的一个边界
    int getLeftBorder(vector& nums, int target)
    {
        int l=0,r=nums.size()-1,mid,lb=-2;        //lb来记录左边界下标
        while(l<=r)
        {   mid=l+(r-l)/2;
            if(nums[mid]>=target)                //如果mid处值大于"等于"target
            {                                   //等于的时候,因为我们要找的是左边界
                r=mid-1;                        //所以这时候不用管mid的右边,继续更新r为mid-1
                lb=r;                           //r=更新后的r,r肯定为左边界
         //因为只要大于等于就会让r-1,所以lb永远在大于等于target的值的左边一个
                                            
            }                                                               
            else                                //mid值小于target时,直接更新l
            {                                   //寻找等于的那个地方就行了
                l=mid+1;
            }
        }
        return lb;
    }
    //寻找右边界同理
    int getRightBorder(vector& nums,int target)
    {
        int l=0,r=nums.size()-1,mid,rb=-2;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(nums[mid]<=target)
            {
               l=mid+1;
                rb=l;
            }
            else
            {
               
                 r=mid-1;
            }
        
        }
        return rb;
    }
};

情况一必须在情况三上面,因为若rb和lb其中一个是-2的话,就说明是情况一了
若情况三在情况一上面,rb-lb有可能大于一,则输出错误
我第一次就是顺序放错了,然后一个用例就GG了:

注意

1.二分查找

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n) 的数组，二分查找的时间复杂度为 O(log n)。

寻找target在数组里的左右边界，有如下三种情况：
情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1} (只有左界或只有右界)(这也正是初始化为-2的原因下同)
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1} (左右界都有但都是初始化值)
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
再次强调顺序!