class Solution {
    // 时间复杂度O(log n)  空间复杂度O(1) 常量空间存放变量
    // 二分法
    // 寻找第一次target的位置，更新右边界
    // 最后一次target的位置，更新左边界
    public int[] searchRange(int[] nums, int target) {
        int firstPos = findBoundary(nums, target, true);
        if (firstPos == -1) {return new int[]{-1, -1};}
        int lastPos = findBoundary(nums, target, false);
        return  new int[]{firstPos, lastPos};
    }
    public int findBoundary(int[] nums, int target, boolean first) {
        int left = 0, right = nums.length - 1;
        int pos = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {   // nums[mid] == target
                pos = mid;
                if (first) {
                    right = mid - 1; // 寻找第一次出现target的位置，向左移动右边界
                } else {
                    left = mid + 1; // 寻找最后一次出现target的位置，向右移动左边界
                }
            }   
        }
        return pos;
    }
    
}