#33
中等
高频
二分查找搜索旋转排序数组
这是一道围绕数组、排序展开的高频练习。建议先掌握「二分查找」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
排序
题目分析
原本升序排列的数组，在某个未知位置被旋转过一次。
现在给你旋转后的数组和目标值 target，要求你找出目标值的下标；如果不存在，就返回 -1。
题目还强调，要用对数级时间复杂度解决。
一句话概括：
虽然数组整体看起来断开了，但每次二分时总有一半是有序的，利用这一点继续缩小范围。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：每轮先判断哪一半是有序的，再看目标值是否落在这段有序区间里。
推荐代码
推荐解法：二分查找
时间复杂度： O(log n)
空间复杂度： O(1)
核心思路： 每轮先判断哪一半是有序的，再看目标值是否落在这段有序区间里。
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// 如果mid左边有序
if (nums[left] <= nums[mid]) {
// target在左边的有序子数组中
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
// target在右边
} else {
left = mid + 1;
}
// 否则右边有序
} else {
// target在右边的有序子数组中
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
// target在左边
} else {
right = mid - 1;
}
}
}
return -1;
}
}结构化讲解
面试时怎么讲
开场思路
这题还是二分，但关键不是直接比较大小，而是先识别哪一边有序。
核心过程
- 每轮计算中点，如果命中直接返回。
- 判断左半段还是右半段保持有序。
- 如果目标值落在有序半段范围内，就在那一边继续二分。
- 否则去另一边，直到找到目标或区间为空。
复杂度总结
时间复杂度 O(log n)，空间复杂度 O(1)。
面试补一句：旋转数组二分的核心句式是“先判哪边有序，再判目标在哪边”。
核心思路
旋转数组虽然整体不再完全有序，但每次二分后，左右两边一定有一边仍然保持有序。抓住这点，就能像普通二分一样持续砍半。
步骤讲解
1
常规二分取中点
每轮先取 mid，如果 nums[mid] 就是目标值，直接返回。
为什么这样做：旋转数组仍然适合用二分框架组织搜索。
对应代码提示：int mid = left + (right - left) / 2;
2
判断哪一半保持有序
比较 nums[left] 和 nums[mid]，如果左边有序，否则右边有序。
为什么这样做：旋转只会打断一处，因此二分后的两段里至少有一段仍是升序。
对应代码提示：if (nums[left] <= nums[mid]) { ... }
3
只保留目标可能存在的一半
如果目标值落在有序半段范围内，就收缩到这半边；否则去另一边继续搜。
为什么这样做：这样每轮都能把搜索区间减半。
对应代码提示：if (nums[left] <= target && target < nums[mid]) right = mid - 1;
易错点
没先判断哪边有序
旋转数组不能直接像普通二分那样只比大小，否则无法决定收缩方向。
正确理解：必须先识别左半段还是右半段有序。
边界条件写错导致死循环
特别是在更新 left、right 时漏掉 mid，容易卡住。
正确理解：保持标准写法：
right = mid - 1 或 left = mid + 1。把有序区间的比较写反
一旦范围判断错误，就会把目标排除到错误一边。
正确理解：始终围绕“目标是否落在当前有序区间”来判断。
复杂度与适用判断
时间复杂度：O(log n)
空间复杂度：O(1)
比其他方案更好在哪里：比线性扫描快得多，保住了二分的对数级复杂度。
适用判断：数组整体近似有序、只被局部打断时，优先考虑“变体二分”。
额外提醒
- 不是整个数组有序，而是每轮至少有半边有序。
动画演示
如果你还没完全看懂，可以展开动画演示。
二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 点击开始按钮查看动画
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。