LeetCode 33. 搜索旋转排序数组
题目描述
题意分析
一个元素互不相同的升序数组，经过旋转后，要在其中查找
target：存在就返回它当前的下标，不存在返回-1。旋转相当于把某段前缀整体移到数组末尾，两段内部仍然保持原来的升序。数组也可能没有旋转。题目要求 $O(\log n)$ 时间，因此需要像二分查找一样，每轮排除约一半候选位置；但数组整体可能不再有序，不能只比较中点与目标的大小就决定往哪边找。
解法：一次二分判断有序半区
核心思路
[!blue]
旋转后的数组至多有一个从大值跳到小值的断点。用中点
mid划分当前搜索区间时，断点不可能同时位于两侧，所以[left, mid]和[mid, right]中至少有一侧保持升序。先确定有序侧，才能利用它的端点判断目标的去向。每轮先检查
nums[mid]是否就是目标；若不是，再比较nums[left]和nums[mid]。当nums[left] <= nums[mid]，左侧没有跨过断点，是有序的；否则断点在左侧，右侧一定有序。这里依赖元素互不相同；等号用于覆盖left == mid时只有一个元素的左半区。左侧有序时，若
nums[left] <= target < nums[mid]，目标只能在左侧，令right = mid - 1；否则左侧可以排除，令left = mid + 1。右侧有序时同理：若nums[mid] < target <= nums[right]，保留右侧，否则保留左侧。落入值域只表示可能存在，仍要继续二分找到准确下标。无论哪种情况，保留下来的区间都包含尚未排除的目标位置，而
mid已经检查过，所以边界更新时将它一并排除。搜索范围持续缩小，最终找到目标，或者在left > right时确认不存在。没有旋转的数组也满足这些判断，不需要另写分支。
解题步骤
- 在闭区间
[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;
int 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)$。
关键点总结
[!green]
- 数组整体无序，但每轮至少有一个半区有序。
- 只在确定有序的半区内判断
target的值域。- 始终维护闭区间
[left, right]，更新边界时排除已经检查过的mid。
易错点总结
[!yellow]
- 判断左半区有序必须写
nums[left] <= nums[mid]；等号覆盖单元素区间。- 两个值域分别是左闭右开和左开右闭，避免重复保留
mid。- 循环条件应为
left <= right，否则可能漏查最后一个元素。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 81. 搜索旋转排序数组 II | 中等 | 原题允许重复值，可能无法判断哪半区严格有序，最坏需逐步缩边。 |
| 153. 寻找旋转排序数组中的最小值 | 中等 | 同样利用旋转数组的有序半区，原题只找旋转后的最小值，本题查指定目标。 |
| 154. 寻找旋转排序数组中的最小值 II | 困难 | 利用旋转数组中仍有序的一半排除搜索区间；本题元素互异时定位目标下标，该题重复值相等时逐步缩小不确定区间。 |