🔍 LeetCode 系列：解决 4 道「搜索旋转排序数组」题 —— 二分查找的变形经典

旋转排序数组的问题是一类典型的二分查找变形题目。这类题目看似简单，却常常因为细节处理出错而导致调试困难。

本文一次性讲透这类问题，包括以下四道经典题：

• LeetCode 33. 搜索旋转排序数组（无重复）
• LeetCode 81. 搜索旋转排序数组 II（有重复）
• LeetCode 153. 寻找旋转排序数组中的最小值（无重复）
• LeetCode 154. 寻找旋转排序数组中的最小值 II（有重复）

📌 题目一：33. 搜索旋转排序数组

🔗 题目描述

给你一个整数数组 nums，它最初是按升序排列的，并经过一次旋转。给定一个目标值 target，若存在目标值返回其索引，否则返回 -1。

💡 解题思路

整体思路仍然是 二分查找，只是要结合旋转点的判断来决定查找方向。

1. 每次取中点 mid；
2. 判断哪一边是有序的；
3. 然后判断目标值是否落在有序区间内；
4. 缩小边界继续搜索。

✅ Go 代码实现

func search(nums []int, target int) int {
   
    left, right := 0, len(nums)-1

    for left <= right {
   
        mid := (left + right) / 2

        if nums[mid] == target {
   
            return mid
        }

        // 左边有序
        if nums[left] <= nums[mid] {
   
            if nums[left] <= target && target < nums[mid] {
   
                right = mid - 1
            } else {
   
                left = mid + 1
            }
        } else {
    // 右边有序
            if nums[mid] < target && target <= nums[right] {
   
                left = mid + 1
            } else {
   
                right = mid - 1
            }
        }
    }

    return -1
}

📌 题目二：81. 搜索旋转排序数组 II（含重复元素）

🔗 题目描述

本题与 33 题几乎相同，但 nums 中可能含有重复元素。

🧠 解题关键

在某些情况下，例如 [1, 0, 1, 1, 1]，中间值与左右值相同，这时无法确定哪边是有序的，我们只能跳过重复元素。

✅ Go 代码实现

func search(nums []int, target int) bool {
   
    left, right := 0, len(nums)-1

    for left <= right {
   
        mid := (left + right) / 2
        if nums[mid] == target {
   
            return true
        }

        if nums[left] == nums[mid] {
   
            left++
        } else if nums[left] < nums[mid] {
    // 左边有序
            if nums[left] <= target && target < nums[mid] {
   
                right = mid - 1
            } else {
   
                left = mid + 1
            }
        } else {
    // 右边有序
            if nums[mid] < target && target <= nums[right] {
   
                left = mid + 1
            } else {
   
                right = mid - 1
            }
        }
    }

    return false
}

📌 题目三：153. 寻找旋转排序数组中的最小值

🔗 题目描述

给你一个旋转排序数组，元素不重复。找到其中的最小值。

✨ 解题思路

旋转之后的数组，最小值一定出现在「无序」的部分。使用二分查找找「第一个小于右端点的数」。

✅ Go 代码实现

func findMin(nums []int) int {
   
    left, right := 0, len(nums)-1

    for left < right {
   
        mid := (left + right) / 2
        if nums[mid] > nums[right] {
   
            left = mid + 1
        } else {
   
            right = mid
        }
    }

    return nums[left]
}

📌 题目四：154. 寻找旋转排序数组中的最小值 II（含重复元素）

🧩 解题难点

与 153 题不同的是，这道题目允许数组中含有重复值。

当 nums[mid] == nums[right] 时，无法判断最小值在哪一边，只能 right-- 缩小范围。

✅ Go 代码实现

func findMin(nums []int) int {
   
    left, right := 0, len(nums)-1

    for left < right {
   
        mid := (left + right) / 2
        if nums[mid] > nums[right] {
   
            left = mid + 1
        } else if nums[mid] < nums[right] {
   
            right = mid
        } else {
   
            right--
        }
    }

    return nums[left]
}

🧠 总结与对比

🔍 类似题推荐

• 1. 在排序数组中查找元素的第一个和最后一个位置
• 1. 搜索二维矩阵
• 1. 寻找峰值
• 1. 寻找两个正序数组的中位数

🎯 结语

这四道题完美地展示了 二分查找在旋转数组上的变形应用，也是 LeetCode 中非常有代表性的一类题。

📌 只要掌握：

• 判断有序区间
• mid 与边界的比较逻辑
• 如何处理重复元素的干扰

你就能轻松应对类似问题，写出高效、鲁棒的代码。

欢迎收藏 ⭐、点赞 👍 或评论交流 💬，我会继续更新更多高质量 LeetCode 题解！