給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標值 target。找出給定目標值在數(shù)組中的開始位置和結束位置。
你的算法時間復雜度必須是 O(log n) 級別。
如果數(shù)組中不存在目標值，返回 [-1, -1]。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]

解

要求時間復雜度為O(log n)，提示使用二分查找。所以使用二分查找先查找出數(shù)組中有沒有目標元素，如果有則使用flag記錄元素的位置，然后從flag向左向右遍歷，找到目標元素的起始位置的結束位置。注意在使用二分查找是i+1==j需要break掉。

public static int[] searchRange(int[] nums, int target) {
        int res[] = new int[] {-1,-1};
        int len = nums.length;
        if(0==len||target<nums[0]||target>nums[len-1])
            return res;
        if(1==len&&target==nums[0])
            return new int[] {0,0};
        
        int i = 0, j = len,flag = -1;
        while(i<j) {
            int mid = (i+j)/2;
            if(target==nums[mid]) {
                flag=mid;
                break;
            }
            if(i+1==j)
                break;
            if(target>nums[mid])
                i = mid;
            else 
                j = mid;
        }
        if(-1==flag)
            return res;
        int left = flag,right=flag;
        
        while(left>=0&&nums[left]==target)
            left--;
        while(right<len&&nums[right]==target)
            right++;

        res[0]=left+1;
        res[1]=right-1;
        return res;
    }