在排序数组中查找元素的第一个和最后一个位置

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

二分查找：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lowerBound(nums, target);
        if (left == nums.size() || nums[left] != target)
        {
            return {-1, -1};
        }

        int right = upperBound(nums, target) - 1;
        return {left, right};
    }

private:
    int lowerBound(vector<int>& nums, int target)
    {
        int left = 0;
        int right = nums.size();

        while (left < right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] >= target)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        return left;
    }

    int upperBound(vector<int>& nums, int target)
    {
        int left = 0;
        int right = nums.size();

        while (left < right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] > target)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        return left;
    }
};

核心思想

数组已经按非递减顺序排列，所以可以使用二分查找。

这题不是只找一个目标值，而是要找到它出现的范围：

• 最左边第一次出现的位置
• 最右边最后一次出现的位置

如果把“开始位置”和“结束位置”分开看，其实就是两个经典问题：

• 第一个大于等于 target 的位置
• 第一个大于 target 的位置，再往左一格

这题最关键的观察是：

目标区间的左边界是第一个满足 nums[i] >= target 的下标；右边界是第一个满足 nums[i] > target 的下标减 1。

因此只需要做两次二分：

1. 用 lowerBound 找到第一个大于等于 target 的位置。
2. 用 upperBound 找到第一个大于 target 的位置，再减 1 得到最后一个等于 target 的位置。

为什么要找两个边界

如果数组中目标值只出现一次，那么起点和终点相同。

如果目标值出现多次，那么这些相同值会连续排列在一起。

例如：

nums = [5,7,7,8,8,10], target = 8

8 的位置是：

3, 4

所以必须找到：

• 第一次出现 8 的位置 3
• 最后一次出现 8 的位置 4

普通二分只会告诉你“找到了一个 8”，但不知道它是否是最左或最右。

因此需要专门维护边界。

lowerBound 的含义

lowerBound(nums, target) 返回的是：

第一个满足 nums[i] >= target 的位置。

代码使用左闭右开区间 [left, right)：

int left = 0;
int right = nums.size();

循环中：

• 如果 nums[mid] >= target，说明 mid 可能就是答案，继续往左找，令 right = mid
• 如果 nums[mid] < target，说明 mid 及其左侧都不可能是答案，令 left = mid + 1

循环结束后，left 就是第一个大于等于 target 的位置。

upperBound 的含义

upperBound(nums, target) 返回的是：

第一个满足 nums[i] > target 的位置。

它和 lowerBound 很像，只是比较条件改成了 >。

代码中：

• 如果 nums[mid] > target，说明 mid 可能是答案，继续往左找，令 right = mid
• 如果 nums[mid] <= target，说明 mid 及其左侧都不可能是第一个大于 target 的位置，令 left = mid + 1

循环结束后，left 就是第一个大于 target 的位置。

把它减 1，就是最后一个等于 target 的位置。

为什么先检查 nums[left] != target

lowerBound 找到的是第一个大于等于 target 的位置。

如果这个位置已经越界，或者它的值不等于 target，说明数组中根本不存在 target。

例如：

nums = [5,7,7,8,8,10], target = 6

lowerBound 会返回 1，因为 nums[1] = 7 是第一个大于等于 6 的元素。

但 nums[1] != 6，说明数组里没有 6。

因此直接返回：

{-1, -1}

为什么 right = upperBound(...) - 1

upperBound 返回的是第一个大于 target 的位置。

这个位置右边的元素一定都大于 target，不能作为目标值的结束位置。

而它左边一格的位置，才是最后一个等于 target 的位置。

例如：

nums = [5,7,7,8,8,10], target = 8

upperBound 返回的是 5，因为 nums[5] = 10 是第一个大于 8 的元素。

所以最后一个 8 的位置是：

5 - 1 = 4

边界情况

如果数组为空，lowerBound 会直接返回 0，但 nums.size() == 0，所以会返回 [-1, -1]。

如果 target 小于所有元素，lowerBound 会返回 0，但 nums[0] != target，所以返回 [-1, -1]。

如果 target 大于所有元素，lowerBound 会返回 nums.size()，说明数组中不存在该值，返回 [-1, -1]。

如果 target 只出现一次，那么 lowerBound 和 upperBound - 1 会得到同一个下标。

如果 target 出现多次，那么两个边界会把这一段连续区间完整圈出来。

题目保证数组是非递减的，所以相同值会连续出现，二分得到的边界一定是连续段的左右端点。

正确性证明

我们证明：算法返回的区间正好是 target 在数组中的开始位置和结束位置。

结论 1：lowerBound 返回第一个大于等于 target 的位置

在 [left, right) 区间内，算法保持如下性质：

• left 左侧的元素都小于 target
• right 及其右侧仍可能存在第一个大于等于 target 的位置

如果 nums[mid] >= target，那么 mid 及其右侧都不可能比 mid 更早成为第一个满足条件的位置，所以保留左半部分，令 right = mid。

如果 nums[mid] < target，那么 mid 及其左侧都不可能是答案，令 left = mid + 1。

循环结束时，left == right，此时 left 就是第一个大于等于 target 的位置。

结论 2：upperBound 返回第一个大于 target 的位置

upperBound 的证明和 lowerBound 完全类似，只是把比较条件改成了 > target。

如果 nums[mid] > target，说明 mid 可能是第一个大于 target 的位置，继续向左收缩。

如果 nums[mid] <= target，说明 mid 及其左侧都不可能是第一个大于 target 的位置，继续向右收缩。

因此循环结束时，left 就是第一个大于 target 的位置。

结论 3：如果 lowerBound 位置不是 target，说明数组中不存在 target。

lowerBound 找到的是第一个大于等于 target 的位置。

如果这个位置越界，说明数组中所有元素都小于 target。

如果这个位置存在，但它的值不等于 target，由于它已经是第一个大于等于 target 的位置，说明数组中不存在值等于 target 的元素。

所以可以直接返回 [-1, -1]。

结论 4：lowerBound 和 upperBound - 1 分别是目标区间的左边界和右边界

如果数组中存在 target，那么所有等于 target 的元素一定连续排列。

lowerBound 找到的是这段连续区间的第一个位置，也就是左边界。

upperBound 找到的是这段连续区间后面第一个更大的位置，所以 upperBound - 1 就是最后一个等于 target 的位置，也就是右边界。

得出结论

由结论 1 可知，lowerBound 正确。

由结论 2 可知，upperBound 正确。

由结论 3 可知，如果 target 不存在，算法会返回 [-1, -1]。

由结论 4 可知，如果 target 存在，算法返回的正是它的开始位置和结束位置。

因此算法正确。

举例理解

以：

nums = [5,7,7,8,8,10], target = 8

为例。

lowerBound

目标是找到第一个大于等于 8 的位置。

二分过程：

结束时 left = 3，所以左边界是 3。

upperBound

目标是找到第一个大于 8 的位置。

二分过程：

结束时 left = 5，所以右边界是：

5 - 1 = 4

最终答案是：

[3,4]

如果 target = 6：

• lowerBound 会返回 1
• 但 nums[1] = 7 != 6

所以直接返回：

[-1,-1]

复杂度分析

lowerBound 和 upperBound 都是标准二分查找。

每次都会把搜索区间缩小一半。

所以单次时间复杂度是：

O(log n)

一共做两次二分，仍然是：

O(log n)

算法只使用了常数个变量，没有额外数组。

所以空间复杂度是：

O(1)