class Solution {
    private int[] answer;
    private int[] nums;
    private int target;
    public int[] searchRange(int[] nums, int target) {
        this.answer =new int[] {-1,-1};
        if(nums == null || nums.length == 0) return answer;
        if(nums.length == 1){
            if(nums[0] == target) return new int[] {0,0};
            return answer;
        }
        this.nums = nums;
        this.target = target;
        int lower = findLower(0, nums.length);
        if(lower == -1) return answer;
        findUpper(lower, nums.length);
        return answer;
    }

    private int findLower(int start, int end){
        while(start < end){
            int middle = start + (end - start)/2;
            if(nums[middle] > target || nums[middle] == target){
                end = middle;
            }else{
              start = middle + 1;
            }
        }

        if(start == nums.length || nums[start] != target){
            answer[0] = -1;
            return answer[0];
        }
        answer[0] = start;
        return start;
    }

    private void findUpper(int start, int end){
        while(start < end){
            int middle = start + (end - start)/2;
            if(nums[middle] > target){
                end = middle;
            }else{
              start = middle + 1;
            }
        }
        answer[1] = start -1;
    }
}