🔍 LeetCode 系列：解决 4 道「搜索旋转排序数组」题 —— 二分查找的变形经典
旋转排序数组的问题是一类典型的二分查找变形题目。这类题目看似简单，却常常因为细节处理出错而导致调试困难。
本文一次性讲透这类问题，包括以下四道经典题：
- LeetCode 33. 搜索旋转排序数组（无重复）
- LeetCode 81. 搜索旋转排序数组 II（有重复）
- LeetCode 153. 寻找旋转排序数组中的最小值（无重复）
- LeetCode 154. 寻找旋转排序数组中的最小值 II（有重复）
📌 题目一：33. 搜索旋转排序数组
🔗 题目描述
给你一个整数数组 nums，它最初是按升序排列的，并经过一次旋转。给定一个目标值 target，若存在目标值返回其索引，否则返回 -1。
💡 解题思路
整体思路仍然是 二分查找，只是要结合旋转点的判断来决定查找方向。
- 每次取中点
mid； - 判断哪一边是有序的；
- 然后判断目标值是否落在有序区间内；
- 缩小边界继续搜索。
✅ 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]
}
🧠 总结与对比
| 题号 | 类型 | 是否允许重复 | 返回结果 | 特殊处理 |
|---|---|---|---|---|
| 33 | 查找目标值 | 否 | 索引 | 判断左右哪边有序 |
| 81 | 查找目标值 | ✅ 是 | 是否存在 | nums[left] == nums[mid] 时，left++ |
| 153 | 查找最小值 | 否 | 最小值 | 典型二分，比较 mid 和 right |
| 154 | 查找最小值 | ✅ 是 | 最小值 | 处理重复值时 right-- |
🔍 类似题推荐
-
- 在排序数组中查找元素的第一个和最后一个位置
-
- 搜索二维矩阵
-
- 寻找峰值
-
- 寻找两个正序数组的中位数
🎯 结语
这四道题完美地展示了 二分查找在旋转数组上的变形应用，也是 LeetCode 中非常有代表性的一类题。
📌 只要掌握：
- 判断有序区间
- mid 与边界的比较逻辑
- 如何处理重复元素的干扰
你就能轻松应对类似问题，写出高效、鲁棒的代码。
欢迎收藏 ⭐、点赞 👍 或评论交流 💬，我会继续更新更多高质量 LeetCode 题解！
