Search for a Range.txt

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> ret(2, -1);
        if ((n == 0) || (target < A[0]) || (target > A[n-1]))
            return ret;
        ret[0] = findFirst(A, n, target);
        ret[1] = findLast(A, n, target);
        return ret;
    }
    int findFirst(int A[], int n, int target) {
        int l = 0, u = n - 1, mid;
        while (l <= u) {
            mid = (l+u)/2;
            if (target == A[mid]) {
                if ((mid == 0) || (A[mid-1] != A[mid]))
                    return mid;
                u = mid - 1;
            } else if (target < A[mid])
                u = mid - 1;
            else
                l = mid + 1;
        }
        return -1;
    }
    int findLast(int A[], int n, int target) {
        int l = 0, u = n - 1, mid;
        while (l <= u) {
            mid = (l+u)/2;
            if (target == A[mid]) {
                if ((mid == n - 1) || (A[mid+1] != A[mid]))
                    return mid;
                l = mid + 1;
            } else if (target < A[mid])
                u = mid - 1;
            else
                l = mid + 1;
        }
        return -1;
    }
};