旋转非递减数组起始索引查找：我的二分查找方案为何出错？

给定一个经k次旋转的非递减排序数组，找出其起始索引。例如数组{1,2,1,1}的起始索引为2。我自己实现了二分查找方案，但部分边界用例失效，希望找出代码中的问题。

原代码实现 #

public class bs {
   private int check(int[] nums) {
       int lo = 0, hi = nums.length-1;
       while(lo<hi) {
           int mid = lo + (hi - lo) / 2;
           if((mid==0 && nums[mid]<nums[nums.length-1]) || (mid!=0 && nums[mid]<nums[mid-1])) {
               lo = mid; break;
           } else if (nums[mid] > nums[hi]) {
               lo = mid + 1;
           } else if (nums[mid] < nums[hi]) {
               hi = mid;
           } else if (nums[mid] > nums[lo]) {
               lo = mid + 1;
           } else if (nums[mid] < nums[lo]) {
               hi = mid;
           } else {
               lo++;
           }
       }
       return lo;
   }


   public static void main(String[] args) {
       bs b = new bs();
       System.out.println("Actual :: " + b.check(new int[]{1, 2, 3, 4, 5}) + " Expected :: 0");
       System.out.println("Actual :: " + b.check(new int[]{6, 1, 1, 4, 5}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{1, 2, 1, 1}) + " Expected :: 2");
       System.out.println("Actual :: " + b.check(new int[]{1, 1, 2, 1}) + " Expected :: 3");
       System.out.println("Actual :: " + b.check(new int[]{10, 1, 1, 10}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{2,1}) + " Expected :: 1");
       System.out.println("Actual :: " + b.check(new int[]{4,6,9,9,10,13,13,14,14,14,15,15,15,15,16,16,18,18,19,20,20,22,22,22,24,25,25,27,27,28,28,31,31,33,34,36,36,36,39,40,41,41,42,42,44,47,50,52,53,53,55,55,56,63,63,70,71,72,72,74,76,76,77,79,80,80,80,81,84,84,85,85,88,88,89,89,89,90,91,92,93,93,94,94,94,96,97,97,97,97,98,99,99,100,1,1,1,2,2,4}) + " Expected :: 94");
   }
}

原代码的问题分析 #

1. 提前终止循环的逻辑错误
   当检测到nums[mid] < nums[mid-1]时，直接lo = mid; break;会导致循环提前终止，无法保证后续的二分收敛逻辑完成。虽然此时mid确实是起始点，但这种写法在某些场景下会因为break后的直接返回lo，忽略了循环未完全收敛的潜在问题。

2. 重复元素处理逻辑缺陷
   当nums[mid] == nums[hi] && nums[mid] == nums[lo]时，直接执行lo++会导致时间复杂度退化为O(n)，且可能跳过正确的起始点。比如测试用例{1,1,2,1}，这种线性移动会错过索引3的正确起始点。

3. 条件分支冗余且顺序不合理
   原代码中额外增加了nums[mid]与nums[lo]的比较分支，这属于冗余判断——通过nums[mid]与nums[hi]的比较已经可以覆盖所有二分收敛的场景，额外的分支会增加逻辑复杂度，甚至导致错误的分支跳转。

修正后的二分查找实现 #

public class bs {
    private int check(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            // 直接命中起始点的情况
            if ((mid == 0 && nums[mid] < nums[nums.length - 1]) || (mid != 0 && nums[mid] < nums[mid - 1])) {
                return mid;
            } else if (nums[mid] > nums[hi]) {
                // 起始点在右半区间
                lo = mid + 1;
            } else if (nums[mid] < nums[hi]) {
                // 起始点在左半区间（包含mid）
                hi = mid;
            } else {
                // 处理重复元素：先检查hi是否是起始点，再缩小右边界
                if (nums[hi] < nums[hi - 1]) {
                    return hi;
                }
                hi--;
            }
        }
        return lo;
    }

    public static void main(String[] args) {
        bs b = new bs();
        System.out.println("Actual :: " + b.check(new int[]{1, 2, 3, 4, 5}) + " Expected :: 0");
        System.out.println("Actual :: " + b.check(new int[]{6, 1, 1, 4, 5}) + " Expected :: 1");
        System.out.println("Actual :: " + b.check(new int[]{1, 2, 1, 1}) + " Expected :: 2");
        System.out.println("Actual :: " + b.check(new int[]{1, 1, 2, 1}) + " Expected :: 3");
        System.out.println("Actual :: " + b.check(new int[]{10, 1, 1, 10}) + " Expected :: 1");
        System.out.println("Actual :: " + b.check(new int[]{2,1}) + " Expected :: 1");
        System.out.println("Actual :: " + b.check(new int[]{4,6,9,9,10,13,13,14,14,14,15,15,15,15,16,16,18,18,19,20,20,22,22,22,24,25,25,27,27,28,28,31,31,33,34,36,36,36,39,40,41,41,42,42,44,47,50,52,53,53,55,55,56,63,63,70,71,72,72,74,76,76,77,79,80,80,80,81,84,84,85,85,88,88,89,89,89,90,91,92,93,93,94,94,94,96,97,97,97,97,98,99,99,100,1,1,1,2,2,4}) + " Expected :: 94");
    }
}

关键修正说明 #

1. 直接返回起始点
   当检测到符合起始点的条件时，直接返回mid，无需break后再返回lo，避免循环提前终止的逻辑漏洞。

2. 优化重复元素处理
   当nums[mid] == nums[hi]时，先检查hi是否为起始点，再逐步左移hi缩小范围，既保证二分查找的收敛性，又不会跳过正确的起始点。

3. 简化条件分支
   移除冗余的nums[mid]与nums[lo]的比较分支，仅通过nums[mid]与nums[hi]的比较完成二分收敛，降低逻辑复杂度。

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