我来给你讲解 LeetCode 第 34 题「在排序数组中查找元素的第一个和最后一个位置」。

题目描述

给定一个按照升序排列的整数数组 nums 和一个目标值 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]

解题思路分析

第一步：理解问题本质

这个问题看似简单，但有几个重要特点：

1. 数组是有序的，这提示我们可以使用二分查找
2. 需要找到目标值的起始位置和结束位置
3. 要求 O(log n) 时间复杂度，意味着不能简单扫描整个数组

第二步：暴力解法 vs 优化解法

暴力解法：遍历整个数组，记录目标值第一次和最后一次出现的位置。

• 时间复杂度：O(n)
• 不符合题目要求

优化思路：由于数组有序，我们可以使用两次二分查找：

1. 第一次二分查找：找到目标值的第一个位置
2. 第二次二分查找：找到目标值的最后一个位置

第三步：详细解题步骤

步骤1：查找第一个位置（左边界）

我们要找到第一个等于 target 的元素位置：

def findFirst(nums, target):
    left, right = 0, len(nums) - 1
    first = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            first = mid        # 记录可能的位置
            right = mid - 1    # 继续在左半部分查找
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return first

关键理解：

• 当 nums[mid] == target 时，我们不直接返回，而是继续在左半部分查找
• 这样可以确保找到的是第一个出现的位置

步骤2：查找最后一个位置（右边界）

我们要找到最后一个等于 target 的元素位置：

def findLast(nums, target):
    left, right = 0, len(nums) - 1
    last = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            last = mid         # 记录可能的位置
            left = mid + 1     # 继续在右半部分查找
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return last

关键理解：

• 当 nums[mid] == target 时，继续在右半部分查找
• 这样可以确保找到的是最后一个出现的位置

第四步：完整解决方案

def searchRange(nums, target):
    if not nums:
        return [-1, -1]
    
    def findFirst(nums, target):
        left, right = 0, len(nums) - 1
        first = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                first = mid
                right = mid - 1  # 继续向左找
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return first
    
    def findLast(nums, target):
        left, right = 0, len(nums) - 1
        last = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                last = mid
                left = mid + 1   # 继续向右找
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return last
    
    first = findFirst(nums, target)
    last = findLast(nums, target)
    
    return [first, last]

第五步：复杂度分析

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

  • 进行了两次二分查找，每次 O(log n)
  • 总时间复杂度仍然是 O(log n)

• 空间复杂度：O(1)

  • 只使用了常数级别的额外空间

第六步：示例验证

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

查找第一个位置：

• 初始：left=0, right=5
• mid=2: nums[2]=7 < 8 → left=3
• mid=4: nums[4]=8 == 8 → 记录first=4，继续向左找：right=3
• mid=3: nums[3]=8 == 8 → 记录first=3，继续向左找：right=2
• 结束：第一个位置是3

查找最后一个位置：

• 初始：left=0, right=5
• mid=2: nums[2]=7 < 8 → left=3
• mid=4: nums[4]=8 == 8 → 记录last=4，继续向右找：left=5
• mid=5: nums[5]=10 > 8 → right=4
• 结束：最后一个位置是4

最终结果：[3, 4]

第七步：边界情况处理

1. 空数组：直接返回 [-1, -1]
2. 目标值不存在：两次查找都返回 -1
3. 只有一个目标值：first 和 last 相同
4. 所有元素都是目标值：first=0, last=len(nums)-1

这个解法巧妙地运用了二分查找的特性，在找到目标值后继续向特定方向搜索，从而准确定位边界位置。