33. 搜索旋转排序数组(leetcode每日一题)

33. 搜索旋转排序数组 | 难度：中等

1. 题意理解（用样例说话）

先看题目给的例子：

nums = [4,5,6,7,0,1,2], target = 0

这个数组原本是[0,1,2,4,5,6,7]，在下标k=4处向左旋转后变成上面的样子。

关键观察：旋转后的数组虽然整体不再有序，但它有一个重要性质——把数组从任意位置切成两半，至少有一半是有序的。

为什么？因为旋转只是把数组"掰"了一下。拿[4,5,6,7,0,1,2]来说：

7 6 \ 5 0 4 1 2 切一刀 → 左半 [4,5,6] 有序 ✓ 右半 [7,0,1,2] 无序 ✗ 左半 [4,5,6,7] 有序 ✓ 右半 [0,1,2] 有序 ✓

这个性质就是我们用二分查找的入口。

样例推演

用表格跟踪 target = 0 的查找过程：

输出：4（target 0 在原数组的位置）

如果 target 不存在，比如target = 3：

2. 解法思路（核心）

直觉：普通二分为什么不行？

普通二分查找依赖一个前提：数组全局有序。nums[m] > target时，我们知道答案一定在左半边。

但在旋转数组中，nums[m] > target不能告诉我们方向，因为数组是"弯"的。

关键：利用"一半有序"

虽然全局无序，但我们能保证：以 m 为界，左边和右边至少有一半是从小到大有序的。

怎么判断哪一半有序？只需要比较nums[m]和窗口左边界nums[l]：

• 如果nums[m] >= nums[l]：左半[l, m]是递增的。因为旋转点一定不在这一段。
• 如果nums[m] < nums[l]：说明跨越了旋转点，左半不是递增的，那右半[m, r-1]一定是递增的。

一旦确定了哪一半有序，就做两件事：

1. 检查 target 是否落在这个有序半区的范围内。
2. 如果在，就在这个半区继续搜；否则去另一半。

┌─────────────────────────────────┐ │ nums[m] >= nums[l] ? │ └──────────┬──────────────────────┘ │ ┌───────────┴───────────┐ ▼ ▼ 左半有序 右半有序 [l, m] 递增 [m, r-1] 递增 │ │ target 在 target 在 [nums[l], nums[m]) ? (nums[m], nums[r-1]] ? │ │ ┌─────┴─────┐ ┌─────┴─────┐ ▼ ▼ ▼ ▼ 是 否 是 否 r = m l = m+1 l = m+1 r = m (去左边) (去右边) (去右边) (去左边)

为什么用>=而不是>？

考虑只剩一个元素的情况：l == m，此时nums[m] == nums[l]。

如果写成nums[m] > nums[l]（严格大于），这个条件为 false，程序会误判为"右半有序"，然后去检查(nums[m], nums[r-1]]——但此时m == r-1，右半区间为空，逻辑就乱了。

用>=保证单个元素也被正确处理为"左半有序"。

为什么每轮都要重新算s和e？

s = nums[l]和e = nums[r-1]是当前搜索窗口的左右边界值。窗口每轮都在缩小，边界值当然也跟着变。把它们放在循环体内更新是必要的。

3. 代码实现

参考你提供的代码，我们可以这样实现（逐行注释）：

