Search for a Range

Given a sorted array of n integers, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

Have you met this question in a real interview? 

Yes

Example

Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Challenge

O(log n) time.

public class Solution {
    /**
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    public ArrayList<Integer> searchRange(ArrayList<Integer> A, int target) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(-1);
        res.add(-1);
        if(A == null || A.size() == 0) return res;
        int low = binarySearch(A, target - 0.5);
        if(low >= A.size() || A.get(low) != target) return res;
        int high = binarySearch(A, target + 0.5);
       
        res.set(0, low);
        res.set(1, high-1);
        return res;
    }
   
    private int binarySearch(ArrayList<Integer> A, double target){
        int start = 0, end = A.size() - 1;
       
        while(start <= end){
            int mid = (start + end) / 2;
            if(A.get(mid) == target) return mid;
            if(A.get(mid) < target){
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start;
    }
}