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

LeetCode 原题链接

#题目描述

给定一个按照非递减顺序排列的整数数组 nums，以及一个目标值 target，请返回 target 在数组中的起始位置和结束位置。

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

要求算法的时间复杂度必须是 O(log n)。

示例：

输入：nums = [5, 7, 7, 8, 8, 10], target = 8
输出：[3, 4]
解释：target = 8 第一次出现在下标 3，最后一次出现在下标 4。

#题型判断

这是一道有序数组中的边界查找题。

数组已经按照非递减顺序排列，说明相同元素一定连续出现。题目又要求 O(log n)，不能线性扫描，所以应使用二分查找。

不过这道题不是找到任意一个 target 就结束，而是要找：

• 第一个等于 target 的位置。
• 最后一个等于 target 的位置。

因此它属于边界二分。

#核心思路

可以把问题拆成两次二分，并且只写一个通用函数 lowerBound：

1. lowerBound(nums, target)：找第一个大于等于 target 的位置，也就是左边界。
2. lowerBound(nums, target + 1) - 1：找第一个大于等于 target + 1 的位置，它的前一个位置就是右边界。

为什么这样可行？

• 左边界就是第一个不小于 target 的位置。
• 右边界之后的第一个位置，就是第一个大于 target 的位置。由于数组元素是整数，可以用第一个大于等于 target + 1 的位置来表示。

最后还要检查找到的左右边界是否真的对应 target。如果左边界越界，或者 nums[leftIndex] !== target，说明数组里没有目标值，返回 [-1, -1]。

#怎么理解lowerBound

lowerBound(nums, value) 的含义是：在有序数组中，找到第一个 >= value 的下标。

也可以把它理解成 value 应该插入到数组中的位置，并且插入后数组仍然有序。

例如：

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

lowerBound(nums, 8) 返回 3，因为下标 3 是第一个 >= 8 的位置：

[5, 7, 7, 8, 8, 10]
          ^
          第一个 >= 8

所以 3 就是 target = 8 的左边界。

#怎么理解target + 1

右边界要找的是最后一个等于 target 的位置。

直接找“最后一个等于 target”当然可以，但如果已经有了 lowerBound，可以换一种角度：

1. 先找第一个大于 target 的位置。
2. 这个位置的前一个下标，就是最后一个等于 target 的位置。

由于本题数组元素是整数，第一个大于 target 的位置，等价于第一个大于等于 target + 1 的位置。

还是以 target = 8 为例：

nums = [5, 7, 7, 8, 8, 10]
target + 1 = 9

lowerBound(nums, 9) 返回 5，因为下标 5 是第一个 >= 9 的位置：

[5, 7, 7, 8, 8, 10]
                ^
                第一个 >= 9，也就是第一个 > 8

那么最后一个 8 的位置就是：

lowerBound(nums, 9) - 1 = 5 - 1 = 4

所以右边界是 4。

如果数组是：

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

lowerBound(nums, 9) 会返回 nums.length = 5，表示数组中没有 >= 9 的位置，也就是所有元素都小于 9。此时右边界就是：

5 - 1 = 4

仍然能正确指向最后一个 8。

#示例步骤图解

以 nums = [5, 7, 7, 8, 8, 10]，target = 8 为例。

#查找左边界

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

循环结束，左边界是 3。

#查找右边界

目标：先找到第一个大于等于 9 的位置，再减一。

循环结束，第一个大于等于 9 的位置是 5，所以右边界是 5 - 1 = 4。

最终返回 [3, 4]。

#变量与区间含义

本题使用闭区间 [left, right]。

• left：当前搜索区间的左边界。
• right：当前搜索区间的右边界。
• mid：当前检查的中间下标。
• ans：当前已经找到的候选边界。

lowerBound(nums, value) 查找第一个大于等于 value 的位置：

• ans 初始化为 nums.length，表示还没有找到符合条件的位置。
• 当 nums[mid] >= value 时，mid 可能是答案，记录下来，并继续搜索左半边。
• 当 nums[mid] < value 时，mid 和它左边的元素都太小，搜索右半边。

#推进规则

#lowerBound

当前 mid 是否可能成为答案？

• 如果 nums[mid] >= value，可能成为答案。
• 如果 nums[mid] < value，不可能成为答案，因为它和它左边的元素都小于 value。

边界移动：