classSolution{public:intsearch(vector<int>&nums,inttarget){// 使用半开区间 [l, r)，所以 r 初始化为 nums.size()intl=0,r=nums.size();// s 和 e：当前搜索窗口的左右边界值ints=nums[0],e=nums[r-1];intret=-1;while(l<r){// 半开区间：l == r 时区间为空intm=(l+r)/2;// 每轮更新窗口边界值——窗口缩小了，边界也跟着变s=nums[l];e=nums[r-1];if(nums[m]==target){ret=m;break;}// 情况1：m 在左半有序区（nums[m] >= 窗口左边界值）elseif(nums[m]>=s){// target 落在 [s, nums[m]) 这个有序区间内吗？// 注意：这里用 nums[m] > target 等价于 target < nums[m]，// 因为前面已经排除了 nums[m] == target 的情况if(s<=target&&nums[m]>target){r=m;// 在左半，收缩右边界}else{l=m+1;// 不在左半，去右边}}// 情况2：m 在右半有序区（跨越了旋转点，右半才是递增的）else{// target 落在 (nums[m], e] 这个有序区间内吗？if(nums[m]<target&&target<=e){l=m+1;// 在右半，收缩左边界}else{r=m;// 不在右半，去左边}}}returnret;}};

时间复杂度：O(log n)，每次迭代将搜索范围减半。

空间复杂度：O(1)，只用了常数个变量。

4. 易错点（这道题的坑真的不少）

坑1：>=还是>？（判断哪半有序时）

用nums[m] > nums[l]看似也可以——只要l != m。但当区间缩到只有一个元素（l == m）时，nums[m] > nums[l]为 false，程序会走进 “else” 分支，认为右半有序。但此时右半是空的，后续的区间判断就会完全错乱。

正确做法：始终用nums[m] >= nums[l]，让单元素区间也被正确处理。

坑2：target 区间判断的边界开闭

在nums[m] >= s分支中，我们检查 target 是否在[s, nums[m])范围内——左闭右开。因为如果target == nums[m]，前面已经 return 了，所以用< target或> target都可以。写成：

if(s<=target&&nums[m]>target)// target ∈ [s, nums[m])

这里s <= target是<=而不是<，因为 target 可能正好等于窗口左边界值。写成<会漏掉这个情况，导致无限循环或错误结果。

在 else 分支中同理，检查的是(nums[m], e]——左开右闭：

if(nums[m]<target&&target<=e)// target ∈ (nums[m], e]

target <= e用<=是正确的，因为 target 可能正好等于窗口右边界值。

坑3：l = m + 1还是l = m？

半开区间[l, r)下：

• 要排除 m 去右边 →l = m + 1（因为 nums[m] 已经检查过了）
• 要排除 m 去左边 →r = m（因为 r 是开边界，自然排除 m）

写成l = m会导致死循环：当r = l + 1时，m = l，l = m意味着 l 不移动。

坑4：初始值r = nums.size()vsr = nums.size() - 1

你的代码用了半开区间，所以r = nums.size()，搭配while (l < r)。

如果用闭区间写法r = nums.size() - 1，则搭配while (l <= r)，且停止条件、边界移动方式都要相应调整。两种写法都对，但必须配套。混用是最常见的 bug 来源。

坑5：忘记每轮更新s和e

有人会这样写：

ints=nums[0],e=nums.back();// 只在循环外初始化一次while(l<r){// s 和 e 始终是初始数组的首尾值，不会随窗口缩小而更新！if(nums[m]>=s){...}}

这是错的。随着l和r移动，窗口边界变了，s和e必须反映当前窗口的边界值，所以每轮都要s = nums[l]; e = nums[r-1];。

5. 相关题目

6. 总结

这道题的核心收获：

1. “全局不有序 ≠ 二分不能用”。只要每次能判断目标在哪一半，二分就成立。旋转数组的特殊之处在于虽然整体有序性被破坏，但每次切分后必有一半是有序的——这是本题能用 O(log n) 的根本原因。

2. 边界条件的精度决定成败。>=vs>、<=vs<、开区间 vs 闭区间——二分查找的每一个等号都不是随意的。写完后用一个元素的数组[1] target=1、两个元素的数组[3,1] target=1这类极端 case 验证一遍，大部分边界 bug 会立刻暴露。

3. 可泛化的原则：当需要在"部分有序"的结构中搜索时，不要试图还原整个有序结构——找到那个局部不变量（本题中是"切分后必有一半有序"），然后围绕它设计判断逻辑。