题目描述

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

你的算法时间复杂度必须是 O(log n) 级别。

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

样例

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

样例

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

算法

(两次二分） $O(n^2)$

1,第一次用二分找到左边界，如果左边界的值不等于 target ，返回(-1，-1)。
2,第二次用二分找到右边界。

C++ 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start,end;
        int l = 0, r = nums.size()-1, mid;
        if(!nums.size())  
             return vector<int>({-1,-1}); //判断数组是否为空
        while(l < r)
        {
            mid = (l + r) / 2;    //这里不需要加 1 
            if(nums[mid] < target) //mid小于目标值，慢慢向右逼近，找到左边界
                l = mid + 1;
            else
                r = mid;
        }

        if(nums[l]!=target) 
             return vector<int>({-1,-1}); //判断数组中是否存在target 

        start = l;
        l = 0 , r = nums.size() - 1;  //重置

        while(l<r)
        {
            mid = (l + r + 1) / 2;    //这里要加1
            if(nums[mid] > target)   //mid大于目标值，慢慢向左逼近，找到右边界
                r = mid - 1;
            else
                l = mid;
        }
        end = l;
        return vector<int>({start,end});
    }
};