1. 题目解析理解问题本质这道力扣第65题要求我们在一个非递减排列的数组中查找给定目标值的第一个和最后一个出现位置。题目看似简单但考察的是对二分查找算法的深入理解和灵活运用能力。举个例子给定数组 [5,7,7,8,8,10] 和目标值 8我们需要返回 [3,4]因为8第一次出现在索引3最后一次出现在索引4。如果目标值不存在于数组中则返回 [-1,-1]。注意题目明确要求算法的时间复杂度必须是 O(log n) 级别这意味着我们不能简单地遍历整个数组来查找目标值。2. 算法选择与思路分析2.1 为什么选择二分查找面对有序数组的查找问题二分查找是最自然的选择。标准的二分查找可以在 O(log n) 时间内确定目标值是否存在但本题需要的是目标值的起始和结束位置这需要对标准二分查找进行一些调整。2.2 双二分查找策略解决这个问题的核心思路是先找到目标值的第一个出现位置左边界再找到目标值的最后一个出现位置右边界我们可以通过修改二分查找的条件判断来实现这两个功能。具体来说查找左边界时当中间值等于目标值时我们继续向左搜索查找右边界时当中间值等于目标值时我们继续向右搜索3. 详细实现步骤3.1 查找左边界的实现def find_left(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return left这个实现的关键点在于当 nums[mid] target 时我们仍然执行 right mid - 1继续向左搜索循环结束时left 指向的就是目标值的第一个出现位置如果存在3.2 查找右边界的实现def find_right(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return right这个实现的区别在于当 nums[mid] target 时我们执行 left mid 1继续向右搜索循环结束时right 指向的就是目标值的最后一个出现位置如果存在3.3 完整解决方案将两个函数组合起来并处理边界情况def searchRange(nums, target): left_idx find_left(nums, target) right_idx find_right(nums, target) if left_idx right_idx and right_idx len(nums) and nums[left_idx] target and nums[right_idx] target: return [left_idx, right_idx] return [-1, -1]4. 复杂度分析与优化4.1 时间复杂度分析我们执行了两次二分查找每次的时间复杂度都是 O(log n)因此总时间复杂度仍然是 O(log n)满足题目要求。4.2 空间复杂度分析算法只使用了常数级别的额外空间空间复杂度为 O(1)。4.3 可能的优化在某些情况下可以提前终止搜索如果在查找左边界时发现目标值不存在可以直接返回 [-1,-1]如果数组为空或目标值小于最小值/大于最大值也可以直接返回 [-1,-1]5. 常见问题与调试技巧5.1 边界条件处理常见的边界情况包括空数组目标值不存在于数组中目标值是数组的最小值或最大值数组中所有元素都等于目标值提示在编写代码时务必测试这些边界情况确保算法在各种情况下都能正确工作。5.2 二分查找的常见错误无限循环通常是由于循环条件或指针更新不正确导致的漏掉元素可能是因为指针更新时跳过了可能的解数组越界在访问 nums[mid] 前没有检查数组长度5.3 调试技巧打印中间值在循环中添加打印语句观察搜索过程小规模测试先用小数组测试验证算法逻辑边界测试专门测试边界情况6. 实际应用场景这种查找元素范围的算法在实际开发中有广泛应用例如日志系统中查找特定时间范围内的事件数据库中查询某个值在索引中的位置范围统计分析中确定某个值的分布区间7. 扩展思考7.1 其他变种问题查找小于目标值的最大元素查找大于目标值的最小元素查找最接近目标值的元素7.2 不同语言的实现差异虽然算法思想相同但不同语言的实现细节可能有所不同Java/C 需要注意整数溢出问题JavaScript 需要注意数组的动态特性Go 需要注意切片的使用方式8. 力扣刷题建议对于想要提高算法能力的开发者我建议先理解基础算法如二分查找的标准实现然后练习各种变种问题最后尝试在真实项目中应用这些算法这道题目是力扣热题100中的经典题目掌握它对于准备技术面试非常有帮助。在实际编写代码时我通常会先写出标准二分查找然后根据具体问题需求进行调整这样可以减少出错的可能性。