You need to enable JavaScript to run this app. 基于二分查找模板2求解旋转数组最小值的代码报错与逻辑问题排查
优惠活动
大模型
产品
解决方案
定价
更多

基于二分查找模板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不符

核心逻辑缺陷

  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,因为右边界被持续左收,永远无法触达数组最右侧的元素。
  2. 边界设置与访问逻辑不匹配
    代码采用开区间写法初始化right = nums.length,但未限制mid的取值范围:一旦mid计算到nums.length - 1,访问nums[mid+1]就会触发数组越界。之前的正常测试样例没有暴露这个问题,只是巧合让mid没有取到最后一个索引,本质上这个访问逻辑不安全。
  3. 未利用旋转数组的核心性质
    旋转数组由两段连续递增序列组成,唯一的相邻降序对位置就是最大值点,其后的相邻元素就是最小值。代码虽然在寻找这个降序对,但没有通过“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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 07:24:02