忍者算法

Appearance

探秘旋转数组：二分查找的华丽转身！ ​

大家好，我是忍者算法。今天要和大家分享一道特别有趣的题目 - LeetCode 33「搜索旋转排序数组」。这道题巧妙地将二分查找与旋转数组结合，是一道考察思维灵活性的经典题目。

📚 从时钟说起 ​

想象你在看一个圆形时钟，如果把时钟的12点位置当作起点，顺时针记录1到12这些数字，这就是一个有序序列。现在，如果我们把时钟的指针从8点开始读数，到12点，再到7点，实际上就形成了一个"旋转"后的有序序列：8,9,10,11,12,1,2,3,4,5,6,7。这正是我们今天要处理的"旋转排序数组"！

💡 问题解析 ​

题目要求： 给你一个整数数组 nums ，它原本是一个升序排序的数组，但在某个位置进行了旋转。现在给你一个目标值 target，请你在数组中搜索 target。如果存在则返回它的下标，否则返回 -1。

示例：

java
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4  // 0在位置4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1  // 3不存在于数组中

🤔 思路发展历程 ​

1. 初学者思路 ​

最简单的方法是直接遍历数组。虽然可以解决问题，但时间复杂度为O(n)，没有利用数组的特殊性质。

2. 进阶思路 ​

既然原数组是有序的，只是被旋转了，那么旋转后的数组会有一个重要特性：它被分成了两个有序的部分。我们可以利用这个特性，结合二分查找来解决。

🚀 优雅的解决方案 ​

java
class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断哪一部分是有序的
            if (nums[left] <= nums[mid]) {  // 左半部分有序
                if (target >= nums[left] && target < nums[mid]) {
                    // target在左半部分
                    right = mid - 1;
                } else {
                    // target在右半部分
                    left = mid + 1;
                }
            } else {  // 右半部分有序
                if (target > nums[mid] && target <= nums[right]) {
                    // target在右半部分
                    left = mid + 1;
                } else {
                    // target在左半部分
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
}

📝 代码详解 ​

让我们来剖析这个解决方案的精妙之处：

1. 核心思想 ​

  • 虽然整个数组不是有序的，但是分成两半后，必定有一半是有序的
  • 通过判断哪一半有序，我们可以确定目标值在哪一半

2. 关键步骤 ​

  1. 找到有序部分

    • 比较 nums[left] 和 nums[mid]
    • 如果 nums[left] <= nums[mid]，左半部分有序
    • 否则右半部分有序

  2. 判断目标值位置

    • 如果左半部分有序，判断 target 是否在区间 [nums[left], nums[mid]] 内
    • 如果右半部分有序，判断 target 是否在区间 [nums[mid], nums[right]] 内

  3. 调整搜索范围

    • 根据判断结果，调整 left 或 right 指针
    • 持续缩小搜索范围

🎯 易错点剖析 ​

  1. 边界条件

    • while 循环的条件是 left <= right
    • 注意处理空数组的情况

  2. 区间判断

    • 判断区间时要考虑等号
    • nums[left] <= nums[mid] 而不是

  3. 范围收缩

    • 在有序部分中判断时要注意区间端点
    • 收缩区间时不要漏掉或多包含元素

💡 举一反三 ​

这类问题的思路可以扩展到其他场景：

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

    • 类似的二分思路，但判断条件不同

  2. 旋转排序数组是否包含重复元素

    • 需要考虑重复元素带来的影响

  3. 在部分有序的数组中查找元素

    • 可以利用类似的"先确定有序部分"的思路

🌟 面试技巧 ​

  1. 清晰的分析过程

    • 先画图理解数组的特点
    • 分析不同情况下的处理方法

  2. 代码的鲁棒性

    • 处理好边界情况
    • 考虑输入的各种可能性

  3. 优化意识

    • 说明为什么选择二分查找
    • 分析时间复杂度的优势

🎨 图解算法 ​

为了帮助大家更好地理解，我来画个示意图：

svg
<svg viewBox="0 0 800 300" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="300" fill="#f8f9fa"/>
  
  <!-- 数组框架 -->
  <g transform="translate(50,50)">
    <!-- 数组元素框 -->
    <rect x="0" y="0" width="700" height="60" fill="none" stroke="#333" stroke-width="2"/>
    <line x1="100" y1="0" x2="100" y2="60" stroke="#333" stroke-width="2"/>
    <line x1="200" y1="0" x2="200" y2="60" stroke="#333" stroke-width="2"/>
    <line x1="300" y1="0" x2="300" y2="60" stroke="#333" stroke-width="2"/>
    <line x1="400" y1="0" x2="400" y2="60" stroke="#333" stroke-width="2"/>
    <line x1="500" y1="0" x2="500" y2="60" stroke="#333" stroke-width="2"/>
    <line x1="600" y1="0" x2="600" y2="60" stroke="#333" stroke-width="2"/>
    
    <!-- 数组值 -->
    <text x="50" y="35" text-anchor="middle" font-size="20">4</text>
    <text x="150" y="35" text-anchor="middle" font-size="20">5</text>
    <text x="250" y="35" text-anchor="middle" font-size="20">6</text>
    <text x="350" y="35" text-anchor="middle" font-size="20">7</text>
    <text x="450" y="35" text-anchor="middle" font-size="20">0</text>
    <text x="550" y="35" text-anchor="middle" font-size="20">1</text>
    <text x="650" y="35" text-anchor="middle" font-size="20">2</text>
    
    <!-- 指针标注 -->
    <text x="50" y="85" text-anchor="middle" font-size="16" fill="#1e88e5">left</text>
    <text x="350" y="85" text-anchor="middle" font-size="16" fill="#e91e63">mid</text>
    <text x="650" y="85" text-anchor="middle" font-size="16" fill="#1e88e5">right</text>
  </g>
  
  <!-- 旋转点说明 -->
  <path d="M 400,140 Q 450,140 450,170" fill="none" stroke="#666" stroke-width="2" marker-end="url(#arrow)"/>
  <text x="500" y="160" font-size="16">旋转点</text>
  
  <!-- 有序区间标注 -->
  <g transform="translate(50,200)">
    <path d="M 0,20 H 300" stroke="#4caf50" stroke-width="3" marker-end="url(#arrow)"/>
    <text x="150" y="45" text-anchor="middle" font-size="16" fill="#4caf50">左半部分有序</text>
    
    <path d="M 400,20 H 700" stroke="#ff9800" stroke-width="3" marker-end="url(#arrow)"/>
    <text x="550" y="45" text-anchor="middle" font-size="16" fill="#ff9800">右半部分有序</text>
  </g>
  
  <!-- 箭头标记定义 -->
  <defs>
    <marker id="arrow" viewBox="0 0 10 10" refX="5" refY="5"
        markerWidth="6" markerHeight="6" orient="auto-start-reverse">
      <path d="M 0 0 L 10 5 L 0 10 z" fill="#666"/>
    </marker>
  </defs>
</svg>

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