企业官网建设流程全解析

剑指 Offer 11：用二分查找定位旋转数组最小数字（LeetCode-Book 图解与三语言源码解析）

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇围绕《剑指 Offer》第 11 题“旋转数组的最小数字”，讲解如何用二分法将线性遍历优化到对数级别：先建立“旋转点”与左/右排序数组的几何直觉，再逐条分析nums[m]与nums[j]比较时的三种分支、严格论证nums[m] == nums[j]时执行j -= 1的正确性，最后结合仓库中 Python、Java、C++ 两套可运行解法源码（含退化特例的线性兜底方案）给出完整实现与复杂度结论。

一、问题本质：寻找“旋转点”

设原始排序数组经过“旋转”操作后得到输入数组 $nums$（文档中把 $numbers$ 缩写为 $nums$）。数组被旋转点 $x$ 切分为两段：

• 左排序数组：$nums[0 \dots x-1]$，元素递增且整体较大；
• 右排序数组：$nums[x \dots n-1]$，元素递增且整体较小。

寻找旋转数组的最小元素，即为寻找右排序数组的首个元素 $nums[x]$，称 $x$ 为旋转点。例如nums = [3, 4, 5, 1, 2]中旋转点 $x = 3$，最小值为nums[3] = 1；而nums = [1, 2, 3, 4, 5]（未旋转或整轮旋转）中 $x = 0$，最小值就是首元素。

排序数组上的查找问题首先考虑二分法：它能把遍历法的 $O(N)$ 线性时间复杂度降至 $O(\log N)$ 对数级别。

二、算法流程：i、j 双指针 + 三分支二分

设 $i, j$ 双指针分别指向数组左右两端，每轮取中点 $m = (i + j) // 2$（//为向下取整除法，因此恒有 $i \leq m < j$）。核心判断是把$nums[m]$ 与右端点 $nums[j]$ 比较，分三种情况收缩区间：

当 $i = j$ 时跳出循环，返回旋转点的值$nums[i]$。

这一逻辑在仓库 Python 解法 sfo_11_find_minimum_in_rotated_sorted_array_s1.py 中逐行对应：

class Solution: def minArray(self, numbers: List[int]) -> int: i, j = 0, len(numbers) - 1 while i < j: m = (i + j) // 2 if numbers[m] > numbers[j]: i = m + 1 elif numbers[m] < numbers[j]: j = m else: j -= 1 return numbers[i]

仓库中的驱动代码使用测试用例numbers = [3, 4, 5, 1, 2]直接运行验证（该文件末尾自带 Test Case 与 Driver Code，执行后输出1）。

三、正确性证明：为什么nums[m] == nums[j]时执行j -= 1是安全的

当 $nums[m] = nums[j]$ 时，无法判定 $m$ 在哪个排序数组，若强行二分（比如按常规置 $i = m + 1$ 或 $j = m$），旋转点 $x$ 可能不再落在区间 $[i, j]$ 内。文档给出了两个反例说明“此时 $m$ 的归属不确定”：

设两个旋转点值为 $0$ 的示例数组，当 $i = 0, j = 4$ 时 $m = 2$，结果却不同：

• 示例一[1, 0, 1, 1, 1]：旋转点 $x = 1$，$m = 2$ 在右排序数组中；
• 示例二[1, 1, 1, 0, 1]：旋转点 $x = 3$，$m = 2$ 在左排序数组中。

而证明j = j - 1的缩小区间安全性，需分两种情况讨论：

1. 当 $x < j$ 时：执行 $j = j - 1$ 后，旋转点 $x$ 仍在区间 $[i, j]$ 内，二分安全性不受影响；
2. 当 $x = j$ 时：执行 $j = j - 1$ 后会越过（丢失）旋转点 $x$，但最终返回的元素值 $nums[i]$ 仍等于旋转点值 $nums[x]$。推导链条如下：
   • 由于 $x = j$，因此 $nums[x] = nums[j] = nums[m] \leq nums[i]$；
   • 又由于 $i \leq m < j$ 恒成立，因此有 $m < x$，即此时 $m$ 一定在左排序数组中，从而 $nums[m] \geq nums[i]$；
   • 综合两点推出 $nums[i] = nums[m]$，且区间 $[i, m]$ 内所有元素值相等：

$$ nums[i] = nums[i+1] = \cdots = nums[m] = nums[x] $$

此时虽然丢失了旋转点 $x$，但之后区间 $[i, j]$ 只包含左排序数组，继续二分下去返回的一定是本轮的 $nums[i]$，而它与 $nums[x]$ 相等。

结论：该方法保证返回值 $nums[i]$ 等于旋转点值 $nums[x]$，但在少数特例下 $i \neq x$；而题目只要求返回“旋转点的值”，因此本方法正确。

四、补充思考：为什么不用nums[m]与nums[i]比较？

