题目描述

给定一个按照升序排列的整数数组 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]

算法分析

二分套路多，请看 二分套路总结

根据题意，其实就是要我们求出一段包含所有给定目标值的区间，并返回该区间的左右端点。因此我们直接套用上面的模板一和二，即可求出答案，当我们第一次求某一侧端点时，需要看一下它的值是不是等于我们的目标值，如果不相等，说明数组中并不存在我们要找的数，此时即可返回[-1, -1]了。

C++代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (!nums.size()) return {-1, -1};

        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1; 
        }
        if (nums[l] != target) return {-1, -1};
        res.push_back(l);
        l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        res.push_back(r);
        return res;
    }
};