为何用lo索引实现旋转数组二分找最小值需额外条件？

问题描述 #

给定一个长度为n的升序排序数组，该数组被旋转了1到n次。例如，数组nums = [0,1,2,4,5,6,7]可能变为：
若旋转4次，数组变为[4,5,6,7,0,1,2]；
若旋转7次，数组变为[0,1,2,4,5,6,7]。
注意，将数组[a[0], a[1], a[2], ..., a[n-1]]旋转1次的结果为[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
给定元素唯一的旋转有序数组nums，返回数组中的最小元素。
你必须编写时间复杂度为O(log n)的算法。

示例 #

• 示例1：
  输入：nums = [3,4,5,1,2]
  输出：1
  解释：原数组[1,2,3,4,5]旋转了3次。
• 示例2：
  输入：nums = [4,5,6,7,0,1,2]
  输出：0
  解释：原数组[0,1,2,4,5,6,7]旋转了4次。
• 示例3：
  输入：nums = [11,13,15,17]
  输出：11
  解释：原数组[11,13,15,17]旋转了4次。

约束条件 #

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums中的所有整数互不相同。
nums是升序排序且旋转了1到n次的数组。

初始正确解法（基于hi索引判断区间） #

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1, mid = -1;
        if(nums[lo] <= nums[hi]) return nums[lo]; // 处理单元素数组和未旋转数组，无需进入循环。单元素数组首尾元素相等，符合判断条件。
        
        while(lo <= hi){
            mid = (lo + hi) >>> 1; // 计算mid索引
            if(mid > 0 && nums[mid] < nums[mid - 1]) return nums[mid];
            if(nums[mid] < nums[hi]) hi = mid - 1; // 用hi索引确定正确的查找区间
            else lo = mid + 1;
        }
        return -1;
    }
}

失效的解法（改用lo索引判断区间，无额外条件） #

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1, mid = -1;
        if(nums[lo] <= nums[hi]) return nums[lo];

        while(lo <= hi){
            mid = (lo + hi) >>> 1;
            if(mid > 0 && nums[mid] < nums[mid - 1]) return nums[mid];
            if(nums[mid] < nums[lo]) hi = mid - 1; // 最小元素在mid左侧
            else lo = mid + 1; // 否则最小元素在mid右侧
        }
        return -1;
    }
}

该代码在测试用例[4,5,6,7,0,1,2]中无法返回正确结果0。

修正后的正确解法（添加额外条件） #

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1, mid = -1;
        if(nums[lo] <= nums[hi]) return nums[lo];

        while(lo <= hi){
            mid = (lo + hi) >>> 1;
            if(mid - 1 >= 0 && nums[mid] < nums[mid - 1]) return nums[mid];
            else if( mid + 1 <= hi && nums[mid] > nums[mid + 1]) return nums[mid + 1]; // 新增的额外条件，之前的实现不需要该条件

            else if(nums[mid] < nums[lo]) hi = mid - 1; // 注意此处使用nums[lo]
            else lo = mid + 1;
        }
        return -1;
    }
}

失效原因解析 #

我们以测试用例nums = [4,5,6,7,0,1,2]为例，逐步分析失效代码的执行过程：

1. 初始状态：lo=0，hi=6，nums[lo]=4 <= nums[hi]=2不成立，进入循环。
2. 第一次循环：
   • mid=(0+6)>>>1=3，nums[mid]=7。
   • 检查mid>0 && nums[mid]<nums[mid-1]：7 < 6不成立。
   • 判断nums[mid] < nums[lo]：7 < 4不成立，执行lo=mid+1=4。
3. 第二次循环：
   • lo=4，hi=6，mid=(4+6)>>>1=5，nums[mid]=1。
   • 检查mid>0 && nums[mid]<nums[mid-1]：1 < 0不成立。
   • 判断nums[mid] < nums[lo]：1 < 0不成立，执行lo=mid+1=6。
4. 第三次循环：
   • lo=6，hi=6，mid=6，nums[mid]=2。
   • 检查mid>0 && nums[mid]<nums[mid-1]：2 < 1不成立。
   • 判断nums[mid] < nums[lo]：2 < 2不成立，执行lo=mid+1=7。
5. 循环结束（lo>hi），返回-1，结果错误。

核心问题 #

在基于lo的判断逻辑中，当nums[mid] >= nums[lo]时，我们默认最小元素在mid右侧，但这个结论不严谨：

• 旋转后的数组分为两段升序区间，前半段所有元素都大于后半段。
• 当mid刚好是前半段的最后一个元素（比如测试用例中的mid=3，对应元素7），此时nums[mid] >= nums[lo]成立，但最小元素就在mid的下一个位置（0）。代码执行lo=mid+1后，后续循环无法触发nums[mid] < nums[mid-1]的判断（因为当mid指向0时，mid-1=3，nums[0]=0 < nums[3]=7成立，但此时循环已经走到lo=6，错过了这个判断时机）。

而基于hi的判断逻辑中，nums[mid] < nums[hi]说明mid落在后半段，最小元素在左侧；否则在前半段，这个判断逻辑是严谨的——后半段所有元素都小于前半段，不会出现“踩在分界点”导致的遗漏。

额外条件的作用 #

新增的else if(mid + 1 <= hi && nums[mid] > nums[mid + 1]) return nums[mid + 1]条件，专门处理了mid是前半段最后一个元素的情况：此时nums[mid]是前半段最大值，nums[mid+1]是后半段最小值，直接返回即可，避免了后续循环的错误区间调整。

内容的提问来源于stack exchange，提问作者John Doe