CS-Notes 剑指 Offer 11 解析：旋转数组的最小数字与二分查找变体

本文基于 CS-Notes 仓库 notes/11. 旋转数组的最小数字.md 展开，系统讲解"在旋转后的非递减数组中查找最小元素"这一经典面试题的完整解法：为什么可以套用二分、nums[m] <= nums[h] 这一核心判断的来龙去脉、允许重复元素时退化为顺序查找的原因，以及对应的 Java 实现与边界情况。读完本文，你将能够独立推导并手写出该问题的 O(log₂N) 二分解法，并正确处理重复元素的最坏情形。

一、题目背景：什么是"旋转数组"

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例如 {1, 2, 3, 4} 旋转后可能得到 {2, 3, 4, 1}，此时最小元素 1 恰好是被搬到末尾的那"一段"的头部：

这个定义意味着输入数组具有一个关键性质：它一定可以看成两个非递减数组首尾拼接，例如 [2, 3] + [1] 或 [3, 4, 5] + [1, 2]。拼接点处会出现全数组唯一的"下降沿"（前一个元素大于后一个元素的位置），而最小元素正好位于下降沿之后。这个"两段拼接"的结构正是后续可以折半搜索的根基。

二、为什么可以折半：问题规模的 O(log₂N) 减半

将旋转数组对半分，可以得到：

• 一个包含最小元素的新旋转数组（问题规模的"递归主体"）；
• 一个非递减排序的数组（可以直接丢弃）。

新旋转数组的长度是原数组的一半，问题规模每轮减半，这正是二分法 O(log₂N) 时间复杂度的来源：

此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组，哪一个是非递减数组。原文档给出的判据是：非递减数组的第一个元素一定小于等于最后一个元素。反过来，"首元素 > 尾元素"的区间必然被下降沿切开，一定包含最小元素。

三、核心判断：nums[m] <= nums[h] 的推导

注意判据是拿 nums[m] 和 nums[h]（high 端）比较，而不是和 nums[l] 比较——因为左端 l 处可能是"大段"的头部，参考 nums[l] 无法区分 m 落在哪一段。设 l 代表 low、m 代表 mid、h 代表 high，则规则为：

• 当 nums[m] <= nums[h] 时：[m, h] 区间首元素 ≤ 尾元素，说明该区间是非递减数组，最小元素不可能在 (m, h] 内部，只能位于 m 或其左侧，因此此时令 h = m（m 本身保留为候选答案）；
• 否则（nums[m] > nums[h]）：[m, h] 区间内部必然存在下降沿，最小元素位于 [m + 1, h]，此时令 l = m + 1。

循环以 l < h 为条件，收敛后 l == h，指向的即最小元素。

无重复元素时的完整解法

public int minNumberInRotateArray(int[] nums) {
    if (nums.length == 0)
        return 0;
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] <= nums[h])
            h = m;
        else
            l = m + 1;
    }
    return nums[l];
}

用 {3, 4, 5, 1, 2} 手工推演一遍，验证收敛过程：

轮次	l	m	h	nums[m] vs nums[h]	操作
1	0	2	4	nums[2]=5 > nums[4]=2	l = 3
2	3	3	4	nums[3]=1 <= nums[4]=2	h = 3
结束	3	—	3	l == h，返回 nums[3]=1	—

两点实现细节值得注意：

1. 空数组时直接 return 0，这是原文档定义的兜底行为（实际工程中也可以改成抛出异常或返回约定值，但要与题目约定保持一致）；
2. 计算中点使用 l + (h - l) / 2 而不是 (l + h) / 2，可避免两端点下标之和溢出的隐患。

复杂度：时间 O(log₂N)（每轮排除一半区间），空间 O(1)。

四、允许重复元素：退化到顺序查找的特殊情况

如果数组元素允许重复，会出现一个特殊的情况：nums[l] == nums[m] == nums[h]。此时无法通过首尾比较判断 [l, h] 中哪一段是旋转数组——例如对于数组 {1, 1, 1, 0, 1}，l、m 和 h 指向的数都为 1，二分无法知道最小数字 0 在哪个区间，此时必须切换到顺序查找：

