[LeetCode] Search for a Range

Problem Statement (link):

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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Analysis:
The search algorithm is same as that in the Search Insert Position problem.

- First we search if the target value exists in the array. If not, we return the [-1, -1] as required.
- Next we search for the lower and upper index bound of the given value in the array. A trick is to search for a value that is a bit smaller and a bit larger than the target value, as we are sure then the searching value doesn't exist in the array and will return us the exact index boundary of the given target value. Note that we need to -1 for the upper bound as we are not looking for the inserting position of the larger value.

The time complexity is O(log n). Precisely, we execute the binary search three times on the array.

Code:

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> index(2,-1);
        int found = recur(A, 0, n-1, n, (double)target);
        if (A[found]!=target) // if target doesn't exist in the array
            return index;

        index[0]=recur(A, 0, n-1, n, target-0.5);
        index[1]=recur(A, 0, n-1, n, target+0.5)-1; 
        return index;
    }

    int recur(int A[], int st, int ed, int n, double target) {
        if (st>ed) return st;

        int mid=(st+ed)/2;
        if (A[mid]<target)
            recur(A, mid+1, ed, n, target);
        else
            recur(A, st, mid-1, n, target);
    }
};