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

题目链接

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

题目描述

给定一个非递减排序的整数数组 nums 和目标值 target，找出 target 在数组中的起始位置和结束位置。若数组中无 target，返回 [-1, -1]。要求时间复杂度为 O(log n)（二分查找）。

三种解法对比分析

三种解法均基于二分查找找下界的核心思路：通过查找 target 的下界（第一个 ≥ target 的位置）确定起始索引，通过查找 target + 1 的下界确定结束索引（结束索引 = target + 1 的下界 - 1）。差异主要体现在二分查找的边界处理细节上。

解法一：循环条件 l <= r（经典二分）

from typing import Listclass Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 下界查找：寻找第一个 >= t 的位置 def lower_bound(l: int, r: int, t: int) -> int: while l <= r: # 循环条件：左边界 <= 右边界 m = (l + r) // 2 if nums[m] >= t:  r = m - 1 # 中间值 >= 目标，收缩右边界（跳过m） else:  l = m + 1 # 中间值 < 目标，收缩左边界（跳过m） return l # 循环结束时 l > r，l 为目标位置 # 查找起始位置：范围为 [0, len(nums)-1]（数组有效索引范围） start = lower_bound(0, len(nums) - 1, target) # 验证起始位置有效性 if start == len(nums) or nums[start] != target: return [-1, -1] # 查找结束位置：target + 1 的下界 - 1 end = lower_bound(start, len(nums) - 1, target + 1) - 1 return [start, end]

核心特点

1. 循环条件：l <= r，当 l > r 时退出循环，是最经典的二分查找循环条件。
2. 边界设置：初始范围为 [0, len(nums)-1]（数组有效索引范围），符合“索引在数组内”的直觉。
3. 收缩逻辑：
   • 若 nums[m] >= t：右边界收缩至 m - 1（跳过 m，后续通过 l 还原）。
   • 若 nums[m] < t：左边界收缩至 m + 1（跳过 m）。
4. 返回值：l（此时 l > r，l 必为第一个 ≥ t 的位置）。
5. 越界处理：需额外判断 start == len(nums)（目标大于所有元素时的越界情况）。

解法二：循环条件 l < r

from typing import Listclass Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 下界查找：寻找第一个 >= t 的位置 def lower_bound(l: int, r: int, t: int) -> int: while l < r: # 循环条件：左边界 < 右边界 m = (l + r) // 2 if nums[m] >= t:  r = m # 中间值 >= 目标，收缩右边界（保留m） else:  l = m + 1 # 中间值 < 目标，收缩左边界（跳过m） return l # 循环结束时 l == r，即为目标位置 # 查找起始位置：范围为 [0, len(nums)]（右边界为数组长度，处理越界） start = lower_bound(0, len(nums), target) # 验证起始位置有效性 if start == len(nums) or nums[start] != target: return [-1, -1] # 查找结束位置：target + 1 的下界 - 1 end = lower_bound(start, len(nums), target + 1) - 1 return [start, end]

核心特点

1. 循环条件：l < r，当 l == r 时退出循环，避免死循环。
2. 边界设置：初始范围为 [0, len(nums)]（右边界为数组长度，而非 len(nums)-1），天然处理“目标大于所有元素”的越界情况。
3. 收缩逻辑：
   • 若 nums[m] >= t：右边界收缩至 m（保留 m 作为候选，因为可能是第一个 ≥ t 的位置）。
   • 若 nums[m] < t：左边界收缩至 m + 1（m 不可能是目标，直接跳过）。
4. 返回值：l（此时 l == r，必为第一个 ≥ t 的位置）。

解法三：循环条件 l + 1 < r（开区间处理）

from typing import Listclass Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 下界查找：寻找第一个 >= t 的位置（开区间风格） def lower_bound(l: int, r: int, t: int) -> int: while l + 1 < r: # 循环条件：左右边界不相邻 m = (l + r) // 2 if nums[m] >= t:  r = m # 中间值 >= 目标，收缩右边界 else:  l = m # 中间值 < 目标，收缩左边界 return r # 循环结束时 l 和 r 相邻，r 为目标位置 # 查找起始位置：范围为 (-1, len(nums))（左边界为-1，右边界为数组长度） start = lower_bound(-1, len(nums), target) # 验证起始位置有效性 if start == len(nums) or nums[start] != target: return [-1, -1] # 查找结束位置：target + 1 的下界 - 1 end = lower_bound(start, len(nums), target + 1) - 1 return [start, end]

核心特点

1. 循环条件：l + 1 < r（左右边界不相邻），当 l 和 r 相邻时退出循环，避免复杂边界判断。
2. 边界设置：初始范围为 (-1, len(nums))（左边界为 -1，右边界为 len(nums)），将所有可能的结果包在开区间内，更符合“二分查找范围包含目标”的直觉。
3. 收缩逻辑：
   • 若 nums[m] >= t：右边界收缩至 m。
   • 若 nums[m] < t：左边界收缩至 m（不跳过 m，因为循环条件保证最终会收敛）。
4. 返回值：r（此时 l 和 r 相邻，r 必为第一个 ≥ t 的位置）。

三种解法对比分析

维度 解法一（l <= r） 解法二（l < r） 解法三（l + 1 < r） 循环条件 l <= r（l > r 时退出） l < r（相等时退出） l + 1 < r（相邻时退出） 初始范围 [0, len(nums)-1] [0, len(nums)] (-1, len(nums)) 收缩逻辑 跳过 m（l/r = m ± 1） 保留可能的 m（r = m） 不跳过 m（l = m 或 r = m） 返回值 l（l > r） l（l == r） r（l 和 r 相邻） 越界处理 需要额外判断（start == len(nums)） 天然支持（右边界为 len(nums)） 天然支持（范围包含所有可能） 直观性 高（经典二分范围） 中等（右边界非索引） 较高（开区间包围目标） 适用场景 入门级二分查找教学 大多数二分查找场景 复杂边界的二分查找

正确性验证（边界情况）

测试用例 解法一 解法二 解法三 预期结果 nums = [], target = 0 [-1,-1] [-1,-1] [-1,-1] [-1,-1] nums = [1], target = 1 [0,0] [0,0] [0,0] [0,0] nums = [1,3], target = 2 [-1,-1] [-1,-1] [-1,-1] [-1,-1] nums = [5,7,7,8,8,10], target = 8 [3,4] [3,4] [3,4] [3,4] nums = [2,2], target = 2 [0,1] [0,1] [0,1] [0,1]

总结

三种解法均通过二分查找下界实现 O(log n) 时间复杂度，核心差异在于边界处理细节：

• 解法一（l <= r）是最经典的二分查找实现，逻辑清晰，适合入门理解，但需额外处理越界。
• 解法二（l < r）通过调整循环条件和范围，天然支持越界处理，实用性强，是工程中常用的写法。
• 解法三（l + 1 < r）通过开区间范围处理边界，逻辑严谨，适合复杂边界场景，但理解成本稍高。

实际应用中，三种方法均可正确解决问题，选择取决于个人对二分查找边界的理解习惯。核心是掌握“下界查找”的本质：找到第一个满足 nums[i] >= target 的位置，进而推导出目标值的起始和结束范围。