• nums[mid] >= value：记录 ans = mid，然后 right = mid - 1。
• nums[mid] < value：排除左半边，left = mid + 1。

左边界使用 lowerBound(nums, target)。

右边界使用 lowerBound(nums, target + 1) - 1。

#边界条件与易错点

• 空数组：right = -1，二分循环不会进入，最终返回 [-1, -1]。
• 单元素数组：同样适用闭区间二分。
• 目标值不存在：只找到插入位置还不够，必须检查 nums[leftIndex] === target。
• 找边界时，遇到 target 不能立刻返回，因为还要继续向左或向右收缩。
• mid 已经被检查过，所以移动边界时要使用 mid + 1 或 mid - 1，避免死循环。

#代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // 左边界：第一个大于等于 target 的位置。
  const leftIndex = lowerBound(nums, target);

  // 如果 leftIndex 越界，或者当前位置不是 target，说明 target 不存在。
  if (leftIndex === nums.length || nums[leftIndex] !== target) {
    return [-1, -1];
  }

  // 右边界：第一个大于 target 的位置再往前一位。
  const rightIndex = lowerBound(nums, target + 1) - 1;

  return [leftIndex, rightIndex];
};

function lowerBound(nums, value) {
  let left = 0;
  let right = nums.length - 1;
  // 默认没有找到符合条件的位置，用 nums.length 表示插入到数组末尾。
  let ans = nums.length;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] >= value) {
      // mid 可能是第一个大于等于 value 的位置，先记录下来。
      ans = mid;
      // 继续向左找，确认前面是否还有更靠左的候选位置。
      right = mid - 1;
    } else {
      // nums[mid] 太小，mid 以及左侧都不可能是答案。
      left = mid + 1;
    }
  }

  return ans;
}

#其他解法

#一个函数查左右边界

也可以把左边界和右边界的查找合并到同一个函数里，通过 side 控制当前要找哪一侧边界。

这种写法的优势是语义直观：

• side === "left"：遇到 target 时继续向左收缩，最终返回左边界。
• side === "right"：遇到 target 时继续向右收缩，最终返回右边界。

相比 lowerBound(nums, target + 1) - 1，这种写法不依赖 target + 1，但函数内部需要多判断一次当前查找方向。

#代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  const left = searchBoundary(nums, target, "left");
  const right = searchBoundary(nums, target, "right");

  return left <= right ? [left, right] : [-1, -1];
};

function searchBoundary(nums, target, side) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] > target || (side === "left" && nums[mid] === target)) {
      // 当前值偏大，或者正在找左边界且已经遇到 target，都要继续向左收缩。
      right = mid - 1;
    } else {
      // 当前值偏小，或者正在找右边界且已经遇到 target，都要继续向右收缩。
      left = mid + 1;
    }
  }

  return side === "left" ? left : right;
}

#复杂度分析

• 时间复杂度：O(log n)。两次二分查找，每次都会将搜索区间缩小一半。
• 空间复杂度：O(1)。只使用了常数个变量。

#双指针

如果不考虑题目要求的 O(log n)，也可以使用双指针从数组两端向中间查找。

因为数组是有序的：

• 左指针 left 从左往右移动，遇到第一个 target 时，就是起始位置。
• 右指针 right 从右往左移动，遇到第一个 target 时，就是结束位置。

这种写法非常直观，但最坏情况下需要扫描整个数组，所以时间复杂度是 O(n)，不符合本题的最优要求。

#双指针步骤图解

以 nums = [5, 7, 7, 8, 8, 10]，target = 8 为例：

最终返回 [3, 4]。

#双指针代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;

  // 从左往右找第一个 target。
  while (left < nums.length && nums[left] !== target) {
    left++;
  }

  // 左侧没有找到 target，说明整个数组都不存在 target。
  if (left === nums.length) {
    return [-1, -1];
  }

  // 从右往左找最后一个 target。
  while (right >= 0 && nums[right] !== target) {
    right--;
  }

  return [left, right];
};

#双指针复杂度分析

• 时间复杂度：O(n)。最坏情况下左右指针总共会扫描整个数组。
• 空间复杂度：O(1)。只使用了常数个变量。

#复杂度分析

• 时间复杂度：O(log n)。分别进行两次二分查找，每次都是 O(log n)。
• 空间复杂度：O(1)。只使用了常数个变量。