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

算法刷题>LeetCode>面试经典150
3.7k words

问题描述

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

核心设计思想：为何选择两次二分搜索？

要解决这个问题并满足 O(log n) 的时间复杂度，二分搜索是唯一可行的路径。但标准的二分搜索只能判断一个元素是否存在，或者找到它的任意一个位置。我们的问题更复杂：需要找到一个可能重复出现的目标值的确切左右边界。

方案一：一次二分搜索 + 线性扫描（被否决）

一个自然而然的想法是：

  1. 用一次标准的二分搜索找到 target 的任意一个位置 p。
  2. 从 p 开始，向左线性扫描找到起始位置 start。
  3. 从 p 开始，向右线性扫描找到结束位置 end。

这种方法在 target 不重复或重复次数很少时表现良好。但是，考虑最坏情况：nums = [8, 8, 8, ..., 8]。此时，线性扫描的复杂度会退化到 O(n)，导致整个算法的时间复杂度变为 O(log n + n) = O(n)，不符合题目的进阶要求。

方案二：两次独立的二分搜索（最终选择）

为了保证 O(log n) 的复杂度，我们必须在查找边界的过程中也使用对数时间复杂度的算法。这就引出了最终的设计：执行两次独立的、经过特殊改造的二分搜索。

  1. 第一次搜索：专门设计用于查找左边界（起始位置）。
  2. 第二次搜索：专门设计用于查找右边界（结束位置）。

这种”分而治之”的思想，将一个复杂问题（寻找一个区间）分解为两个独立的、更简单的子问题（分别寻找左、右边界），每次查找都保持 O(log n) 的效率，从而确保总体复杂度达标。

解题思路与实现细节

🚀 二分搜索的精髓：循环不变量与边界收敛

重点标记：
这道题是学习二分搜索的绝佳范例。它考察的不是你是否会写二分搜索，而是你是否真正理解其核心原理，特别是循环不变量 (loop invariant) 和边界收敛。

循环不变量是指在循环的每次迭代之前和之后都保持为真的一个条件。在我们的二分搜索中，这个不变量就是 “目标值（如果存在）一定在闭区间 [left, right] 内”。

  • 循环条件 while (left <= right) 保证了只要这个区间有效（left 不大于 right），我们就继续搜索。当 left > right 时，区间 [left, right] 变为空，说明搜索结束。
  • 边界更新 left = mid + 1 或 right = mid - 1 的设计，正是为了在排除 mid 后，继续维持这个不变量。

理解了这一点，你就能自信地调整边界更新逻辑，以满足不同的查找目标（左边界、右边界，或第一个大于/小于某值的元素）。

第一次搜索：查找起始位置（左边界）

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

  • nums[mid] < target: 这意味着 mid 以及其左边的所有元素都绝对不是起始位置。因此，我们将搜索区间的左边界移动到 mid 的右边：left = mid + 1。
  • nums[mid] >= target: 这意味着 mid 可能是起始位置，但它左边可能还有更早的 target。我们不能排除 mid，但可以肯定起始位置不会在 mid 的右边。因此，我们将搜索区间的右边界收缩到 mid 的左边：right = mid - 1，并期望在下一轮找到更靠左的位置。

指针收敛过程：
当循环结束时（left > right），left 指针将停在这样一个位置：它是数组中第一个值大于或等于 target 的索引。我们只需在循环后检查 nums[left] 是否确实等于 target，即可确认是否找到了起始位置。

第二次搜索：查找结束位置（右边界）

目标：找到最后一个小于或等于 target 的位置。

  • nums[mid] <= target: 这意味着 mid 可能是结束位置，或者结束位置在它的右边。我们不能排除 mid，但可以肯定结束位置不会在 mid 的左边。因此，我们将搜索区间的左边界移动到 mid 的右边：left = mid + 1，并期望在下一轮找到更靠右的位置。
  • nums[mid] > target: 这意味着 mid 以及其右边的所有元素都绝对不是结束位置。因此，我们将搜索区间的右边界收缩到 mid 的左边：right = mid - 1。

指针收敛过程：
当循环结束时（left > right），right 指针将停在这样一个位置：它是数组中最后一个值小于或等于 target 的索引。这个位置就是我们要找的结束位置。

代码实现

这是使用 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
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{-1, -1};
    }

    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
}

复杂度分析

  • 时间复杂度: O(log n)

    • 我们执行了两次独立的二分搜索，每次的时间复杂度都是 O(log n)。
    • 因此，总的时间复杂度为 O(log n) + O(log n) = O(log n)。

  • 空间复杂度: O(1)

    • 我们只使用了有限的几个变量 (start, end, left, right, mid, n)，没有使用额外的存储空间。

关键收获

  • 分治思想：将”寻找一个区间”的复杂问题，拆分为”寻找左边界”和”寻找右边界”两个独立的、更简单的问题，是解决复杂问题的有效策略。
  • 理解循环不变量：二分搜索的核心是维护”目标在 [left, right] 区间内”这个不变量。理解这一点，可以帮助你正确地设计循环条件和边界更新逻辑。
  • 边界调整的艺术：通过微调 if 条件和 left/right 的更新方式，二分搜索可以实现多种查找目标（如第一个大于X的数，最后一个小于X的数等），这是其强大灵活性的体现。
  • 代码健壮性：计算 mid 时使用 left + (right-left)>>1 而不是 (left+right)>>1，可以有效防止当 left 和 right 都很大时可能发生的整数溢出问题。