34 在排数组中查找元素第一个和最后一个位置

原题地址：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目描述

给定一个按照升序排列的整数数组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]

分析

看到题目要求O(log n)就可以想到要用二分法
一开始做的时候思路比较low，想到使用二分法找到目标值后对其左右两侧分别使用线性查找边界。
实际上题目是想让作题者使用特殊的二分查找，通过改变二分的判断条件 来对左右边界实现二分查找

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int right =nums.size()-1;
        int left=0,mid=0;
        int pos=0;//判断是否存在
        vector<int> ans(2,0);
        if(right==0)
        {
            if(target==nums[0])
                return ans;
            ans[0]=-1;
            ans[1]=-1;
            return ans;
        }

        while(right>=left)//二分判断条件一定注意是 >=
        {   mid=(right+left)/2;
            if(nums[mid]==target)
            {
                pos=1;
                break;
            }else if(nums[mid]>target)
            {
                right=mid-1;
            }else
            {
                left=mid+1;
            }     
        }
        if (pos==0)
        {
            ans[0]=-1;
            ans[1]=-1;
            return ans;
        }
        int n= mid;
        while(n>0 && nums[n-1]==target  )//向左
        {
            n=n-1;
        }
        ans[0]=n;
        n=mid;
        while(n<nums.size()-1 && nums[n+1]==target)//向右
        {
            n=n+1;
        }
        ans[1]=n;
        return ans;

    }
};

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left =getLeftBorder(nums,target);
        int right=getRightBorder(nums,target);
        if(left ==-2||right==-2)
            return {-1,-1};
        if (right-left>1)//判断左右边界是否正确
            return {left+1,right-1};
        return {-1,-1};



    }
    //二分查找右边界
    int getRightBorder(vector<int>&nums ,int target)
    {
      int left =0;
      int right =nums.size() -1;
      int rightBorder =-2;
      while(left<=right)
      {
          int mid= left +(right-left)/2;
          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(right>=left)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target)
            {
                left =mid+1;
            }
            else{ //找左侧的最右边边界即为 左边界 >=
                right=mid -1;
                leftBorder = right;
            }
        }
        return leftBorder;
    }
};