LeetCode 33中等二分查找 · 旋转
搜索旋转排序数组 图解题解
旋转数组整体无序，但从 mid 一切，总能认出有序的那半——target 在不在里面，一比就知道往哪走。
旋转数组从 mid 切两半，必有一半是完整升序——就像一根折弯的尺，两段各自仍标着连续刻度。认出哪半有序（比较两个端点即可），再看 target 落不落在那半的范围里：落进去就去那半，落不进就去另一半。每步砍一半，二分在「局部有序」里也能用。
这道题到底在问什么
一个升序数组在某个点旋转过（比如 [0,1,2,4,5,6,7] 转成 [4,5,6,7,0,1,2]），在里面找 target，找到返回下标，没有返回 -1。
- nums
- [4,5,6,7,0,1,2]
- target
- 0
- 输出
- 4
先想最直接的笨办法
挨个找当然行，可那就白白浪费了「旋转前本来有序」这个条件。题目都把有序明牌摆你面前了，必须把二分用起来。（动画第 3 步）
最优解：一步一步想明白
- 3挨个找当然行，可那就白白浪费了「旋转前本来有序」这个条件。题目都把有序明牌摆你面前了，必须把二分用起来。
- 4转折：旋转数组虽整体无序，但从 mid 切两半，总有一半是完整升序（端点一比就知道：nums[l] ≤ nums[mid] 则左半有序，否则就是右半有序）。认出有序半后，只要看 target 在不在那半的范围里就能决定丢哪边——照样每步砍一半。
- 5l=0, r=6搜索范围是整个数组，l=0、r=6。要找的 target = 0。
- 6mid=3 → nums[3]=7中点 mid=3 处是 7，不等于目标 0。先判断哪半有序。
- 7nums[0]=4 ≤ nums[3]=7 → 左半有序比端点：nums[l]=4 小于等于 nums[mid]=7，说明左半 [4,5,6,7] 是有序的（高亮那段）。那就拿 target 和这个有序半的范围比。
- 80 不在 [4,7) → l=mid+1=40 不落在有序左半 [4,7)（含左端 4、不含已单独判过的 mid=7）里，所以它必在另一半。整个左半丢掉（灰），l 跳到 4。
- 9mid=5 → nums[5]=1只看右段 [0,1,2]。新中点 mid=5 处是 1，仍不等于 0。
- 10nums[4]=0 ≤ nums[5]=1 → 左半有序同样先比端点：nums[4]=0 小于等于 nums[5]=1，左半 [0,1] 有序。拿 target 和它的范围比。
- 110 在 [0,1) → r=mid-1=4这次 0 正好落在有序左半 [0,1)（含左端 0、不含已单独判过的 mid=1）里，所以去这半找：丢掉 mid 右边，r 收到 4。
- 12l=r=4, nums[4]=0 ✓区间只剩一个，mid=4 处正好是 0 = target。返回下标 4。每轮都砍掉一半，所以是 O(log n)。
- 13注意：上面三轮 mid 都落在左半，比出来都是「左半有序」。可代码里还有个 else——当 nums[l] ＞ nums[mid] 时，是右半有序。换个例子把这条分支也跑一遍，套路才算闭环。
- 14l=0, r=6换一个旋转得更狠的数组 [6,7,0,1,2,4,5]，要找的 5 在靠右那段。看 mid 落到小数那边会发生什么。
- 15mid=3 → nums[3]=1中点 mid=3 处是 1，不等于 5。照例先判哪半有序。
- 16nums[0]=6 ＞ nums[3]=1 → 右半有序关键差别来了：nums[l]=6 大于 nums[mid]=1，左半不再是升序——说明断点在左边，反而是右半 [1,2,4,5] 完整有序（高亮右段）。这就是代码里的 else 分支。
- 175 在 (1,5] → l=mid+1=4这回比的是右有序半的范围：5 落在 (1, 5] 里，所以去右半。丢掉 mid 左边（灰），l 跳到 4。注意这里收的是 l，正好和左半有序那支相反。
- 18mid=5 → nums[5]=4剩下 [2,4,5]。新中点 mid=5 处是 4，还不是 5。
- 19nums[4]=2 ≤ nums[5]=4 → 左半有序这小段又恢复成左半有序：nums[4]=2 小于等于 nums[5]=4。5 不在 [2,4] 里，所以去另一半，l 跳到 6。
- 20l=r=6, nums[6]=5 ✓区间只剩 mid=6，正好是 5 = target。返回下标 6。两条分支（左半有序 / 右半有序）现在都跑通了。
- 23旋转数组的二分，核心就这一句：哪半有序看得出来（端点比一下），target 在不在那半也看得出来（范围比一下）。剩下交给二分。
- 28把这题练到能复述后，再去同类题里迁移：先复用「定有序半」的状态判断，再调整边界条件。也可以直接问问右侧的小欧：「LC81 有重复元素时这套二分会怎么退化？」
⚠️ 容易写错的地方
✗ 错：nums[l] ＜ nums[mid] 判有序
✓ 对：nums[l] ≤ nums[mid]
mid 和 l 可能相邻甚至重合，必须带等号，否则漏判
✗ 错：落点范围两端都算 / 两端都不算
✓ 对：含有序半外侧端点、不含 mid（mid 已单独判过命中）：左半有序用 [nums[l], nums[mid])，右半有序用 (nums[mid], nums[r]]
外侧端点本身可能就是答案不能漏；mid 上一步已单独判过命中，再算进范围会把它算重导致逻辑出错
✗ 错：只写 if（左半有序）忘了 else
✓ 对：else（右半有序）那支必须照样写齐
mid 落进旋转后的小数段时就是右半有序，漏了这支会越界或死循环
完整代码（Python / C++ / Java）
Python
class Solution:
def search(self, nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]: # 左半有序
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # 右半有序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1C++
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // 左半有序
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半有序
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
};Java
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // 左半有序
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半有序
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
}套路模板 · 旋转数组二分（背下来）
# 旋转二分骨架：l<=r闭区间搜索 + 先定有序半 + 半开范围判落点
while l <= r:
mid = (l + r) // 2
if nums[mid] == ___目标命中: return mid # 先判命中
if nums[l] <= nums[mid]: # 端点比一下：左半有序
if target 在 [nums[l], nums[mid]): 收右 r = mid-1 # 含左端,不含mid
else: 否则去另一半 l = mid+1
else: # 否则右半有序（别忘这支！）
if target 在 (nums[mid], nums[r]]: 收左 l = mid+1 # 不含mid,含右端
else: 否则去另一半 r = mid-1// 旋转二分骨架（伪码挖空，填进比较即可）
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid; // 先判命中
if (nums[l] <= nums[mid]) { // 端点比：左半有序
if (/* target 在 [nums[l], nums[mid]) */) r = mid - 1;
else l = mid + 1;
} else { // 否则右半有序
if (/* target 在 (nums[mid], nums[r]] */) l = mid + 1;
else r = mid - 1;
}
}// 旋转二分骨架（伪码挖空，填进比较即可）
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid; // 先判命中
if (nums[l] <= nums[mid]) { // 端点比：左半有序
if (/* target 在 [nums[l], nums[mid]) */) r = mid - 1;
else l = mid + 1;
} else { // 否则右半有序
if (/* target 在 (nums[mid], nums[r]] */) l = mid + 1;
else r = mid - 1;
}
}复杂度
时间复杂度
O(log n)
每轮砍一半
空间复杂度
O(1)
几个指针
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 搜索旋转排序数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么旋转数组还能二分？+
从 mid 切开必有一半仍有序；在有序半里能 O(1) 判断 target 是否在内，从而砍掉一半。
怎么判断到底是左半还是右半有序？+
比端点 nums[l] 和 nums[mid]：nums[l]≤nums[mid] 则左半有序，否则（nums[l]＞nums[mid]）右半有序。两支都要写。
有重复元素(LC81)会怎样？+
nums[mid]==nums[left] 时分不清哪半有序，要 left++ 跳过，最坏退化 O(n)。
复杂度？+
O(log n) 时间、O(1) 空间。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。