题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解题思路

二分查找。需要分别查找上下边界。如果是查找下界的话，当找到target的值则high=mid，继续查找直到!(low<high)；同理上边界。

int helper(vector<int>& nums, int target, bool left){
    int low=0;
    int high=nums.size()-1;
    int mid;
    while(low<high){
        mid = (low+high)/2;
        if(nums[mid]>target || (left && nums[mid]==target))
            high = mid;
        else
            low = mid + 1;
    }
    return nums[mid]==target ? mid : -1;
}
vector<int> SearchRange(vector<int>& nums, int target){
    int left = helper(nums, target, true);
    int right = helper(nums, target, false);
    return vector<int> {left, right};
}