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

方法1：二分查找

返回数组中第一个大于等于target的位置，Solution类中的tar方法

注：传统的二分查找中，要求：

• 数组为有序数组

• 数组无重复元素

该题不满足第二条，无法直接使用二分

class Solution {
public:
    
    //返回数组中第一个大于等于target的位置,如果所有数都小于target，返回长度
    //left左边的数都小于target
    //right右边的数都大于等于target
    //最后一次循环，left等于right的时候（mid=left=right）
    //不管left+1（mid所指小于target）还是right-1（mid所值大于等于target），left始终指向第一个大于等于target位置
    int tar(vector<int>& nums, int target){
        int left = 0,right = nums.size()-1;
        while(left<=right){//一定是小于等于
            int mid = (left + right)/2;
            if(nums[mid] < target) left = mid+1;//一定是+1
            else right = mid-1;//一定是-1
        }
        return left;  //right + 1也可以
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int start = tar(nums,target);
        if(start == nums.size() || nums[start] != target) return{-1,-1};
        int end = tar(nums,target+1) - 1;
        return{start,end};
    }
};