本文概览：本文讲解在排序数组中查找元素的第一个和最后一个位置的核心思路：通过两次二分查找分别定位左右边界

一、题目

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

二、题目分析

这题给的是一个非严格递增的数组，意味着可能有重复元素，比如 [1, 1, 2, 3] 有两个 1。

题目要求找到 target 的左边界索引和右边界索引：

  • 查找 1，返回 [0, 1]（左边界 0，右边界 1）
  • 查找 2，返回 [2, 2]（左右边界都是 2）
  • 查找 4，返回 [-1, -1]（不存在）

题目要求时间复杂度 O(log n)，看到有序数组 + O(log n)，显然要用二分查找。

思路概览

Java 实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int[] searchRange(int[] nums, int target) {
    int[] res = {-1, -1};
    if (nums.length == 0) {
        return res;
    }
    int left = 0;
    int right = nums.length - 1;
    // 二分查找左边界
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) {
        return res;
    }
    res[0] = left;
    // 查找右边界
    right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    res[1] = right;
    return res;
}

思路简要说明：

  1. 第一次二分：找左边界，只要 nums[mid] >= target，就更新 right = mid - 1
  2. 第二次二分：找右边界，只要 nums[mid] <= target，就更新 left = mid + 1
  3. 边界检查：如果 left >= nums.length 或 nums[left] != target，说明不存在，返回 [-1, -1]

三、思路详解

第一步：为什么不能用"先找到再向两边扩展"

一个直观的思路是：先用二分找到 target 的任意一个位置，然后向两边扩展找到边界。

但这个思路的时间复杂度是 O(log n + k)，k 是 target 的个数。最坏情况下（数组全是 target），k = n，时间复杂度退化为 O(n)，不符合题目要求。

所以必须用两次二分查找，分别定位左右边界，时间复杂度才是 O(log n)。

第二步：左边界查找的思路

左边界的意思是：第一个等于 target 的位置。

二分查找时，只要 nums[mid] >= target，说明左边界可能在 mid 或 mid 左边，所以更新 right = mid - 1。

只有当 nums[mid] < target 时，才更新 left = mid + 1。

这样循环结束时，left 就是左边界（如果存在的话）。

第三步：右边界查找的思路

右边界的意思是：最后一个等于 target 的位置。

二分查找时，只要 nums[mid] <= target，说明右边界可能在 mid 或 mid 右边，所以更新 left = mid + 1。

只有当 nums[mid] > target 时，才更新 right = mid - 1。

这样循环结束时，right 就是右边界（如果存在的话）。

第四步：边界情况处理

有两种情况 target 不存在：

  1. target 比所有元素都小：比如 [1, 3, 4] 查找 0，循环结束时 left = 0，但 nums[0] = 1 != 0
  2. target 比所有元素都大：比如 [1, 3, 4] 查找 5，循环结束时 left = 3，但 left >= nums.length
  3. target 在中间但不存在：比如 [1, 3, 4] 查找 2，循环结束时 left = 1，但 nums[1] = 3 != 2

所以检查条件是：

1
2
3
if (left >= nums.length || nums[left] != target) {
    return res; // 返回 [-1, -1]
}

第五步：完整执行过程

例子 1：target 存在

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

第一次二分：找左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
初始：left=0, right=5

第 1 轮：
  mid = 2, nums[2] = 7 < 8
  left = 3

第 2 轮：
  left=3, right=5
  mid = 4, nums[4] = 8 >= 8
  right = 3

第 3 轮：
  left=3, right=3
  mid = 3, nums[3] = 8 >= 8
  right = 2

第 4 轮：
  left=3, right=2
  left > right，退出循环
  left = 3，nums[3] = 8 == 8 ✓
  左边界 = 3

第二次二分：找右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
初始：left=3, right=5

第 1 轮：
  mid = 4, nums[4] = 8 <= 8
  left = 5

第 2 轮：
  left=5, right=5
  mid = 5, nums[5] = 10 > 8
  right = 4

第 3 轮：
  left=5, right=4
  left > right，退出循环
  right = 4
  右边界 = 4

返回 [3, 4] ✓

例子 2：target 不存在

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

第一次二分：找左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
初始：left=0, right=5

第 1 轮：
  mid = 2, nums[2] = 7 >= 6
  right = 1

第 2 轮：
  left=0, right=1
  mid = 0, nums[0] = 5 < 6
  left = 1

第 3 轮：
  left=1, right=1
  mid = 1, nums[1] = 7 >= 6
  right = 0

第 4 轮：
  left=1, right=0
  left > right，退出循环
  left = 1，nums[1] = 7 != 6
  不存在，返回 [-1, -1]

四、总结

在排序数组中查找元素的第一个和最后一个位置的核心是两次二分查找：

  1. 第一次二分：找左边界，nums[mid] >= target 时 right = mid - 1
  2. 第二次二分：找右边界，nums[mid] <= target 时 left = mid + 1
  3. 边界检查：判断 target 是否真的存在

时间复杂度 O(log n)，空间复杂度 O(1)。