跳至内容

查找元素的首尾位置

LeetCode 34：用两次二分查找确定目标值的起始位置和结束位置。

LeetCode 34 中等 数组
发布于 约 3 分钟阅读 浏览 — 次
  • 数组
  • 二分查找
  • 复杂度
  • Python
  • 变量

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

在非递减整数数组（允许重复）中查找 target 的首尾下标；不存在时返回 [-1, -1]。要求时间复杂度为 O(log n)。

1. 查找过程

nums = [5, 7, 7, 8, 8, 10]，target = 8。以下为区间示意，L、M、R 分别表示左边界、中点、右边界。

1.1 找第一个 8

第 1 轮

代码块 Text
1
2
3
4

index:  0   1   2   3   4   5
value:  5   7   7   8   8  10
        ●───●───●───●───●───●
        L       M           R

middle = 2，nums[2] = 7 < 8，排除下标 0～2，更新 left = middle + 1，即 left = 3。

第 2 轮：检查下标 [3, 5]

代码块 Text
1
2
3
4

index:  3   4   5
value:  8   8  10
        ●───●───●
        L   M   R

middle = 4，nums[4] = 8。左侧可能还有 8，不能直接返回；更新 right = middle - 1， 即 right = 3，继续检查下标 3。

第 3 轮：只检查下标 3

代码块 Text
1
2
3
4

index:  3
value:  8
        ●
      L=M=R

nums[3] = 8，仍更新 right = middle - 1，即 right = 2。此时 left = 3 > right = 2， 查找结束，返回 3。检查 nums[3] == target，确认目标存在，再查最后一个位置。

把上面“找第一个大于或等于指定数的位置”的过程写成一个函数，本文将它命名为 lower_bound(value)。

关键提示：查找中，left 左侧的元素都小于 value，right 右侧的元素都大于或等于 value。结束时 left = right + 1，因此返回的 left 正是第一个 >= value 的位置；如果所有元素都小于 value，就返回 len(nums)。

1.2 找最后一个 8

本题元素和 target 都是整数，第一个 >= 9 的位置，就是第一个 > 8 的位置；它的前一个位置才是最后一个 8。

重新查找 lower_bound(9)。第 1 轮同样比较 nums[2] = 7 < 9，更新 left = 3，从第 2 轮继续看。

第 2 轮：检查下标 [3, 5]

代码块 Text
1
2
3
4

index:  3   4   5
value:  8   8  10
        ●───●───●
        L   M   R

middle = 4，nums[4] = 8 < 9，更新 left = middle + 1，即 left = 5，只剩下标 5。

第 3 轮：只检查下标 5

代码块 Text
1
2
3
4

index:  5
value: 10
        ●
      L=M=R

nums[5] = 10 >= 9，更新 right = middle - 1，即 right = 4。此时 left = 5 > right = 4，返回 5，所以最后一个 8 的下标是 5 - 1 = 4，最终返回 [3, 4]。

2. Python 实现

只需找到一个匹配位置时，二分查找遇到相等就可以返回，常用 if / elif / else 分别处理大于、小于、等于。 本题要找第一个符合条件的位置，大于和等于时都继续向左找，可以合并为 nums[middle] >= value。 这个条件不成立时，就只剩 nums[middle] < value。

因此，下面的 else 等价于 elif nums[middle] < value，相等的情况已经由上面的 if 处理。 小于时，由于数组有序，当前中点及其左侧都小于 value，可以一起排除，更新 left = middle + 1。

代码块 Python
 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

def search_range(nums, target):
    def lower_bound(value):
        """
        value 存在时，返回它第一次出现的下标
        value 不存在时，返回第一个大于 value 的元素下标
        若 value 大于所有元素，则返回 len(nums)
        """
        left, right = 0, len(nums) - 1  # 左闭右闭区间 [left, right]

        while left <= right:
            middle = (left + right) // 2
            if nums[middle] >= value:
                right = middle - 1  # 大于和等于时都继续向左找
            else:  # nums[middle] < value
                left = middle + 1  # 排除中点及其左侧
        return left

    first = lower_bound(target)

    # 先判断 first 是否越界，再访问 nums[first]；空数组也由此处理
    # 例如 nums = [1, 3, 5]、target = 10 时，first == len(nums)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]

    # 整数数组中，第一个 >= target + 1 的位置，就是第一个 > target 的位置
    # 它的前一个位置才是 target 的最后出现位置，因此减 1
    last = lower_bound(target + 1) - 1
    return [first, last]


nums = [5, 7, 7, 8, 8, 10]
print(search_range(nums, 8))
print(search_range(nums, 6))
print(search_range([], 0))
运行结果 Text
1
2
3

# [3, 4]
# [-1, -1]
# [-1, -1]

3. 复杂度

  • 时间复杂度：O(log n)，两次二分查找各自都是 O(log n)。
  • 额外空间复杂度：O(1)，只维护固定数量的下标变量。

若先用普通二分命中，再向两侧逐个扫描，target 出现 k 次时总时间为 O(log n + k)。 当数组全部等于 target 时，最坏为 O(n)，不满足本题要求。

评论

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。