二分的目的是判断 $m$ 在哪个排序数组中，从而缩小区间。看似“与左端点比较”更自然，但在 $nums[m] > nums[i]$ 情况下无法判断 $m$ 归属，其本质是：$j$ 的初始值 $n-1$ 一定在右排序数组中（旋转后尾部必属于较小值段），而 $i$ 的初始值 $0$ 无法确定在哪个排序数组中——只有右端点是“可靠锚点”。文档给出反例：

对于以下两示例，当 $i = 0, j = 4, m = 2$ 时均有nums[m] > nums[i]，而 $m$ 的归属却不同：

• [1, 2, 3, 4, 5]，旋转点 $x = 0$：$m$ 在右排序数组（该示例只有右排序数组）；
• [3, 4, 5, 1, 2]，旋转点 $x = 3$：$m$ 在左排序数组。

这解释了为什么三语言实现（如 Java 版 s1 解法、C++ 版 s1 解法）全部以 $nums[j]$ 作为比较基准，而不是 $nums[i]$。

五、三语言参考实现（s1 解法：j 左移）

以下为仓库中与文档主解法一一对应的三语言源码，均可直接编译运行（Python 通过 include/init.py 统一引入List等类型，C++ 通过../include/include.hpp引入标准头文件，Java 通过include.*引入公共依赖）：

Python—— sfo_11_find_minimum_in_rotated_sorted_array_s1.py：

class Solution: def minArray(self, numbers: List[int]) -> int: i, j = 0, len(numbers) - 1 while i < j: m = (i + j) // 2 if numbers[m] > numbers[j]: i = m + 1 elif numbers[m] < numbers[j]: j = m else: j -= 1 return numbers[i]

Java—— sfo_11_find_minimum_in_rotated_sorted_array_s1.java：

class Solution { public int minArray(int[] numbers) { int i = 0, j = numbers.length - 1; while (i < j) { int m = (i + j) / 2; if (numbers[m] > numbers[j]) i = m + 1; else if (numbers[m] < numbers[j]) j = m; else j--; } return numbers[i]; } }

C++—— sfo_11_find_minimum_in_rotated_sorted_array_s1.cpp：

class Solution { public: int minArray(vector<int>& numbers) { int i = 0, j = numbers.size() - 1; while (i < j) { int m = (i + j) / 2; if (numbers[m] > numbers[j]) i = m + 1; else if (numbers[m] < numbers[j]) j = m; else j--; } return numbers[i]; } };

六、变体（s2 解法）：退化为线性查找

文档指出：当出现 $nums[m] = nums[j]$ 时，一定有区间 $[i, m]$ 内所有元素相等或区间 $[m, j]$ 内所有元素相等（或两者皆满足）。对于寻找此类数组的最小值问题，可以直接放弃二分查找，改用线性查找兜底——命中相等分支时直接在 $[i, j)$ 中扫描最小值并返回。

对应仓库 sfo_11_find_minimum_in_rotated_sorted_array_s2.py：

class Solution: def minArray(self, numbers: List[int]) -> int: i, j = 0, len(numbers) - 1 while i < j: m = (i + j) // 2 if numbers[m] > numbers[j]: i = m + 1 elif numbers[m] < numbers[j]: j = m else: return min(numbers[i:j]) return numbers[i]

Java / C++ 版（见 sfo_11_find_minimum_in_rotated_sorted_array_s2.cpp）则用显式循环扫描numbers[i+1 .. j-1]求最小下标x后返回numbers[x]，与 Python 的min(numbers[i:j])语义一致。

两种策略的取舍：

• s1（j -= 1）：实现最短、无额外分支，最坏情况（如[1, 1, 1, 1]）逐位左移退化为 $O(N)$，但常数极小；
• s2（线性兜底）：命中相等分支时一次扫描直达答案，逻辑更直观，代价同样是 $O(N)$ 最坏情况。

七、复杂度分析

• 时间复杂度 $O(\log_2 N)$：常规情况下每轮二分区间减半；在特例情况（例如[1, 1, 1, 1]大量重复）下，s1 会因反复执行j -= 1退化到 $O(N)$，s2 则在该分支下以一次线性扫描终止，同为 $O(N)$ 最坏界。
• 空间复杂度 $O(1)$：仅 $i$、$j$、$m$ 三个指针变量使用常数级额外空间，s2 解法的线性扫描也未引入额外结构。

八、小结与延伸阅读

本主题的关键要点可归纳为三点：① 旋转数组的最小值 = 右排序数组首元素（旋转点值）；② 二分必须与“必在右排序数组”的右端点 $nums[j]$ 比较，而非左端点；③ 相等分支下j -= 1虽可能在个别特例丢失旋转点下标，但返回值仍恒等于旋转点值，方法整体正确。

同一算法家族在仓库中还有多处可对照学习：二分思想见 剑指 Offer 11 原文档，类似“旋转/有序结构上的二分”可延伸对照 剑指 Offer 53 - I. 在排序数组中查找数字 I；剑指 Offer 全量题目与分类导航可参考 剑指 Offer 刷题计划 与 剑指 Offer 题目分类，以及仓库内的 LCR 121. 寻找目标值 - 二维数组 等同类查找题，形成“有序结构 + 二分”的完整知识链。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book