搜索旋转排序数组
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
整数数组 nums 按升序排列，数组中的值 互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。
给你 旋转后 的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。你必须设计一个时间复杂度为 O(log n) 的算法。
示例 1
target = 0 在下标 4 处。示例 2
示例 3
模拟答题者思考
1. 我先想暴力：从左到右线性扫描找 target，O(n)——能过但题目明确要求 O(log n)。
2. 重复在哪里？原数组整体升序，旋转后只是「在某个点切开再拼接」；任意取 mid，左半 [l,mid] 与右半 [mid+1,r] 里至少有一段仍是严格升序（另一段可能跨过旋转断点）。
3. 关键转化：先判断哪一半有序——若 nums[l] <= nums[mid]，左半升序；否则右半升序。再在有序半段上做普通二分：看 target 是否落在这段数值范围内，是则缩到该半段，否则去另一半。
4. 例 [4,5,6,7,0,1,2], target=0：首轮 mid=3, nums[mid]=7，左半 [4,7] 升序且 0 不在其中，故去右半；次轮右半 [0,1,2] 升序且 0 在内，最终命中下标 4。
5. 每轮排除一半元素，整体 O(log n)；元素互不相同保证了有序半段的边界判断不会出现 == 歧义。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
l, r | int | 定义：当前待搜索区间的左右边界下标 维护：若 target 存在，其下标始终在 [l, r] 内更新：每轮根据哪一半有序、 target 是否落在该有序半段，将 l 或 r 收缩一半 |
mid | int | 定义：当前区间中点下标 (l + r) // 2维护：将区间切成左段 [l, mid] 与右段 [mid+1, r]，其中至少有一段仍是升序更新：每轮二分重新计算；若 nums[mid] == target 直接返回 |
有序半段判定 | bool | 定义：用 nums[l] <= nums[mid] 判断左半是否升序，否则右半 [mid+1, r] 升序维护：旋转数组任意时刻都只有「断点」一侧无序，另一侧保持原升序 更新：在有序半段上用普通二分条件 nums[l] <= target < nums[mid] 或 nums[mid] < target <= nums[r] 决定往哪边缩 |
落码步骤
1. 初始化 l = 0、r = len(nums) - 1
2. 当 l <= r：取 mid = (l + r) // 2，若 nums[mid] == target 返回 mid
3. 若 nums[l] <= nums[mid]（左半升序）：若 nums[l] <= target < nums[mid] 则 r = mid - 1，否则 l = mid + 1
4. 否则（右半升序）：若 nums[mid] < target <= nums[r] 则 l = mid + 1，否则 r = mid - 1
5. 循环结束返回 -1
代码实现
class Solution:
def search(self, nums: list[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]: # 左半 [l, mid] 升序
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # 右半 [mid+1, r] 升序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // 左半 [l, mid] 升序
if (nums[l] <= target && target < nums[mid])
r = mid - 1;
else
l = mid + 1;
} else { // 右半 [mid+1, r] 升序
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
}
}
return -1;
}
};
// 时间 O(log n)，空间 O(1)复杂度分析
O(log n)
O(1)
常见坑
左半有序时用 nums[l] <= target < nums[mid]（右边界不含 mid），右半有序时用 nums[mid] < target <= nums[r]——与已排除的 nums[mid] 对称，避免死循环。
误判哪一半有序：必须比较 nums[l] 与 nums[mid]，不能只看 nums[mid] 与 nums[r] 的大小关系。
忘记 nums[mid] == target 的提前返回：虽然范围判断有时也能收敛到 mid，但显式判断更清晰且避免边界遗漏。
必测边界 Case
nums = [1], target = 1 → 0
nums = [1], target = 0 → -1
nums = [1,3,5], target = 3 → 1（退化为普通二分，左半始终升序）
nums = [4,5,6,7,0,1,2], target = 0 → 4（首轮排除左半升序段，次轮在右半升序段命中）