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

🎯 问题描述（来源于LeetCode）

描述：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

说明：

  • 这是一个二分查找问题。

  • 核心逻辑是找到目标值的下界（第一个大于等于目标值的位置）。

  • 通过两次二分查找，分别找到目标值的起始位置和结束位置。

  • 示例：

  • 示例 1：

1
2
3
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
解释：目标值 8 在数组中的开始位置是 3，结束位置是 4。
  • 示例 2：
1
2
3
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
解释：目标值 6 不在数组中。

💻 解题思路

思路1：二分查找（下界）

思路1：代码实现

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
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lowerbond(nums: List[int], target: int):
            # 寻找第一个大于等于 target 的位置
            left = -1
            right = len(nums) 
            while left + 1 < right:
                mid = left + (right - left)//2
                if nums[mid] < target:
                    left = mid
                else:
                    right = mid 
            return right        
        
        # 1. 找到 target 的起始位置（第一个 >= target 的位置）
        start = lowerbond(nums, target)
        
        # 2. 检查起始位置是否有效
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        
        # 3. 找到 target+1 的起始位置，然后减 1，得到 target 的结束位置
        end = lowerbond(nums, target + 1) - 1
        
        return [start, end]

思路1：📊 性能分析

  • 时间复杂度：O(log⁡N)O(\log N)
    • 其中 NN 是数组 nums 的长度。
    • 代码中调用了两次 lowerbond 函数，每次都是二分查找，时间复杂度为 O(log⁡N)O(\log N)。
    • 总时间复杂度为 O(2log⁡N)≈O(log⁡N)O(2 \log N) \approx O(\log N)。
  • 空间复杂度：O(1)O(1)
    • 只使用了常数个额外变量，没有使用额外的数据结构。

思考

  1. 二分查找模板：

    • 代码使用了开区间的二分查找模板：left = -1, right = len(nums)，循环条件为 while left + 1 < right。
    • 这种模板的优点是边界处理简单，不需要考虑 left == right 的情况。
    • 最终返回的 right 就是第一个大于等于 target 的位置。

  2. 起始位置：

    • start = lowerbond(nums, target) 找到第一个大于等于 target 的位置。
    • 如果 start 超出数组范围或 nums[start] != target，说明 target 不在数组中。

  3. 结束位置：

    • end = lowerbond(nums, target + 1) - 1 找到第一个大于等于 target + 1 的位置，然后减 1，得到最后一个等于 target 的位置。
    • 这种技巧避免了单独处理 target 的结束位置，代码更简洁。

  4. 边界情况：

    • 数组为空：lowerbond 返回 0，start == len(nums) 成立，返回 [-1, -1]。
    • 目标值不存在：start 指向第一个大于 target 的位置，nums[start] != target 成立，返回 [-1, -1]。
    • 目标值在数组开头或结尾：lowerbond 能正确处理边界情况。