public class Solution {
    public int[] searchRange(int[] A, int target) {
        if (A == null)
            return new int[]{-1, -1};
        int[] res = new int[2];
        res[0] = findLeft(A, target);
        res[1] = findRight(A, target);
        return res;
    }
    
    private int findLeft(int[] A, int target) {
        int lo = 0, hi = A.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target <= A[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return lo == A.length? -1: A[lo] == target? lo: -1;
    }
    
    private int findRight(int[] A, int target) {
        int lo = 0, hi = A.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target >= A[mid])
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        return hi == -1? -1: A[hi] == target? hi: -1;
    }
}