题目描述

给定一个按照升序排列的整数数组 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(\log n)$

1. 第一次二分查找第一个位置使得它的值 大于等于 target，若该位置的值不等于 target，则返回 [-1, -1]。
2. 第二次二分查找第一个位置使得它的值 大于 target。注意需要特判边界。

时间复杂度

• 两次二分时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

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

        int l = 0, r = n - 1;
        int start, end;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] < target)
                l = mid + 1;
            else
                r = mid;
        }

        if (nums[l] != target)
            return vector<int>({-1, -1});

        start = l;

        l = 0; r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target)
                l = mid + 1;
            else
                r = mid;
        }

        if (nums[l] > target)
            end = l - 1;
        else
            end = l;

        return vector<int>({start, end});
    }
};