基于二分查找模板2求解旋转数组最小值的代码报错与逻辑问题排查
LeetCode 153 寻找旋转排序数组最小值 代码问题定位
题目说明
给定经过1到n次右旋转的无重复元素升序数组,返回数组中的最小元素。
约束条件:
- 数组长度范围:
1 <= n <= 5000 - 数组元素范围:
-5000 <= nums[i] <= 5000 - 数组所有元素互不重复
当前提交的代码
public int findMin(int[] nums) { if(nums == null || nums.length == 0) { return -1; } if(nums.length == 1) return nums[0]; if(nums.length == 2) { return (nums[0] > nums[1])? nums[1]:nums[0]; } int left = 0; int right = nums.length; while(left < right) { int mid = left + (right - left)/2; if(nums[mid] > nums[mid + 1]) { return nums[mid + 1]; } else if(nums[mid] < nums[mid + 1]) { right = mid; } } if(left != nums.length) { return nums[left]; } return -1; }
现存问题
- 无前置边界判断时,输入长度为1的数组
[1]会触发ArrayIndexOutOfBoundsException:计算得到mid=0后直接访问nums[1]越界 - 补充长度1、2的边界判断后,输入
[2,3,4,5,1]时错误返回2,和正确结果1不符
核心逻辑缺陷
- 二分收缩方向完全错误
代码只要检测到nums[mid] < nums[mid+1](相邻递增),就将右边界收缩到mid。这个逻辑会直接丢弃所有右侧可能存在最小值的区域。
以输入[2,3,4,5,1]为例的执行流:- 初始
left=0, right=5,mid=2(值4 < 相邻5),right收缩为2 - 下一轮
left=0, right=2,mid=1(值3 < 相邻4),right收缩为1 - 下一轮
left=0, right=1,mid=0(值2 < 相邻3),right收缩为0,循环终止
最终返回nums[0]=2,全程没有访问到数组末尾的最小值1,因为右边界被持续左收,永远无法触达数组最右侧的元素。
- 初始
- 边界设置与访问逻辑不匹配
代码采用开区间写法初始化right = nums.length,但未限制mid的取值范围:一旦mid计算到nums.length - 1,访问nums[mid+1]就会触发数组越界。之前的正常测试样例没有暴露这个问题,只是巧合让mid没有取到最后一个索引,本质上这个访问逻辑不安全。 - 未利用旋转数组的核心性质
旋转数组由两段连续递增序列组成,唯一的相邻降序对位置就是最大值点,其后的相邻元素就是最小值。代码虽然在寻找这个降序对,但没有通过“mid位置与右边界元素的大小关系”判断降序对所在的区间,导致收缩方向完全错误。
适配二分模板II的修正方向
保留模板II的开区间结构(right = nums.length),将判断逻辑从“比较mid和相邻元素”改为“比较mid位置元素与右边界对应元素”:
- 当
nums[mid] > nums[right - 1],说明mid处于左侧的递增大值区,最小值在mid右侧,设置left = mid + 1 - 否则,说明mid处于右侧的递增小值区,最小值在mid或mid左侧,设置
right = mid
循环终止时left == right,对应位置的元素就是数组最小值,全程不会出现越界访问问题。
内容的提问来源于stack exchange,提问作者user2755407
相关产品推荐
相关产品推荐

