忍者算法

Appearance

探秘旋转数组：寻找最小值的巧妙之旅！ ​

大家好，我是忍者算法。今天我们要一起探讨一道非常有意思的题目 - LeetCode 153「寻找旋转排序数组中的最小值」。这道题是我们之前讨论的搜索旋转排序数组的姐妹题，同样需要我们以创新的方式运用二分查找。

📚 从日出日落说起 ​

让我们用一个生动的比喻来理解今天的问题：想象一下太阳从东边升起，温度逐渐升高，到正午达到最高点，然后开始下降，直到日落。如果我们从某个时刻开始记录温度，到第二天同一时刻结束，这些温度数据就形成了一个"旋转"的有序序列。找出最低温度，就像我们要在旋转排序数组中找最小值！

💡 问题解析 ​

题目要求： 假设一个按升序排序的数组在未知的某个点上进行了旋转（例如，[0,1,2,4,5,6,7] 旋转成了 [4,5,6,7,0,1,2]）。请找出其中的最小元素。注意数组中不包含重复元素。

示例：

java
输入：nums = [3,4,5,1,2]
输出：1  // 1是数组中的最小值

输入：nums = [4,5,6,7,0,1,2]
输出：0  // 0是数组中的最小值

🤔 思路发展历程 ​

1. 朴素思路 ​

遍历一遍数组找最小值。这个方法虽然直观，但时间复杂度是O(n)，没有充分利用数组的特性。

2. 优化思路 ​

仔细观察旋转后的数组，我们会发现一个重要特点：最小值一定位于数组的"断崖"处——也就是前一个数比后一个数大的位置。这启发我们可以用二分查找来寻找这个位置。

🚀 优雅的解决方案 ​

java
class Solution {
    public int findMin(int[] nums) {
        // 特判：空数组或只有一个元素
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        if (nums.length == 1) {
            return nums[0];
        }
        
        // 如果数组没有旋转，直接返回第一个元素
        if (nums[0] < nums[nums.length - 1]) {
            return nums[0];
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            // 如果区间只剩一个元素，它就是最小值
            if (left == right) {
                return nums[left];
            }
            
            int mid = left + (right - left) / 2;
            
            // 如果中间元素大于它的下一个元素，说明找到了"断崖"
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            
            // 如果中间元素小于它的前一个元素，说明它就是最小值
            if (mid > 0 && nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            
            // 判断最小值在哪一侧
            if (nums[mid] > nums[0]) {
                // 最小值在右侧
                left = mid + 1;
            } else {
                // 最小值在左侧
                right = mid - 1;
            }
        }
        
        // 正常情况下不会执行到这里
        return nums[0];
    }
}

📝 代码详解 ​

让我们深入理解这个解决方案的每个细节：

1. 前置判断 ​

我们首先处理了几个特殊情况：

  • 空数组或单元素数组
  • 数组未发生旋转的情况（通过比较首尾元素判断）

2. 二分查找的核心逻辑 ​

每次二分，我们都做三个关键判断：

  1. 是否找到"断崖"：

    • 如果 nums[mid] > nums[mid + 1]，说明找到了旋转点
    • nums[mid + 1] 就是最小值

  2. 是否是最小值：

    • 如果 nums[mid - 1] > nums[mid]，说明 mid 就是最小值

  3. 确定搜索方向：

    • 通过比较 nums[mid] 和 nums[0] 确定最小值在哪一侧
    • 如果 nums[mid] > nums[0]，说明左半部分是有序的，最小值在右侧
    • 否则最小值在左侧

🎯 易错点剖析 ​

  1. 边界处理

    • 注意数组为空或只有一个元素的情况
    • 处理数组未旋转的特殊情况

  2. 区间选择

    • 比较时要注意数组越界
    • mid 和 mid+1 的比较要在数组范围内

  3. 终止条件

    • 仔细处理 left == right 的情况
    • 确保不会陷入死循环

💡 举一反三 ​

这道题的思路可以应用到多个类似场景：

  1. 寻找旋转排序数组中的最大值

    • 只需稍微修改判断条件

  2. 判断数组是否是旋转排序数组

    • 可以利用类似的性质判断

  3. 处理包含重复元素的情况

    • LeetCode 154 题就是这个问题的进阶版

🌟 面试技巧 ​

  1. 思路解释

    • 先解释为什么普通的二分查找不能直接用
    • 说明如何利用旋转数组的特性

  2. 代码优化

    • 展示对边界情况的全面考虑
    • 解释代码的每个关键判断

  3. 性能分析

    • 解释为什么时间复杂度是 O(log n)
    • 比较不同解法的优劣

🎨 图解演示 ​

为了帮助大家更好地理解算法的执行过程，我绘制了一个直观的示意图：

svg
<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>

作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #二分查找 #数组

通过这篇文章，我们不仅学会了如何在旋转排序数组中查找最小值，更重要的是理解了如何灵活运用二分查找来解决变体问题。这种思维方式对于解决其他算法问题也很有帮助。如果你对这个题目还有任何疑问，欢迎在评论区讨论！