LeetCode: 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].

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

---

The idea is the similar to binary search. One more thing to keep in mind is that we need to check the current index just found is left bound or right bound or neither of them.

C++ Code:

/*
 * func: search_range_helper
 * goal: binary search for the target
 * @param A: input integer array A
 * @param start: start index
 * @param end: end index
 * @param target: target value
 * return: the index of target
 */
int search_range_helper(int A[], int start, int end, int target){
    if(start > end){
        return -1;
    }
    int mid = start + (end-start) / 2;
    if(A[mid] == target){
        return mid;
    }else if(A[mid] > target){
        return search_range_helper(A, start, mid-1, target);
    }else{
        return search_range_helper(A, mid+1, end, target);
    }
    
}
/*
 * func: search_range
 * goal: find the starting and ending index of the target in
 *       a sorted array
 * @param A: input integer array A
 * @param n: the length of array A
 * @param target: target value
 * return: a vector containing the starting index and end index
 *         If there doesn't exist, return {-1, -1}
 */
vector<int> search_range(int A[], int n, int target){
    vector<int> result;
    assert(n > 0);
    int target_start = -1;
    int target_end = -1;
    //Use binary search to find the target's first appearence
    int first_found = search_range_helper(A, 0, n-1, target);
    if(first_found == -1){
        result = {target_start, target_end};
        return result;
    }else{
        //Find its left bound
        int left_index = first_found;
        target_start = left_index;
        while(left_index > 0 && A[left_index-1] == target){
            left_index = search_range_helper(A, 0, left_index-1, target);
            if(left_index != -1){
                target_start = left_index;
            }
        }
        
        //Find its right bound
        int right_index = first_found;
        target_end = right_index;
        while(right_index != -1 && right_index < n-1 && A[right_index + 1] == target){
            right_index = search_range_helper(A, right_index+1, n-1, target);
            if(right_index != -1){
                target_end = right_index;
            }
        }
        result = {target_start, target_end};
        return result;
    }
}

Python Code:

# func: find the starting and ending position of a given target value
# @param A: integer list
# @param target: target value
# @return: a list of index [start, end]. If not found, return [-1, -1]
def search_range(A, target):
    if not A:
        return [-1, -1]

    else:
        result = [len(A)-1, 0]
        search_range_helper(A, target, 0, len(A)-1, result)

        if result[0] == len(A)-1 and result[1] == 0 and A[0] != target:
            return [-1, -1]
        else:
            return result

# func: helper function for search_range
# @param A: integer list A
# @param target: target value
# @param start: searching start position
# @param end: searching end position
# @param result: result list
# @return:
def search_range_helper(A, target, start, end, result):
    if start > end:
        return
    else:
        mid = start + (end-start)/2
        #If target value is found
        if A[mid] == target:
            if mid == 0:
                result[0] = 0
            if mid == len(A) - 1:
                result[1] = len(A) - 1

            if 0 < mid < result[0] and A[mid-1] != target:
                result[0] = mid
            else:
                search_range_helper(A, target, start, mid-1, result)

            if result[1] <= mid < len(A)-1 and A[mid+1] != target:
                result[1] = mid
            else:
                search_range_helper(A, target, mid+1, end, result)

        elif A[mid] > target:
            search_range_helper(A, target, start, mid-1, result)
        else:
            search_range_helper(A, target, mid+1, end, result)

There is a cheating way for Python. We can use system library bisect to perform binary search in a list

Python Code Cheating:

def searchRange(self, A, target):
    if not A:
        return [-1, -1]

    left_index = bisect.bisect_left(A, target)
    if left_index == len(A) or A[left_index] != target:
        return [-1, -1]

    right_index = bisect.bisect_right(A, target)
    return [left_index, right_index-1]