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

tags: array, binary search

简单题的变形，需要考虑找到结果后，从结果位置出发向左向右搜索所有与结果连续相等的数字。

中间有一点需要注意：left和right表示的是第一个不符合条件的元素位置，我们需要对left加一，对right减一，使之满足我们的条件。

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> re;
        _searchRange(re, A, 0, n, target);
        return re;
    }
    void _searchRange(vector<int> &result, int A[], int start, int end, int target){
        int mid = (start + end) / 2;
        if(start + 1 > end){//not found
            result.push_back(-1);
            result.push_back(-1);
            return;
        }
        else if(A[mid] == target){//found
            int left = mid;
            int right = mid;
            while(A[left] == target && left >= start){
                left--;
            }
            left++;//important
            while(A[right] == target && right < end){
                right++;
            }
            right--;//important
            result.push_back(left);
            result.push_back(right);
            return;
        }
        else{
            if(A[mid] > target){
                _searchRange(result, A, start, mid, target);
            }
            else{
                _searchRange(result, A, mid + 1, end, target);
            }
        }
        
    }
};