61. 搜索区间

给定一个包含 n 个整数的排序数组，找出给定目标值 target的起始和结束位置。

如果目标值不在数组中，则返回[-1, -1]

 

样例

给出[5, 7, 7, 8, 8, 10]和目标值target=8,

返回[3, 4]

挑战 

时间复杂度 O(log n)

 

 

应该要第一时间反应到二分，就算没有想到看到这个时间复杂度也要想到了

总体思路就是用二分找到target再前后搜索下就行了

vector<int> searchRange(vector<int> &A, int target) {
        // write your code here
        vector<int> res;
        if(A.empty() ||target < A[0] || target > A[A.size() - 1]){ 
            res.push_back(-1);
            res.push_back(-1);
            return res;  
        }  
        
        int low=0,high=A.size();
        int mid;
        int start,end;
        while(low<=high){
            mid=low+(high-low)/2;
            if(A[mid]==target){
                start=mid-1;
                end=mid+1;
                while (end < A.size() && A[end] == target) {
                    end++;
                }
                while (start >= 0 && A[start] == target ) {
                    start--; 
                }
                res.push_back(start + 1);
                res.push_back(end - 1);
                return res;
            }
            
            if(A[mid]>target){
                high=mid-1;
            }
            else{
                low=mid+1;
            }
        }
        res.push_back(-1);
        res.push_back(-1);
        return res; 
    }