Search for a Range

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

Your algorithm's runtime complexity must be in the order of O(log n).

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

Example

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

 
class Solution {
private:
   int searchLeft(vector &A, int target) {
       int L = 0, R = A.size()-1;
       while(L <= R) {
           int m = L + (R-L)/2;
           if ( A[m] < target)
              L = m+1;
            else
              R = m-1;
       }
       
       if (L < A.size() && A[L] == target) return L;
       return -1;
   }

   int searchRight(vector &A, int target, int startIdx) {
       int L = startIdx, R = A.size()-1;
       while(L <= R) {
           int m = L + (R-L)/2;
           if ( A[m] > target)
              R = m - 1;
            else
              L = m + 1;
       }
       
       return R; 
   }
   
public:
   
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    vector searchRange(vector &A, int target) {
        vector output(2);
        int L = searchLeft(A, target);
        output[0] = output[1] = L;
        if (L != -1) 
            output[1] = searchRight(A, target, L);
        
        return output;
    }
};