二分查找篇——在排序数组中查找元素的第一个和最后一个位置【LeetCode】
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，具有高效、简洁、稳定的特点，是解决有序数组中查找范围类问题的经典解法之一，非常适合作为面试准备的重点内容。