搜索旋转排序数组：二分在非单调序列上的深度应用

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 18 分钟 | 难度：⭐⭐⭐

---

开篇故事

面试的时候，有一道题我被问到过不止一次：给你一个旋转过的有序数组，用 O(log n) 找到目标值。

第一次被问到这道题，我用了最笨的办法，先二分找到旋转点，再在两段有序区间里分别二分。面试官没说这不行，但他问了一句："能不能一次扫描完成？"我愣在那里。

后来我花了整整一个下午，把这道题吃透了。旋转数组的二分查找，表面上看是"数组不是单调的，二分不能用"，但实际上，数组虽然整体不单调，但任意一段 [left, mid] 或者 [mid, right]，必定有一段是有序的。利用这个性质，二分依然可以精确地丢弃一半的元素。

这道题教会了我一件事：二分查找的本质不是"数组单调"，而是"每次能否丢弃一半的元素"。只要你能判断目标值不在某一半，就能二分。

---

一、题目解析

题目（LeetCode 33）： 整数数组 nums 按升序排列，所有值互不相同。但 nums 在某个未知的旋转点 k 处被旋转，旋转后变成 [nums[k], nums[k+1], ..., nums[n-1], nums[0], ..., nums[k-1]]。给定旋转后的数组和 target，返回 target 的下标，不存在则返回 -1。

要求时间复杂度 O(log n)。

示例：

• 输入：nums = [4,5,6,7,0,1,2]，target = 0，输出：4
• 输入：nums = [4,5,6,7,0,1,2]，target = 3，输出：-1

关键观察： 对任意 mid，[left, mid] 和 [mid+1, right] 中，至少有一段是有序的（即单调递增的）。可以用 nums[left] <= nums[mid] 来判断左半段是否有序。

---

二、解法一：先找旋转点，再双段二分

思路分析

第一步用二分找到旋转点（即最小值的下标），将数组逻辑上分成两段有序数组。第二步判断 target 落在哪段，再在那段上二分查找。

这种方法逻辑清晰，但需要调用两次二分，代码量稍多。

完整代码

public class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        // 第一步：找最小值下标（旋转点）
        int pivot = findMinIndex(nums);

        // 第二步：判断 target 在哪段
        if (target >= nums[pivot] && target <= nums[n - 1]) {
            // target 在右段 [pivot, n-1]
            return binarySearch(nums, pivot, n - 1, target);
        } else {
            // target 在左段 [0, pivot-1]
            return binarySearch(nums, 0, pivot - 1, target);
        }
    }

    private int findMinIndex(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;  // 最小值在右半段
            } else {
                right = mid;     // 最小值在左半段（含 mid）
            }
        }
        return left;
    }

    private int binarySearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(sol.search(nums, 0)); // 4
        System.out.println(sol.search(nums, 3)); // -1
    }
}

复杂度分析

• 时间复杂度：O(log n)。两次二分，每次 O(log n)。
• 空间复杂度：O(1)。

---

三、解法二：一次扫描二分（判断有序段）

思路分析

核心思路：每次计算 mid 后，判断 [left, mid] 是否有序。

若左半段有序（nums[left] <= nums[mid]）：

• 如果 target 在 [nums[left], nums[mid]) 内，则目标在左半段，令 right = mid - 1。
• 否则目标在右半段，令 left = mid + 1。

若右半段有序（nums[mid] < nums[left]）：

• 如果 target 在 (nums[mid], nums[right]] 内，则目标在右半段，令 left = mid + 1。
• 否则目标在左半段，令 right = mid - 1。

这样一次扫描就能完成搜索，代码更简洁。

完整代码

public class Solution2 {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

            // 判断左半段 [left, mid] 是否有序
            if (nums[left] <= nums[mid]) {
                // 左半段有序
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;  // target 在左半段
                } else {
                    left = mid + 1;   // target 在右半段
                }
            } else {
                // 右半段有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;   // target 在右半段
                } else {
                    right = mid - 1;  // target 在左半段
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Solution2 sol = new Solution2();
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(sol.search(nums1, 0)); // 4
        System.out.println(sol.search(nums1, 3)); // -1

        int[] nums2 = {1};
        System.out.println(sol.search(nums2, 0)); // -1
        System.out.println(sol.search(nums2, 1)); // 0

        int[] nums3 = {3, 1};
        System.out.println(sol.search(nums3, 1)); // 1
    }
}

复杂度分析

• 时间复杂度：O(log n)。每次循环搜索范围减半。
• 空间复杂度：O(1)。

---

四、解法三最优：统一边界处理 + 完整注释

思路分析

解法二已经很好了，但很多人在写的时候，因为条件判断较多，容易写错。这里给出一个更有系统性的写法，把所有情况整理成表格，然后翻译成代码。

整体框架：

• 每次循环，先判断左半段是否有序（以 nums[left] <= nums[mid] 为判断条件）
• 判断 target 是否在有序的那半段内
• 据此更新 left 或 right

