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

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

进阶：

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

示例 ：

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

有序数组中查找，必然二分法，这个题在于查找到数字后，由于可能有重复，需要把重复数起始位置都找到。

那么当找到数字后，那么用双指针从找到的位置左右扩散寻找相同值即可。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        if(nums.length==0){
            return new int[]{-1,-1};
        }

        int right = nums.length-1;
        int left = 0;

        while (left<=right){

            int mid = ((right-left)>>1)+left;

            if(target>nums[mid]){
                left = mid + 1;
            }else if(target<nums[mid]){
                right = mid - 1;
            }else {
                //找到值后，双指针从当前位置，向两边扩散寻找是否还有相同的数
                left = mid;
                right=mid;

                while (left>=0 && target==nums[left]){
                    left--;
                }

                while (right<nums.length && target==nums[right]){
                    right++;
                }
                //由于循环多计算了一次，需要调整一位
                return new int[]{left+1,right-1};
            }

        }

        return new int[]{-1,-1};
    }
}

时间复杂度：O(n)，最坏的情况下，数组所有数字都是target，那么需要遍历整个数组。

空间复杂度：O(1)