1. 问题背景与核心需求这道题目要求我们在一个非递减顺序排列的整数数组中找到给定目标值的开始位置和结束位置。如果目标值不存在于数组中则返回 [-1, -1]。题目要求算法时间复杂度必须为 O(log n)这意味着我们必须使用二分查找的变种来实现。在实际开发中这种需求非常常见。比如在日志分析系统中我们需要快速定位某个特定错误码的所有出现记录在电商系统中需要查询某个价格区间的所有商品。理解这个二分查找的变种实现对提升算法能力很有帮助。2. 标准二分查找的局限性常规的二分查找在找到目标值后就会立即返回这无法满足我们需要找到边界位置的需求。例如在数组 [5,7,7,8,8,10] 中查找8标准二分可能返回索引3或4但我们实际上需要的是[3,4]。这里的关键在于当mid位置的值等于target时我们不能直接返回而是需要继续向左或向右搜索以确定真正的边界位置。这就引出了左边界查找和右边界查找两个变种算法。3. 左边界查找实现3.1 算法思路左边界查找的目标是找到第一个等于target的元素位置。具体实现时当nums[mid] target时我们继续在左半部分搜索(right mid)当nums[mid] target时搜索右半部分(left mid 1)当nums[mid] target时搜索左半部分(right mid)3.2 代码实现def find_left_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left注意这里right初始化为len(nums)而不是len(nums)-1这样可以处理target大于所有数组元素的情况。4. 右边界查找实现4.1 算法思路右边界查找的目标是找到最后一个等于target的元素位置。具体实现时当nums[mid] target时我们继续在右半部分搜索(left mid 1)当nums[mid] target时搜索右半部分(left mid 1)当nums[mid] target时搜索左半部分(right mid)4.2 代码实现def find_right_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left - 15. 完整解决方案5.1 组合左右边界查找将上述两个函数组合起来就能得到完整的解决方案def searchRange(nums, target): left_idx find_left_bound(nums, target) if left_idx len(nums) or nums[left_idx] ! target: return [-1, -1] return [left_idx, find_right_bound(nums, target)]5.2 边界条件处理需要特别注意以下几种边界情况空数组输入target小于数组所有元素target大于数组所有元素target存在于数组中但只有1个target存在于数组中且有多个6. 算法复杂度分析6.1 时间复杂度两次二分查找每次都是O(log n)因此总时间复杂度为O(log n)满足题目要求。6.2 空间复杂度只使用了常数级别的额外空间O(1)。7. 常见问题与调试技巧7.1 死循环问题二分查找容易出现死循环特别是在处理边界条件时。确保每次迭代区间都在缩小检查left和right的更新是否正确验证循环终止条件是否完备7.2 索引越界特别注意right的初始值设置和返回值的处理右边界查找返回left-1时要确保不会越界检查左边界查找结果是否有效7.3 测试用例建议建议测试以下典型情况常规情况[5,7,7,8,8,10], target8 → [3,4]目标不存在[5,7,7,8,8,10], target6 → [-1,-1]单个元素[1], target1 → [0,0]空数组[], target0 → [-1,-1]全部相同[2,2,2], target2 → [0,2]8. 实际应用场景这种边界查找的二分变种在实际工程中有广泛应用日志系统中查询某个时间段内的所有日志数据库中范围查询的索引优化监控系统中查找某个指标超出阈值的时段版本控制系统中定位某个特性的引入时间范围理解这个算法不仅对面试有帮助更能提升解决实际工程问题的能力。我在处理大规模日志分析时就多次用到这种技巧相比线性扫描能带来数百倍的性能提升。