为什么用 nums[left] <= nums[mid] 而不是 <？ 因为当 left == mid（数组只有两个元素时）时，nums[left] == nums[mid]，左半段只有一个元素，认为它是有序的，处理逻辑依然正确。

Mermaid 图：旋转数组二分决策流程

完整代码

public class Solution3 {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

            if (isLeftSorted(nums, left, mid)) {
                // 左半段 [left, mid] 有序
                if (inRange(target, nums[left], nums[mid] - 1)) {
                    // target 在左半段的有效范围内（严格小于 nums[mid]，因为 nums[mid] 已排除）
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右半段 [mid, right] 有序
                if (inRange(target, nums[mid] + 1, nums[right])) {
                    // target 在右半段的有效范围内（严格大于 nums[mid]，因为 nums[mid] 已排除）
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    private boolean isLeftSorted(int[] nums, int left, int mid) {
        return nums[left] <= nums[mid];
    }

    private boolean inRange(int target, int lo, int hi) {
        return target >= lo && target <= hi;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();

        // 标准测试
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(sol.search(nums1, 0)); // 4
        System.out.println(sol.search(nums1, 3)); // -1
        System.out.println(sol.search(nums1, 4)); // 0
        System.out.println(sol.search(nums1, 2)); // 6

        // 边界测试
        int[] nums2 = {1, 3};
        System.out.println(sol.search(nums2, 3)); // 1

        // 单元素
        int[] nums3 = {1};
        System.out.println(sol.search(nums3, 1)); // 0

        // 无旋转（正常有序）
        int[] nums4 = {1, 2, 3, 4, 5};
        System.out.println(sol.search(nums4, 3)); // 2
    }
}

复杂度分析

• 时间复杂度：O(log n)。每次循环，right - left 至少减少一半。
• 空间复杂度：O(1)。

---

五、举一反三：同类题与模板应用

这道题的核心思想——"在非完全单调的数组中，局部有序足以支撑二分"——在以下题目中都有体现：

题号	题目	关键点
81	搜索旋转排序数组 II	含重复元素，需要额外处理 nums[left] == nums[mid] 的情况
153	寻找旋转排序数组中的最小值	只需找旋转点，无需查找 target
154	寻找旋转排序数组中的最小值 II	含重复元素版
852	山脉数组的峰顶索引	先上升后下降，找到局部最大值

含重复元素的旋转数组（LeetCode 81）关键处理：

// 当 nums[left] == nums[mid] 时，无法判断哪半段有序，需要退化处理
if (nums[left] == nums[mid]) {
    left++;  // 缩小搜索范围，但可能退化到 O(n)
} else if (nums[left] < nums[mid]) {
    // 左半段有序，同 LeetCode 33
} else {
    // 右半段有序，同 LeetCode 33
}

---

六、踩坑实录

坑一：nums[left] <= nums[mid] 中的等号不能去掉

当 left == mid 时（数组只剩两个元素），nums[left] == nums[mid]，如果用严格的 <，会误判为右半段有序。而实际上左半段只有一个元素，当然是"有序"的。我第一次写这道题就踩了这个坑，导致两元素的测试用例失败。

坑二：条件判断顺序不能搞错

很多人把"判断有序段"和"判断 target 范围"的条件混写在一起，逻辑一乱就写错了。我的建议是：先把"哪段有序"判断清楚，再在有序段内判断 target 是否在范围内，这两步要清晰分离。

坑三：忘记处理 target == nums[mid] 的情况

这种情况应该直接返回，但有些人把这个判断放在了条件嵌套的里面，导致某些路径下没有被覆盖到。最安全的做法是在循环的最开始就先判断 nums[mid] == target，然后再进入有序判断逻辑。

坑四：无旋转的情况（数组本来就有序）

当旋转点为 0 时，数组其实没有旋转，nums[left] <= nums[mid] 始终成立。需要确认你的代码在这种情况下也能正确运行——事实上，上面的解法完全兼容这种情况，无需特殊处理。

坑五：旋转点就是 mid 的情况

比如 nums = [5, 1, 3]，mid = 1，nums[left] = 5 > nums[mid] = 1，所以判断右半段有序。右半段是 [1, 3]，有序正确。这种情况需要在脑子里跑一遍，确认逻辑没问题。

---

七、总结

旋转排序数组是二分查找在"不完全有序"场景下的经典扩展。解题关键是利用旋转数组的特性：任意一次二分，左右两半中必有一半是严格有序的，利用这半边进行范围判断，就能确定 target 在哪侧，从而执行二分收缩。

对于面试来说，推荐解法二（一次扫描），它是最简洁、最常见的写法。但理解解法一（先找旋转点）有助于将这道题分解成两个更简单的子问题，逻辑更透明。

记住这个核心原则：二分的关键不是"数组是否有序"，而是"能否在每步丢弃一半的搜索空间"。 这个原则在后续的二分答案、峰值查找等题目中都会反复用到。