在旋转排序数组中高效查找目标值的完整教程

本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段搜索”的逻辑缺陷，并提供标准的单次二分解决方案，附带可运行示例与关键边界分析。

本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段搜索”的逻辑缺陷，并提供标准的单次二分解决方案，附带可运行示例与关键边界分析。

在旋转排序数组（如 [3,4,5,6,7,0,1,2]）中查找目标值，不能简单套用普通二分查找，也不能依赖“先定位峰值、再分两段搜索”的策略——因为该策略存在两个致命隐患：峰值定位不鲁棒（如数组无严格峰值或全等元素），且分段后二分区间判断缺失对目标值分布的动态验证，导致右半段（如 peak+1 到 length-1）的搜索可能跳过实际解。

原代码中 peak_ele() 方法虽能找出最大值索引（即旋转点前一位），但其循环终止条件 while(start < end) 在 start == end 时退出，返回 end 是正确的；问题核心在于后续调用 bs(arr, target, peak+1, arr.length-1) 时，未校验该区间是否真正有序且可能包含目标值。例如，当 target = 1 时，峰值为 4（对应元素 7），右半段为 [0,1,2]，看似合理——但 bs() 函数本身是标准升序二分，而它被错误地应用于一个未做有效性预判的子区间：若目标值实际位于左段（如 target=5），右段搜索必然失败并返回 -1，此时程序不会回退重试，直接输出错误结果。

更本质、更高效的解法是：不显式寻找峰值，而在每次二分中动态判断哪一侧有序，并据此收缩搜索范围。核心思想是——旋转数组任一中点 mid 必将数组划分为「一侧严格有序、另一侧可能旋转」的两部分。通过比较 nums[start] 与 nums[mid] 即可判定左半是否有序：

• 若 nums[start] <= nums[mid]：左半 [start, mid] 有序 → 检查 target 是否落在该有序区间内（即 nums[start] <= target < nums[mid]），是则搜索左半，否则搜右半；
• 否则（nums[start] > nums[mid]）：右半 [mid, end] 有序 → 检查 target 是否落在 nums[mid] < target <= nums[end] 内，是则搜右半，否则搜左半。

该逻辑覆盖所有边界，时间复杂度稳定为 O(log n)，且无需额外峰值扫描。

以下是修正后的完整可运行代码：

public class SearchInRotatedSortedArray {
    public static int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // 左半部分有序
            if (nums[start] <= nums[mid]) {
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } 
            // 右半部分有序
            else {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 6, 7, 0, 1, 2};
        int target = 1;
        int index = search(arr, target);
        System.out.println("Index of " + target + " is " + index); // 输出：6
    }
}

✅ 关键注意事项：

• nums[start] <= nums[mid] 中的等号不可省略，用于处理只有两个元素（如 [2,1]）或单元素数组的边界；
• 区间判断必须严格匹配有序侧的上下界（如左有序时用 target < nums[mid] 而非 <=，因 == 已在上一步被排除）；
• 不需要单独处理 nums[mid] == nums[start] 的重复情况（本题默认无重复），如有重复需额外去重逻辑；
• 初始化检查 nums == null || nums.length == 0 提升健壮性。

总结：旋转数组搜索的本质不是“还原秩序”，而是“利用局部有序性做决策”。摒弃分治式峰值预处理，转而采用一次遍历中的动态有序判断，才是简洁、正确、高性能的标准解法。