153. 寻找旋转排序数组中的最小值#
今天我们要一起探讨一道非常有意思的题目 - LeetCode 153「寻找旋转排序数组中的最小值」。这道题是我们之前讨论的搜索旋转排序数组的姐妹题，同样需要我们以创新的方式运用二分查找。
📚 从日出日落说起#
让我们用一个生动的比喻来理解今天的问题：想象一下太阳从东边升起，温度逐渐升高，到正午达到最高点，然后开始下降，直到日落。如果我们从某个时刻开始记录温度，到第二天同一时刻结束，这些温度数据就形成了一个”旋转”的有序序列。找出最低温度，就像我们要在旋转排序数组中找最小值！
问题描述#
题目目标#
已知长度为 n 的数组 nums 按升序排列，数组中的值互不相同。在传入函数前，nums 在某个下标处发生旋转。请你找出并返回旋转后数组中的最小元素，要求时间复杂度为 O(log n)。
示例 1#
输入： nums = [3,4,5,1,2]
输出： 1
说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。
💡 问题解析#
题目要求： 假设一个按升序排序的数组在未知的某个点上进行了旋转（例如，[0,1,2,4,5,6,7] 旋转成了 [4,5,6,7,0,1,2]）。请找出其中的最小元素。注意数组中不包含重复元素。
示例：
// 示例1：数组在中间位置发生旋转
// 输入：nums = [3,4,5,1,2]
// 输出：1（最小值是 1）
// 示例2：数组旋转后最小值落在后半段
// 输入：nums = [4,5,6,7,0,1,2]
// 输出：0（最小值是 0）🤔 思路发展历程#
1. 朴素思路#
遍历一遍数组找最小值。这个方法虽然直观，但时间复杂度是O(n)，没有充分利用数组的特性。
2. 优化思路#
仔细观察旋转后的数组，我们会发现一个重要特点：最小值一定位于数组的”断崖”处——也就是前一个数比后一个数大的位置。这启发我们可以用二分查找来寻找这个位置。
🚀 优雅的解决方案#
class Solution {
public int findMin(int[] nums) {
// 边界处理1：空数组非法，按题意抛出异常
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("数组不能为空");
}
// 边界处理2：只有一个元素时，该元素就是最小值
if (nums.length == 1) {
return nums[0];
}
// 边界处理3：若首元素小于尾元素，说明数组整体仍然有序（未旋转）
if (nums[0] < nums[nums.length - 1]) {
return nums[0];
}
int left = 0; // 二分左边界（包含）
int right = nums.length - 1; // 二分右边界（包含）
// 在闭区间 [left, right] 内查找最小值（即旋转断点后一个元素）
while (left <= right) {
// 如果区间只剩一个元素，它必然是当前最小候选值
if (left == right) {
return nums[left];
}
int mid = left + (right - left) / 2; // 中点下标，防溢出写法
// 关键判断1：若 nums[mid] > nums[mid + 1]，说明 mid 是“断崖前”位置
// 那么断崖后的 nums[mid + 1] 就是全局最小值
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
// 关键判断2：若 nums[mid - 1] > nums[mid]，说明 mid 本身就是断崖后第一个元素
if (mid > 0 && nums[mid - 1] > nums[mid]) {
return nums[mid];
}
// 根据 nums[mid] 与 nums[0] 的关系，判断最小值在左侧还是右侧
if (nums[mid] > nums[0]) {
// mid 位于左侧有序段，最小值一定在右侧
left = mid + 1;
} else {
// mid 位于右侧有序段，最小值在左侧（含 mid 左边）
right = mid - 1;
}
}
// 理论上不会到达这里（前面应已返回），兜底返回首元素
return nums[0];
}
}📝 代码详解#
让我们深入理解这个解决方案的每个细节：
1. 前置判断#
我们首先处理了几个特殊情况：
- 空数组或单元素数组
- 数组未发生旋转的情况（通过比较首尾元素判断）
2. 二分查找的核心逻辑#
每次二分，我们都做三个关键判断：
-
是否找到”断崖”：
- 如果 nums[mid] > nums[mid + 1]，说明找到了旋转点
- nums[mid + 1] 就是最小值
-
是否是最小值：
- 如果 nums[mid - 1] > nums[mid]，说明 mid 就是最小值
-
确定搜索方向：
- 通过比较 nums[mid] 和 nums[0] 确定最小值在哪一侧
- 如果 nums[mid] > nums[0]，说明左半部分是有序的，最小值在右侧
- 否则最小值在左侧
🎯 易错点剖析#
-
边界处理
- 注意数组为空或只有一个元素的情况
- 处理数组未旋转的特殊情况
-
区间选择
- 比较时要注意数组越界
- mid 和 mid+1 的比较要在数组范围内
-
终止条件
- 仔细处理 left == right 的情况
- 确保不会陷入死循环
💡 举一反三#
这道题的思路可以应用到多个类似场景：
-
寻找旋转排序数组中的最大值
- 只需稍微修改判断条件
-
判断数组是否是旋转排序数组
- 可以利用类似的性质判断
-
处理包含重复元素的情况
- LeetCode 154 题就是这个问题的进阶版
🌟 面试技巧#
-
思路解释
- 先解释为什么普通的二分查找不能直接用
- 说明如何利用旋转数组的特性
-
代码优化
- 展示对边界情况的全面考虑
- 解释代码的每个关键判断
-
性能分析
- 解释为什么时间复杂度是 O(log n)
- 比较不同解法的优劣
🎨 图解演示#
为了帮助大家更好地理解算法的执行过程，我绘制了一个直观的示意图：
<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
<!-- 背景 -->
<rect width="800" height="400" fill="#f8f9fa"/>
<!-- 坐标轴 -->
<g transform="translate(50,350)">
<!-- X轴 -->
<line x1="0" y1="0" x2="700" y2="0" stroke="#333" stroke-width="2"/>
<!-- Y轴 -->
<line x1="0" y1="0" x2="0" y2="-300" stroke="#333" stroke-width="2"/>
<!-- 数据点和连线 -->
<polyline points="0,-100 100,-150 200,-200 300,-250 400,-50 500,-75 600,-90"
fill="none" stroke="#2196f3" stroke-width="3"/>
<!-- 最小值标记 -->
<circle cx="400" cy="-50" r="6" fill="#e91e63"/>
<text x="420" y="-40" font-size="14">最小值</text>
<!-- 二分查找过程 -->
<g stroke="#4caf50" stroke-width="2" stroke-dasharray="5,5">
<line x1="0" y1="-280" x2="700" y2="-280"/>
<line x1="350" y1="-280" x2="350" y2="0"/>
<text x="360" y="-270" fill="#4caf50" font-size="14">二分查找路径</text>
</g>
</g>
<!-- 说明文字 -->
<g transform="translate(50,50)">
<text x="0" y="0" font-size="16">查找过程：</text>
<text x="20" y="30" font-size="14">1. 比较中点值与两端</text>
<text x="20" y="60" font-size="14">2. 确定最小值所在区间</text>
<text x="20" y="90" font-size="14">3. 寻找"断崖"位置</text>
</g>
</svg>
通过这篇文章，我们不仅学会了如何在旋转排序数组中查找最小值，更重要的是理解了如何灵活运用二分查找来解决变体问题。这种思维方式对于解决其他算法问题也很有帮助。如果你对这个题目还有任何疑问，欢迎在评论区讨论！