// 1. 单调-> 二分
// 2. bound:【0~end-1】, 
// 3. check: MAX(x <= nums[i]) , MIN(x >= num[i])
// 4. 特判：
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target < nums[0] || nums[nums.length-1] < target) return new int[]{-1, -1};
        int l = 0, r = nums.length-1;
        int start;
        while (l < r){
            int mid = (l+r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid+1;
        }

        if (nums[l] != target) return new int[]{-1, -1};
        else start = l;

        l = 0;
        r= nums.length -1;
        while(l < r){
            int mid = (l+r+1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid -1;
        }
        return new int[]{start, l};
    }

}