本文概览：本文讲解搜索旋转排序数组的核心思路：两种方法——两次二分查找（先找旋转点再二分）和一次二分查找（利用局部有序性）
一、题目
二、题目分析
这题给的是一个旋转排序数组。
什么是旋转？就是对于一个有序数组，选取一个索引，把该索引到数组末尾的所有元素前挪。
比如原来是 [1, 2, 3, 4, 5, 6, 7]，选取索引 3（值为 4）进行左旋转，数组就变成了 [4, 5, 6, 7, 1, 2, 3]。
旋转后的数组有两个特点：
- 分成两段递增序列：
[4, 5, 6, 7] 和 [1, 2, 3]
- 整体不再完全有序
题目要求时间复杂度 O(log n)，看到 O(log n) + 有序相关，显然要用二分查找。
但是标准二分查找会失败，因为数组不再完全有序。比如 [3, 4, 1, 2]，第一次 mid 取到 4，如果 target = 2，标准二分会错误地更新 right = mid - 1，但实际上 target 在右边。
所以需要变化，有两种方法：
- 方法一：两次二分查找（先找旋转点，再在对应范围二分）
- 方法二：一次二分查找（利用局部有序性）
思路概览
方法一：两次二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| public int search(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
int pivot = left;
int start, end;
if (target >= nums[pivot] && target <= nums[nums.length - 1]) {
start = pivot;
end = nums.length - 1;
} else {
start = 0;
end = pivot - 1;
}
left = start;
right = end;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
|
方法二：一次二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| 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;
}
|
思路简要说明：
方法一：
- 第一次二分：找旋转点（最小值的索引）
- 判断范围：根据 target 和旋转点、末尾元素的关系，确定 target 在哪一段
- 第二次二分：在确定的范围内进行标准二分查找
方法二：
- 判断局部有序：
nums[left] <= nums[mid] 说明左边有序，否则右边有序
- 判断 target 范围：如果 target 在有序部分内，按标准二分更新；否则去另一边
- 核心思想：每次都能确定一半是有序的，利用这个有序性判断 target 在哪边
三、思路详解
方法一：两次二分查找
第一步：找旋转点
旋转点就是数组中最小值的索引。
二分时，如果 nums[mid] > nums[right]，说明旋转点在 mid 右边（因为右边有更小的值），更新 left = mid + 1。
否则旋转点在 mid 或 mid 左边，更新 right = mid。
循环结束时 left 就是旋转点。
第二步：判断 target 在哪一段
旋转点把数组分成两段递增序列：
- 第一段：
[0, pivot - 1]
- 第二段：
[pivot, nums.length - 1]
如果 target >= nums[pivot] && target <= nums[nums.length - 1]，说明 target 在第二段，否则在第一段。
第三步：在确定范围内二分
确定了范围后，就是标准的二分查找了。
完整执行过程
以 nums = [4, 5, 6, 7, 0, 1, 2]，target = 0 为例：
第一次二分：找旋转点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 初始：left=0, right=6
第 1 轮：
mid = 3, nums[3] = 7 > nums[6] = 2
left = 4
第 2 轮：
left=4, right=6
mid = 5, nums[5] = 1 <= nums[6] = 2
right = 5
第 3 轮：
left=4, right=5
mid = 4, nums[4] = 0 <= nums[5] = 1
right = 4
第 4 轮：
left=4, right=4
left == right，退出循环
pivot = 4
|
判断范围
1
2
3
| nums[pivot] = 0, nums[6] = 2
target = 0
0 >= 0 && 0 <= 2 → target 在第二段 [4, 6]
|
第二次二分：在 [4, 6] 范围内查找
1
2
3
4
5
6
7
8
9
10
| 初始：left=4, right=6
第 1 轮：
mid = 5, nums[5] = 1 > 0
right = 4
第 2 轮：
left=4, right=4
mid = 4, nums[4] = 0 == 0
返回 4 ✓
|
方法二：一次二分查找
第一步：为什么标准二分会失败
以 nums = [3, 4, 1, 2]，target = 2 为例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 初始：left=0, right=3
第 1 轮：
mid = 1, nums[1] = 4 > 2
right = mid - 1 = 0 ← 错误！target 在右边
第 2 轮：
left=0, right=0
mid = 0, nums[0] = 3 > 2
right = -1
第 3 轮：
left=0, right=-1
退出循环，返回 -1 ← 错误！
|
问题在于：标准二分假设数组完全有序，但旋转数组不是。当 nums[mid] > target 时，target 不一定在左边。
第二步：利用局部有序性
观察旋转数组的特点：对于任意 mid，左边或右边必然有一边是有序的。
- 如果
nums[left] <= nums[mid]：说明左边有序（[left, mid] 是递增的）
- 否则：说明右边有序（
[mid, right] 是递增的）
第三步：判断 target 在哪边
情况 1：左边有序
如果 nums[left] <= target && target < nums[mid]，说明 target 在左边的有序范围内，更新 right = mid - 1。
否则 target 在右边，更新 left = mid + 1。
情况 2：右边有序
如果 nums[mid] < target && target <= nums[right]，说明 target 在右边的有序范围内，更新 left = mid + 1。
否则 target 在左边，更新 right = mid - 1。
完整执行过程
以 nums = [4, 5, 6, 7, 0, 1, 2]，target = 0 为例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 初始：left=0, right=6
第 1 轮：
mid = 3, nums[3] = 7 != 0
nums[0] = 4 <= nums[3] = 7 → 左边有序
nums[0] = 4 <= 0? false → target 不在左边有序范围
left = mid + 1 = 4
第 2 轮：
left=4, right=6
mid = 5, nums[5] = 1 != 0
nums[4] = 0 <= nums[5] = 1 → 左边有序
nums[4] = 0 <= 0 && 0 < 1? true → target 在左边有序范围
right = mid - 1 = 4
第 3 轮：
left=4, right=4
mid = 4, nums[4] = 0 == 0
返回 4 ✓
|
再举一个例子，nums = [4, 5, 6, 7, 0, 1, 2]，target = 6：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 初始：left=0, right=6
第 1 轮：
mid = 3, nums[3] = 7 != 6
nums[0] = 4 <= nums[3] = 7 → 左边有序
nums[0] = 4 <= 6 && 6 < 7? true → target 在左边有序范围
right = mid - 1 = 2
第 2 轮：
left=0, right=2
mid = 1, nums[1] = 5 != 6
nums[0] = 4 <= nums[1] = 5 → 左边有序
nums[0] = 4 <= 6 && 6 < 5? false → target 不在左边有序范围
left = mid + 1 = 2
第 3 轮：
left=2, right=2
mid = 2, nums[2] = 6 == 6
返回 2 ✓
|
四、总结
搜索旋转排序数组有两种方法：
方法一：两次二分查找
- 第一次二分找旋转点
- 判断 target 在哪一段
- 第二次二分在确定范围内查找
方法二：一次二分查找
- 判断哪边有序（
nums[left] <= nums[mid]）
- 判断 target 是否在有序范围内
- 根据判断结果更新 left 或 right
两种方法的时间复杂度都是 O(log n)，方法二代码更简洁，但方法一思路更直观。
