LeetCode 33. 搜索旋转排序数组
目录
题目描述
题意分析
题目要的东西非常朴素：在一个数组里找
target，返回它的下标（不是值、也不是是否存在），找不到返回-1。真正的难点全在约束里。最硬的约束是「必须设计一个 $O(\log n)$ 的算法」。这句话直接把「从头扫到尾比一遍」这条路封死了：线性扫描是 $O(n)$，即使能过测试用例也不满足题目要求。$O(\log n)$ 意味着每做常数次判断，就必须能永久丢掉剩余候选范围的一个固定比例。于是整道题的核心问题变成：站在数组中间某个位置上，我凭什么断定
target不可能在某一侧？题面给了三个前提，它们各有各的用处，少一个结论就不成立。原本是升序数组是「一侧可以被整体排除」的根基——只有在有序段里，才能靠两个端点的值判断某个数是否可能落在段内。只被旋转了一次保证了结构是「两段升序拼接，且前一段的每个元素都大于后一段的每个元素」，断点只有一个；因此不管从哪里切一刀，断点最多落在其中一侧，另一侧必然是完整的升序段。如果允许旋转多次（等价于任意打乱），这个结论立刻失效。元素互不相同让「比较两个端点的值」能得出确定结论；一旦允许重复，端点值相等时就无法区分「这一段是平坦的有序段」还是「断点藏在相等的值里面」，判断退化成不确定，只能退回逐个排除。
需要提前想清楚的边界情形有四类。旋转 0 次，即数组原封不动完全有序，它是合法输入，算法不能依赖「一定存在断点」。只有一个元素时唯一的候选就是它自己，任何「先切一刀再取一侧」的写法都必须保证这个元素被真正检查到，而不是被区间收缩直接跳过。
target根本不在数组里时不会有任何一轮命中，必须靠候选区间收缩成空来终止并返回-1，而不是靠找到答案来终止。只有两个元素且被旋转过（形如「大的在前、小的在后」）是最容易暴露区间划分与取中点方式配合失误的规模，务必单独验算。
解法：一次二分判断有序半区
核心思路
旋转数组以
mid分割后，至少有一半仍然有序。先判断哪一半有序，再根据target是否落在该半区的值域内，排除另一半；每轮都能缩小一半搜索范围。
解题步骤
- 在闭区间
[left, right]上二分，先判断nums[mid]是否等于target。- 若
nums[left] <= nums[mid]，左半区有序；判断target是否在[nums[left], nums[mid])内。- 否则右半区有序；判断
target是否在(nums[mid], nums[right]]内。- 保留可能包含
target的半区；区间为空时返回-1。
代码实现
class Solution {
public int search(int[] nums, int target) {
int left = 0, 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 (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;
}
}
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/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
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮排除一半区间。
- 空间复杂度：$O(1)$。
关键点总结
- 数组整体无序，但每轮至少有一个半区有序。
- 只在确定有序的半区内判断
target的值域。- 始终维护闭区间
[left, right]，更新边界时排除已经检查过的mid。
易错点总结
- 判断左半区有序必须写
nums[left] <= nums[mid]；等号覆盖单元素区间。- 两个值域分别是左闭右开和左开右闭，避免重复保留
mid。- 循环条件应为
left <= right，否则可能漏查最后一个元素。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 704. 二分查找 | 简单 | 数组没有被旋转，是本题第二阶段用到的标准闭区间二分骨架 |
| 35. 搜索插入位置 | 简单 | 目标不存在时不返回 -1，而要返回应插入的位置，考的是循环结束后 left 的含义 |
| 81. 搜索旋转排序数组 II | 中等 | 允许重复元素，端点值相等时无法判断哪半有序，需先收缩相等边界，最坏退化到 $O(n)$ |
| 153. 寻找旋转排序数组中的最小值 | 中等 | 只要求找旋转点本身而不查目标，等价于本题解法二的 findPivot 单独成题 |
| 154. 寻找旋转排序数组中的最小值 II | 困难 | 在 153 的基础上加入重复元素，nums[mid] == nums[right] 时只能把右边界退一格 |
| 剑指 Offer 11. 旋转数组的最小数字 | 简单 | 与 154 同题不同表述，可用来对照「含重复元素时找旋转点」的写法 |
| 面试题 10.03. 搜索旋转数组 | 中等 | 同样是旋转数组查找，但允许重复且要求返回下标最小的那个匹配位置 |
| 162. 寻找峰值 | 中等 | 数组完全无序，靠邻居比较而非区间端点决定往哪半收缩，是「无序也能二分」的另一例 |