public int minNumberInRotateArray(int[] nums) {
    if (nums.length == 0)
        return 0;
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[l] == nums[m] && nums[m] == nums[h])
            return minNumber(nums, l, h);
        else if (nums[m] <= nums[h])
            h = m;
        else
            l = m + 1;
    }
    return nums[l];
}

private int minNumber(int[] nums, int l, int h) {
    for (int i = l; i < h; i++)
        if (nums[i] > nums[i + 1])
            return nums[i + 1];
    return nums[l];
}

辅助函数 minNumber 的查找逻辑同样利用了"下降沿"性质：在 [l, h] 内线性扫描，找到第一个满足 nums[i] > nums[i + 1] 的位置，nums[i + 1] 就是最小值；如果一路扫描都没找到下降沿，说明整个区间本身就是非递减的，最小值即 nums[l]。

以 {1, 1, 1, 0, 1} 为例：初始 l=0, h=4, m=2，三处取值都是 1，触发顺序查找分支；从 i=0 开始扫描，到 i=2 时发现 nums[2]=1 > nums[3]=0，返回 nums[3]=0，结果正确。

复杂度：此版本最坏情况下（如三个端点频繁相等，区间无法有效折半）会退化为 O(N)；平均情况下仍是 O(log₂N)。这是"允许重复"这一条件带来的理论下限，无法用纯二分避免。

五、与 LeetCode 153 的对应关系

仓库中 notes/Leetcode 题解 - 二分查找.md 的第 5 节收录了同一题型的 LeetCode 版本——Find Minimum in Rotated Sorted Array（LeetCode 153），输入示例为 Input: [3,4,5,1,2], Output: 1，给出的解法与本节核心算法完全一致：

public int findMin(int[] nums) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] <= nums[h]) {
            h = m;
        } else {
            l = m + 1;
        }
    }
    return nums[l];
}

对比可见，剑指 Offer 版本只是在 LeetCode 153 的框架上增加了两处适配：空数组的兜底返回，以及重复元素时切换到 minNumber 顺序查找。两题共用同一套"比较 mid 与 high 端"的判定规则，这也是该题型在二分查找专题中被归类在一起的原因。本篇在仓库剑指 Offer 题解目录中的入口可参见 notes/剑指 Offer 题解 - 目录.md。

六、易错点清单

• 比较端点选错：判据必须用 nums[m] <= nums[h]。若误用 nums[m] <= nums[l]，当 m 落在右段（小值段）时会错误地把 l 向 m 靠拢，可能跳过最小元素；
• h = m 还是 h = m - 1：nums[m] <= nums[h] 成立时 m 本身可能是最小元素（例如整个数组未旋转的退化情形，最小值就是 nums[0]），所以必须 h = m 而不能 h = m - 1；相应地，else 分支里 nums[m] 必然大于右端元素，不可能是答案，因此可以安全地 l = m + 1；
• 未旋转数组的退化输入：如 {1, 2, 3, 4}，循环中始终满足 nums[m] <= nums[h]，h 一路收缩到 0，正确返回 nums[0]=1；
• 单元素数组：进入循环前 l == h，直接跳出并返回该元素，逻辑无需特判；
• 重复元素分支不可省略：nums[l] == nums[m] == nums[h] 时若强行折半，在 {1, 1, 1, 0, 1} 这类输入上会得到错误答案，因此该分支必须整体切换到线性扫描。

小结

"旋转数组的最小数字"是二分查找变体的典型样本：利用"旋转数组 = 两段非递减拼接"的结构性质，以 nums[m] <= nums[h] 为判据每轮排除一半区间，达到 O(log₂N) 的时间复杂度；允许重复元素时，nums[l] == nums[m] == nums[h] 会破坏判据的确定性，此时退化为 O(N) 的顺序查找是该约束下的正确处理。上述完整推导、Java 实现与边界分析均可在 notes/11. 旋转数组的最小数字.md 中对照查阅。