Search in Rotated Sorted Array 是 LeetCode Hot 100 里面一道非常经典的二分查找题。
如果说普通二分查找考察的是“在有序数组中如何快速定位目标值”，那么这道题就是在它的基础上做了一层变化： 数组原本是升序排列的，但在某个位置发生了旋转。于是整个数组不再是完全有序，而是变成了：
局部有序、整体断开
其实答案是： 仍然可以二分。
关键就在于：虽然整个数组不是单调递增的，但在每一次二分时，我们总能判断出 mid 左边或者右边至少有一半是有序的。只要利用这一点，就能继续缩小搜索范围。
你给出的这份 Java 代码，就是这道题非常经典的一种写法。 本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定一个经过旋转的升序数组 nums，以及一个目标值 target，要求你在数组中找到目标值的下标。
如果目标值不存在，就返回：
-1
题目中所说的“旋转”，意思是原本有序的数组在某个位置断开，然后把前半部分接到后面。
例如：
原数组：
[0,1,2,4,5,6,7]
如果在下标 3 的位置旋转后，就可能变成：
[4,5,6,7,0,1,2]
虽然这个数组整体上已经不是严格升序，但它依然保留了“两个局部有序区间”的特征。
题目要求你设计一个时间复杂度为：
O(log n)
的算法。
这也就意味着，暴力遍历肯定不是题目想考察的方法，核心一定是 二分查找。
示例
示例 1
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
目标值 0 在数组中的下标是 4，所以返回 4。
示例 2
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
数组中不存在 3，所以返回 -1。
示例 3
输入：nums = [1], target = 0 输出：-1
只有一个元素，而且不是目标值，所以返回 -1。
这道题为什么还能用二分？
很多人第一次看到旋转数组时，会觉得：
数组已经不是完全有序的了，那普通二分查找不就失效了吗？
确实，普通二分查找依赖的是“整个区间有序”。 而这道题里，整个数组不再满足这个条件。
但是这道题的关键在于：
每次取中点以后，左右两边一定至少有一边是有序的。
比如：
[4,5,6,7,0,1,2]
如果当前 mid 落在 7 上，那么：
-
左半部分
[4,5,6,7]是有序的 -
右半部分
[0,1,2]虽然也是有序的，但相对整体来说发生了断开
也就是说，即使整个数组不完全有序，我们依然能通过判断 nums[0]、nums[mid]、nums[n-1] 的关系，确定当前哪一半是单调有序的。
而一旦某一半是有序的，我们就能判断目标值是否落在这一半里面，从而决定下一步往左找还是往右找。
这就是这道题能继续使用二分查找的根本原因。
核心思路
你这段代码的核心逻辑可以概括成下面几步：
-
先正常二分，找到中点
mid -
如果
nums[mid] == target，直接返回 -
判断当前是左半部分有序，还是右半部分有序
-
根据目标值是否落在有序区间中，决定缩小哪一边
重点就在第 3 步和第 4 步。
如何判断哪一半有序？
假设当前区间是 [lef, rig]，中点是 mid。
你的代码使用了下面这个判断：
if (nums[0] <= nums[mid]) {
...
} else {
...
}
这里的含义是：
-
如果
nums[0] <= nums[mid]，说明从数组起点到mid这一段是有序的 -
否则，说明
mid落在旋转点右侧，那么右半部分一定是有序的
在很多题解里，也有人写成：
if (nums[lef] <= nums[mid])
你这份代码写成 nums[0] 也是可以的，因为搜索过程中旋转结构本质没变，而且题目保证数组中元素互不相同。
Java 代码
下面就是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public int search(int[] nums, int target) {
int siz = nums.length;
int lef = 0, rig = siz - 1;
while (lef <= rig) {
int mid = (lef + rig) >> 1;
// 如果刚好找到目标值，直接返回
if (nums[mid] == target) return mid;
// 判断左半部分是否有序
if (nums[0] <= nums[mid]) {
// 如果目标值落在左侧有序区间中，就去左边找
if (nums[0] <= target && target < nums[mid]) rig = mid - 1;
else lef = mid + 1;
} else {
// 否则说明右半部分有序
// 如果目标值落在右侧有序区间中，就去右边找
if (nums[mid] < target && target <= nums[siz - 1]) lef = mid + 1;
else rig = mid - 1;
}
}
return -1;
}
}
代码拆解
这段代码整体不长，但逻辑绕的地方主要在“如何判断哪一边有序”以及“目标值应该落在哪一边”。 下面一步一步来看。
1. 为什么一开始还是普通二分模板？
int lef = 0, rig = siz - 1;
while (lef <= rig) {
int mid = (lef + rig) >> 1;
...
}
因为这道题本质上还是查找问题，只不过数组不再完全有序。
所以整体框架依然是标准的二分模板：
-
维护左右边界
lef、rig -
取中点
mid -
每次排除一半区间
这说明：
旋转数组并没有让二分失效，它只是改变了“如何判断下一步去哪边找”的条件。
2. 为什么先判断 nums[mid] == target？
if (nums[mid] == target) return mid;
这是任何查找题里最优先的判断。
因为如果中点就是目标值，那就没必要继续缩小区间了，直接返回即可。
这一句虽然简单，但它保证了后面的逻辑都是在“当前中点不是目标值”的前提下展开的。
3. 为什么 nums[0] <= nums[mid] 可以判断左边有序？
if (nums[0] <= nums[mid]) {
...
}
这是整道题最关键的判断之一。
在旋转排序数组中，数组可以看成两段：
-
一段较大的有序部分
-
一段较小的有序部分
例如：
[4,5,6,7,0,1,2]
这里：
-
[4,5,6,7]是一段 -
[0,1,2]是另一段
如果当前 mid 落在左边那一大段中，那么它一定满足：
nums[0] <= nums[mid]
因为左侧这段是从数组起点开始连续递增的。
反过来，如果 nums[0] > nums[mid]，说明 mid 已经落在旋转点右边那一段小值区间里了，这时候右半部分一定有序。
所以这个判断本质上是在判断：
中点到底落在旋转点左边，还是右边。
4. 左边有序时，为什么用这个条件判断目标是否在左边？
if (nums[0] <= target && target < nums[mid]) rig = mid - 1;
else lef = mid + 1;
当左半部分有序时，它的值域范围就是：
[nums[0], nums[mid])
注意不包含 nums[mid]，因为前面已经判断过 nums[mid] != target 了。
所以如果目标值满足：
-
大于等于左端点
nums[0] -
小于中点值
nums[mid]
就说明目标值一定落在左边这个有序区间中。 此时就应该把搜索范围缩到左边：
rig = mid - 1;
否则，目标值不在左边，只能去右边找：
lef = mid + 1;
5. 右边有序时，为什么用这个条件判断目标是否在右边？
if (nums[mid] < target && target <= nums[siz - 1]) lef = mid + 1;
else rig = mid - 1;
如果左边不是有序的，那说明右边一定有序。
这时右边有序区间的值域范围就是：
(nums[mid], nums[siz - 1]]
因为 nums[mid] != target，所以中点值本身不需要包含。
如果目标值满足：
-
大于
nums[mid] -
小于等于数组最后一个值
nums[siz - 1]
那就说明目标值一定在右边，于是移动左边界：
lef = mid + 1;
否则，就只能去左边继续找：
rig = mid - 1;
手动模拟一遍
我们用经典样例来走一遍：
nums = [4,5,6,7,0,1,2], target = 0
第一次
-
lef = 0 -
rig = 6 -
mid = 3 -
nums[mid] = 7
判断：
-
nums[mid] != target -
nums[0] <= nums[mid]，即4 <= 7，成立
说明左半部分 [4,5,6,7] 有序。
再看目标值 0 是否在左边有序区间中：
-
4 <= 0不成立
所以目标值不在左边，去右边找：
lef = mid + 1 = 4
第二次
-
lef = 4 -
rig = 6 -
mid = 5 -
nums[mid] = 1
判断：
-
nums[mid] != target -
nums[0] <= nums[mid]，即4 <= 1，不成立
说明右半部分有序。
判断目标值 0 是否在右边有序区间：
-
1 < 0不成立
所以目标值不在右边，只能去左边找：
rig = mid - 1 = 4
第三次
-
lef = 4 -
rig = 4 -
mid = 4 -
nums[mid] = 0
此时：
nums[mid] == target
直接返回 4。
这正好就是答案。
再看一个找不到的例子
比如：
nums = [4,5,6,7,0,1,2], target = 3
通过不断二分后会发现：
-
目标值既不在左边有序区间
-
也不在右边有序区间
最终区间缩小到空，循环结束，返回：
-1
这表示数组中不存在目标值。
为什么这个算法是正确的？
因为在任意一次循环中，虽然整个区间不一定有序，但总能保证：
-
左半边有序，或者
-
右半边有序
而一旦知道某一半有序，我们就能判断目标值是否落在这半边中。
如果在，就保留这半边； 如果不在，就排除这半边。
这和普通二分类似，本质上仍然是在每一步排除掉一半不可能的区间，所以最终时间复杂度仍然是：
O(log n)
这也是这道题最核心的思想。
复杂度分析
时间复杂度
每次循环都会把搜索区间缩小一半，因此时间复杂度是：
O(log n)
空间复杂度
只使用了常数级别的额外变量，所以空间复杂度是：
O(1)
这道题真正想考什么？
这道题表面上是在考“旋转数组查找”，但本质上考察的是两个能力。
第一，是否真正理解二分查找
很多人把二分查找理解成“数组有序才能用”。 但更准确地说，二分查找真正依赖的是：
每一步都能判断出哪一半可以被排除。
这道题虽然整体不是完全有序，但依然满足“每次至少有一半有序”这个特征，所以仍然可以二分。
第二，是否能利用数组的结构特征
旋转数组虽然整体断开了，但它不是完全无序，而是保留了非常强的结构性：
-
左边某段有序
-
右边某段有序
-
中点一定落在其中一段中
谁能抓住这个结构，谁就能把题做出来。
和普通二分查找有什么区别？
普通二分查找中：
-
整个区间始终有序
-
所以只要比较
target和nums[mid]大小，就能决定往哪边走
而这道题中：
-
整个区间不一定有序
-
所以不能只看
target和nums[mid] -
必须先判断哪一半有序，再判断目标值是否在那一半中
也就是说，这题本质上是：
在普通二分上多加了一步“识别有序区间”的判断。
这是它和基础二分最大的区别。
总结
这道题的核心思想可以概括成一句话：
虽然旋转数组整体无序，但每次二分时总能找到一半有序区间，再根据目标值是否落在该区间中决定搜索方向。
具体步骤就是：
-
取中点
mid -
如果
nums[mid] == target，直接返回 -
判断左半边还是右半边有序
-
再判断目标值是否在有序区间里
-
排除掉不可能的一半，继续二分
最终就能在：
O(log n)
的时间复杂度内完成查找。
这是一道非常经典、也非常值得反复理解的二分题。 因为它会让你真正意识到：二分查找并不只是“在完全有序数组里查数”，而是一种“利用结构特征不断缩小搜索范围”的思维方式。
把这道题真正吃透之后，再去看：
-
寻找旋转排序数组中的最小值
-
搜索旋转排序数组 II
-
查找峰值
-
寻找重复数
这些“变形二分”题目时，你会明显更容易找到切入点。
