1. 问题背景与核心需求这道算法题来自LeetCode第34题属于二分查找的经典变种。题目要求在一个已排序的整数数组中找出给定目标值的第一个和最后一个出现位置。如果目标值不存在于数组中则返回[-1, -1]。在实际开发中这类需求非常常见。比如日志系统中查询某个错误码首次和最后一次出现的时间戳用户行为分析中统计某个操作在时间序列上的起始和结束位置数据库查询结果中定位某个值的边界范围2. 算法设计思路解析2.1 暴力解法与优化空间最直观的解法是线性扫描从左到右遍历记录第一个等于target的位置继续遍历直到找到最后一个等于target的位置时间复杂度O(n)空间复杂度O(1)但题目给出的数组是有序的这提示我们可以使用二分查找进行优化。有序数组查找问题二分法通常能将时间复杂度降至O(log n)。2.2 二分查找的变形应用标准二分查找在找到目标值后会立即返回但我们需要找到边界位置。因此需要修改二分逻辑查找第一个等于target的位置当nums[mid] target时不立即返回继续向左半部分搜索直到确认mid是最左侧的target查找最后一个等于target的位置当nums[mid] target时不立即返回继续向右半部分搜索直到确认mid是最右侧的target3. 代码实现与细节分析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: right mid - 1 else: left mid 1 return left if left len(nums) and nums[left] target else -1关键点当nums[mid] target时继续向左搜索(right mid - 1)循环结束时left指向第一个等于target的位置需要检查left是否越界以及是否真的等于target3.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 if right 0 and nums[right] target else -1关键点当nums[mid] target时继续向右搜索(left mid 1)循环结束时right指向最后一个等于target的位置需要检查right是否越界以及是否真的等于target3.3 完整解决方案class Solution: def searchRange(self, nums: List[int], target: int) - List[int]: def find_left(): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left if left len(nums) and nums[left] target else -1 def find_right(): 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 if right 0 and nums[right] target else -1 return [find_left(), find_right()]4. 边界条件与测试用例4.1 必须考虑的边界情况空数组输入nums [], target 0 → [-1, -1]目标值不存在nums [1,2,3], target 4 → [-1, -1]单个元素匹配nums [1], target 1 → [0, 0]所有元素相同nums [2,2,2], target 2 → [0, 2]目标值在开头/结尾nums [1,2,2,3], target 1 → [0,0]4.2 测试用例验证def test_searchRange(): solution Solution() assert solution.searchRange([5,7,7,8,8,10], 8) [3,4] assert solution.searchRange([5,7,7,8,8,10], 6) [-1,-1] assert solution.searchRange([], 0) [-1,-1] assert solution.searchRange([1], 1) [0,0] assert solution.searchRange([2,2], 2) [0,1]5. 算法复杂度分析时间复杂度O(log n)两次二分查找每次都是O(log n)没有嵌套循环总体保持对数复杂度空间复杂度O(1)只使用了常数级别的额外空间递归实现的空间复杂度会是O(log n)因此推荐迭代写法6. 实际应用中的优化技巧提前终止优化if not nums: return [-1, -1] if target nums[0] or target nums[-1]: return [-1, -1]合并查找过程可以在一次二分查找中同时记录左右边界但代码会变得复杂可读性降低使用bisect模块(Python)import bisect left bisect.bisect_left(nums, target) right bisect.bisect_right(nums, target) - 1 return [left, right] if left right else [-1, -1]7. 常见错误与调试技巧7.1 典型错误模式无限循环终止条件写错while left right 可能导致漏判区间更新错误left mid 而不是 left mid 1边界判断错误未检查最终位置是否真的等于target数组越界访问nums[left] 可能超出索引范围重复计算在找到左边界后右边界可以从左边界开始搜索不必每次都从0开始7.2 调试方法打印中间状态print(fleft{left}, right{right}, mid{mid}, nums[mid]{nums[mid]})小数据测试用长度为1-3的数组测试更容易发现边界条件问题对比标准库用bisect模块的结果作为参照确保自定义实现的正确性8. 扩展思考与变种问题统计出现次数找到左右边界后出现次数 right - left 1时间复杂度仍为O(log n)模糊匹配查找第一个大于等于target的位置查找最后一个小于等于target的位置二维矩阵搜索在每行有序的矩阵中查找目标值范围可以结合行间二分和行内二分流数据场景数据以流形式到达无法随机访问需要调整算法设计思路在解决这类二分查找变种问题时核心是理解标准二分法的变通方式。记住关键原则在找到目标时不立即返回而是继续向目标方向搜索以确定边界位置。 
长河君 · 2026/10/14 0:26:09 · 阅读 1.2k 二分查找变种：在有序数组中查找目标值范围
1. 问题背景与核心需求这道算法题来自LeetCode第34题属于二分查找的经典变种。题目要求在一个已排序的整数数组中找出给定目标值的第一个和最后一个出现位置。如果目标值不存在于数组中则返回[-1, -1]。在实际开发中这类需求非常常见。比如日志系统中查询某个错误码首次和最后一次出现的时间戳用户行为分析中统计某个操作在时间序列上的起始和结束位置数据库查询结果中定位某个值的边界范围2. 算法设计思路解析2.1 暴力解法与优化空间最直观的解法是线性扫描从左到右遍历记录第一个等于target的位置继续遍历直到找到最后一个等于target的位置时间复杂度O(n)空间复杂度O(1)但题目给出的数组是有序的这提示我们可以使用二分查找进行优化。有序数组查找问题二分法通常能将时间复杂度降至O(log n)。2.2 二分查找的变形应用标准二分查找在找到目标值后会立即返回但我们需要找到边界位置。因此需要修改二分逻辑查找第一个等于target的位置当nums[mid] target时不立即返回继续向左半部分搜索直到确认mid是最左侧的target查找最后一个等于target的位置当nums[mid] target时不立即返回继续向右半部分搜索直到确认mid是最右侧的target3. 代码实现与细节分析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: right mid - 1 else: left mid 1 return left if left len(nums) and nums[left] target else -1关键点当nums[mid] target时继续向左搜索(right mid - 1)循环结束时left指向第一个等于target的位置需要检查left是否越界以及是否真的等于target3.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 if right 0 and nums[right] target else -1关键点当nums[mid] target时继续向右搜索(left mid 1)循环结束时right指向最后一个等于target的位置需要检查right是否越界以及是否真的等于target3.3 完整解决方案class Solution: def searchRange(self, nums: List[int], target: int) - List[int]: def find_left(): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left if left len(nums) and nums[left] target else -1 def find_right(): 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 if right 0 and nums[right] target else -1 return [find_left(), find_right()]4. 边界条件与测试用例4.1 必须考虑的边界情况空数组输入nums [], target 0 → [-1, -1]目标值不存在nums [1,2,3], target 4 → [-1, -1]单个元素匹配nums [1], target 1 → [0, 0]所有元素相同nums [2,2,2], target 2 → [0, 2]目标值在开头/结尾nums [1,2,2,3], target 1 → [0,0]4.2 测试用例验证def test_searchRange(): solution Solution() assert solution.searchRange([5,7,7,8,8,10], 8) [3,4] assert solution.searchRange([5,7,7,8,8,10], 6) [-1,-1] assert solution.searchRange([], 0) [-1,-1] assert solution.searchRange([1], 1) [0,0] assert solution.searchRange([2,2], 2) [0,1]5. 算法复杂度分析时间复杂度O(log n)两次二分查找每次都是O(log n)没有嵌套循环总体保持对数复杂度空间复杂度O(1)只使用了常数级别的额外空间递归实现的空间复杂度会是O(log n)因此推荐迭代写法6. 实际应用中的优化技巧提前终止优化if not nums: return [-1, -1] if target nums[0] or target nums[-1]: return [-1, -1]合并查找过程可以在一次二分查找中同时记录左右边界但代码会变得复杂可读性降低使用bisect模块(Python)import bisect left bisect.bisect_left(nums, target) right bisect.bisect_right(nums, target) - 1 return [left, right] if left right else [-1, -1]7. 常见错误与调试技巧7.1 典型错误模式无限循环终止条件写错while left right 可能导致漏判区间更新错误left mid 而不是 left mid 1边界判断错误未检查最终位置是否真的等于target数组越界访问nums[left] 可能超出索引范围重复计算在找到左边界后右边界可以从左边界开始搜索不必每次都从0开始7.2 调试方法打印中间状态print(fleft{left}, right{right}, mid{mid}, nums[mid]{nums[mid]})小数据测试用长度为1-3的数组测试更容易发现边界条件问题对比标准库用bisect模块的结果作为参照确保自定义实现的正确性8. 扩展思考与变种问题统计出现次数找到左右边界后出现次数 right - left 1时间复杂度仍为O(log n)模糊匹配查找第一个大于等于target的位置查找最后一个小于等于target的位置二维矩阵搜索在每行有序的矩阵中查找目标值范围可以结合行间二分和行内二分流数据场景数据以流形式到达无法随机访问需要调整算法设计思路在解决这类二分查找变种问题时核心是理解标准二分法的变通方式。记住关键原则在找到目标时不立即返回而是继续向目标方向搜索以确定边界位置。