34. 在排序数组中查找元素的第一个和最后一个位置
一、算法逻辑(逐步通顺讲解每一步思路)
该算法用于在一个升序排列的数组 nums 中查找某个目标值 target
的第一个出现的位置和最后一个出现的位置。
✅ 1️⃣ 定义 lower_bound 函数
def lower_bound(self, nums: List[int], target: int) -> int:left, right = -1, len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] >= target:right = midelse:left = midreturn right
- 这个函数返回的是第一个大于等于 target 的索引位置。
- 使用的是左闭右开区间
[left+1, right)
的二分写法,可以避免边界处理错误。 - 循环终止时,
right
就是第一个满足nums[right] >= target
的位置。
✅ 2️⃣ 查找目标值的起始位置
start = self.lower_bound(nums, target)
- 如果
nums[start] != target
或者start == len(nums)
,说明数组中不存在该元素,直接返回[-1, -1]
。
✅ 3️⃣ 查找目标值的结束位置
end = self.lower_bound(nums, target + 1) - 1
- 我们通过查找
target + 1
的第一个位置,再减 1,就得到了target
的最后一个位置。 - 因为数组是有序的,所以
target + 1
第一次出现之前的所有元素都是target
。
✅ 4️⃣ 返回结果
return [start, end]
二、核心点总结
✅ 利用两次二分查找精准定位范围
- 使用两次「lower_bound」分别找到起始位置和结束位置,避免了线性扫描,效率高。
✅ 巧妙的“target + 1”技巧
- 不需要额外编写一个 upper_bound 函数,只需将目标值加一,即可复用 lower_bound 找出右边界。
✅ 适合面试高频题型
- 本题是典型的二分查找变形题,考察对边界条件的理解和对二分思想的灵活运用。
✅ 可扩展性强
- 此种思路也可推广到其他变种问题,如:统计某数字在排序数组中出现的次数(剑指 Offer 题)等。
class Solution:def lower_bound(self, nums:List[int], target:int)-> int:left, right = -1, len(nums)while left+1 < right:mid = (left+right)//2if nums[mid]>=target:right = midelse:left = midreturn rightdef searchRange(self, nums: List[int], target: int) -> List[int]:start = self.lower_bound(nums, target)if start==len(nums) or nums[start] != target:return [-1,-1]end = self.lower_bound(nums, target+1)-1return [start, end]
三、时间复杂度分析
✅ 每次调用 lower_bound
是一个标准的二分查找过程:
- 时间复杂度为 O(log n)
✅ 整体算法执行了两次二分查找:
- 总体时间复杂度为 O(log n)
四、空间复杂度分析
✅ 整个过程中没有使用任何额外的数据结构:
- 所有变量都是常数级的局部变量
✅ 空间复杂度为 O(1)
✅ 总结一句话
这段算法通过两次二分查找定位目标值的起始与结束位置,巧妙利用 target + 1
技巧避免重复编写 upper_bound,具有高效、简洁、稳定的特点,是解决有序数组中查找范围类问题的经典解法之一,非常适合作为面试准备的重点内容。