LeetCode 面试题 10.03. 搜索旋转数组
目录
题目描述
题意分析
数组原本升序排列，被整体旋转了若干位，现在要在里面找
target的下标，找不到返回-1。两个容易被忽略的要求：数组里允许有重复元素；当
target出现多次时，必须返回下标最小的那一个。后者是本题与 33、81 两题最大的差别，也是最常见的失分点——只要写成「命中mid就返回」，遇到重复元素就会返回中间某个位置。约束信号：数组长度可达 $10^6$，说明期望的是对数级别的做法，线性扫描虽然能过一部分数据但显然浪费了「旋转有序」这个结构信息；同时重复元素的存在意味着最坏情况必然退化，面试时要主动说明这一点。
边界包括：空数组；旋转了 0 位（即完全有序）；整个数组元素全部相同；
target恰好落在旋转点两侧；target出现在下标 0。
解法：含重复元素的旋转二分
核心思路
旋转数组由两段非递减区间组成，因此可以二分判断哪一侧有序；线性扫描虽能自然得到最小下标，却没有利用这个结构。
当
arr[left] < arr[mid]时左半段有序；当arr[left] > arr[mid]时右半段有序。用有序段的端点判断target是否落在其中，就能安全舍弃另一半。重复元素会让
arr[left] == arr[mid]，此时无法判断旋转点在哪一侧。循环开头已排除arr[left] == target，所以只能安全地执行left++；一次跳到mid + 1可能越过答案。不变量是：若答案存在，它的最小下标始终在
[left, right]。每轮先检查左端点；中点命中时只令right = mid，继续向左收缩。其余分支只舍弃端点范围明确不含target的有序段，因此不会丢失最小答案。
解题步骤
- 初始化闭区间
[left, right]，循环条件为left <= right；空数组会直接返回-1。- 每轮先检查左端点。若
arr[left] == target，根据不变量它就是全局最小下标。- 若中点命中，令
right = mid继续向左找。此时mid > left，所以区间一定缩小。- 若
arr[mid] > arr[left]，说明[left, mid]有序：target落在(arr[left], arr[mid])之间才可能在左半边，于是right = mid - 1；否则left = mid + 1。- 若
arr[mid] < arr[left]，说明旋转点在(left, mid]，[mid, right]有序：target落在(arr[mid], arr[right]]之间才可能在右半边，于是left = mid + 1；否则right = mid - 1。注意右端要取闭区间<=，否则会漏掉恰好等于arr[right]的目标。- 若
arr[left] == arr[mid]，执行left++消除重复值造成的歧义。- 循环结束仍未命中，返回
-1。例如
arr = [3,4,4,5,1,2]、target = 4：第一次mid = 2命中时不能返回，而应把right收到 2；继续收缩后最终由左端点命中下标 1，得到最小下标。
代码实现
class Solution {
public int search(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
// 左端点命中即是最小下标，区间左侧已被证明不含 target。
if (arr[left] == target) {
return left;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
// 左边可能还有更早的出现位置，只收缩右边界。
right = mid;
} else if (arr[mid] > arr[left]) {
if (arr[left] < target && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (arr[mid] < arr[left]) {
if (arr[mid] < target && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
// 重复值遮蔽有序区间时，只能安全地丢掉一个左端点。
left++;
}
}
return -1;
}
}
func search(arr []int, target int) int {
left := 0
right := len(arr) - 1
for left <= right {
// 左端点命中即是最小下标。
if arr[left] == target {
return left
}
mid := left + (right-left)/2
if arr[mid] == target {
// 继续向左找更小的下标。
right = mid
} else if arr[mid] > arr[left] {
if arr[left] < target && target < arr[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else if arr[mid] < arr[left] {
if arr[mid] < target && target <= arr[right] {
left = mid + 1
} else {
right = mid - 1
}
} else {
// 无法判断有序侧，只丢掉一个左端点。
left++
}
}
return -1
}
复杂度分析
- 时间复杂度：能够判断有序侧时为 $O(\log n)$；最坏为 $O(n)$，因为
arr[left] == arr[mid]时只能丢掉一个元素，形如[1,1,1,...,1,0,1,...,1]找0会退化成线性扫描。- 空间复杂度：$O(1)$，只用了
left、right、mid三个下标变量，没有递归也没有额外容器。
关键点总结
- 本题必须返回最小下标，这是它区别于 33、81 的核心考点；命中
mid时收缩右边界而不是直接返回，是解法的关键改动。- 循环开头的
arr[left] == target检查一举两得：既让返回值天然最小，又为「arr[left] == arr[mid]时left++」提供了安全性依据。- 重复元素只破坏「判断哪一侧有序」这一步，不破坏二分框架；无法判断时退一步而不是猜一半，是保证正确性的底线。
- 面试时要主动说明：重复元素会遮蔽有序侧，因此最坏复杂度退化为 $O(n)$，这不是普通二分的严格 $O(\log n)$。
易错点总结
- 错误写法：
if (arr[mid] == target) return mid;。用例arr = [1,1,1,1,1,2,1,1,1]、target = 1→ 第一轮mid = 4直接返回4，而题目要求返回最小下标0。- 错误写法：把
arr[mid] == target改成right = mid却删掉循环开头的arr[left] == target检查。用例arr = [3,1,2,3]、target = 3→ 收缩到left == right == mid后right = mid不再让区间变小，陷入死循环。- 错误写法：
arr[left] == arr[mid]时写left = mid + 1。用例arr = [1,0,1,1,1]、target = 0→ 一步跳过了下标 1 上的0，最终返回-1，正确答案是1。- 错误写法：直接照搬 33 题模板，用
arr[left] <= arr[mid]判定左侧有序。用例arr = [1,0,1,1,1]、target = 0→ 相等时被误判为左侧升序，判断1 <= 0 < 1不成立而跳向右半边，返回-1，正确答案是1。- 错误写法：右半段判断写成
arr[mid] < target && target < arr[right]。用例arr = [7,0,1,2,4,5,6]、target = 6→ 恰好等于右端点的目标被排除在外，转而搜索左半边，返回-1，正确答案是6。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 33. 搜索旋转排序数组 | 中等 | 无重复元素的旋转二分 |
| 81. 搜索旋转排序数组 II | 中等 | 含重复元素判存在性 |
| 153. 寻找旋转排序数组中的最小值 | 中等 | 二分定位旋转点 |
| 154. 寻找旋转排序数组中的最小值 II | 困难 | 重复元素下的旋转点 |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 二分求左右边界下标 |
| 剑指 Offer 11. 旋转数组的最小数字 | 简单 | 旋转数组最小值模板 |