33. 搜索旋转排序数组 | 难度中等1. 题意理解用样例说话先看题目给的例子nums [4,5,6,7,0,1,2], target 0这个数组原本是[0,1,2,4,5,6,7]在下标k4处向左旋转后变成上面的样子。关键观察旋转后的数组虽然整体不再有序但它有一个重要性质——把数组从任意位置切成两半至少有一半是有序的。为什么因为旋转只是把数组掰了一下。拿[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 的查找过程步骤lr当前窗口mnums[m]snums[l]enums[r-1]nums[m] s?在哪一半目标区间判断行动107[4,5,6,7,0,1,2]3742✅左有序target0 不在 [4,7)搜右边l4247[0,1,2]5102✅左有序target0 在 [0,1)搜左边r5345[0]4000✅左有序nums[m]target返回 4输出4target 0 在原数组的位置如果 target 不存在比如target 3步骤lrmnums[m]se判断行动1073742左有序, 3∉[4,7)l42475102左有序, 3∉[0,1)l63676222左有序, 3∉[2,2)l7477————lr 退出返回 -12. 解法思路核心直觉普通二分为什么不行普通二分查找依赖一个前提数组全局有序。nums[m] target时我们知道答案一定在左半边。但在旋转数组中nums[m] target不能告诉我们方向因为数组是弯的。关键利用一半有序虽然全局无序但我们能保证以 m 为界左边和右边至少有一半是从小到大有序的。怎么判断哪一半有序只需要比较nums[m]和窗口左边界nums[l]如果nums[m] nums[l]左半[l, m]是递增的。因为旋转点一定不在这一段。如果nums[m] nums[l]说明跨越了旋转点左半不是递增的那右半[m, r-1]一定是递增的。一旦确定了哪一半有序就做两件事检查 target 是否落在这个有序半区的范围内。如果在就在这个半区继续搜否则去另一半。┌─────────────────────────────────┐ │ nums[m] nums[l] ? │ └──────────┬──────────────────────┘ │ ┌───────────┴───────────┐ ▼ ▼ 左半有序 右半有序 [l, m] 递增 [m, r-1] 递增 │ │ target 在 target 在 [nums[l], nums[m]) ? (nums[m], nums[r-1]] ? │ │ ┌─────┴─────┐ ┌─────┴─────┐ ▼ ▼ ▼ ▼ 是 否 是 否 r m l m1 l m1 r m (去左边) (去右边) (去右边) (去左边)为什么用而不是考虑只剩一个元素的情况l m此时nums[m] nums[l]。如果写成nums[m] nums[l]严格大于这个条件为 false程序会误判为右半有序然后去检查(nums[m], nums[r-1]]——但此时m r-1右半区间为空逻辑就乱了。用保证单个元素也被正确处理为左半有序。为什么每轮都要重新算s和es nums[l]和e nums[r-1]是当前搜索窗口的左右边界值。窗口每轮都在缩小边界值当然也跟着变。把它们放在循环体内更新是必要的。3. 代码实现参考你提供的代码我们可以这样实现逐行注释classSolution{public:intsearch(vectorintnums,inttarget){// 使用半开区间 [l, r)所以 r 初始化为 nums.size()intl0,rnums.size();// s 和 e当前搜索窗口的左右边界值intsnums[0],enums[r-1];intret-1;while(lr){// 半开区间l r 时区间为空intm(lr)/2;// 每轮更新窗口边界值——窗口缩小了边界也跟着变snums[l];enums[r-1];if(nums[m]target){retm;break;}// 情况1m 在左半有序区nums[m] 窗口左边界值elseif(nums[m]s){// target 落在 [s, nums[m]) 这个有序区间内吗// 注意这里用 nums[m] target 等价于 target nums[m]// 因为前面已经排除了 nums[m] target 的情况if(stargetnums[m]target){rm;// 在左半收缩右边界}else{lm1;// 不在左半去右边}}// 情况2m 在右半有序区跨越了旋转点右半才是递增的else{// target 落在 (nums[m], e] 这个有序区间内吗if(nums[m]targettargete){lm1;// 在右半收缩左边界}else{rm;// 不在右半去左边}}}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]让单元素区间也被正确处理。坑2target 区间判断的边界开闭在nums[m] s分支中我们检查 target 是否在[s, nums[m])范围内——左闭右开。因为如果target nums[m]前面已经 return 了所以用 target或 target都可以。写成if(stargetnums[m]target)// target ∈ [s, nums[m])这里s target是而不是因为 target 可能正好等于窗口左边界值。写成会漏掉这个情况导致无限循环或错误结果。在 else 分支中同理检查的是(nums[m], e]——左开右闭if(nums[m]targettargete)// target ∈ (nums[m], e]target e用是正确的因为 target 可能正好等于窗口右边界值。坑3l m 1还是l m半开区间[l, r)下要排除 m 去右边 →l m 1因为 nums[m] 已经检查过了要排除 m 去左边 →r m因为 r 是开边界自然排除 m写成l m会导致死循环当r l 1时m ll 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有人会这样写intsnums[0],enums.back();// 只在循环外初始化一次while(lr){// s 和 e 始终是初始数组的首尾值不会随窗口缩小而更新if(nums[m]s){...}}这是错的。随着l和r移动窗口边界变了s和e必须反映当前窗口的边界值所以每轮都要s nums[l]; e nums[r-1];。5. 相关题目题号题目关联点81搜索旋转排序数组 II允许重复元素需要额外处理nums[l] nums[m] nums[r-1]的情况153寻找旋转排序数组中的最小值同样利用一半有序性质但目标从查找特定值变成了找最小值的拐点154寻找旋转排序数组中的最小值 II153 的带重复元素版本6. 总结这道题的核心收获“全局不有序 ≠ 二分不能用”。只要每次能判断目标在哪一半二分就成立。旋转数组的特殊之处在于虽然整体有序性被破坏但每次切分后必有一半是有序的——这是本题能用 O(log n) 的根本原因。边界条件的精度决定成败。vs、vs、开区间 vs 闭区间——二分查找的每一个等号都不是随意的。写完后用一个元素的数组[1] target1、两个元素的数组[3,1] target1这类极端 case 验证一遍大部分边界 bug 会立刻暴露。可泛化的原则当需要在部分有序的结构中搜索时不要试图还原整个有序结构——找到那个局部不变量本题中是切分后必有一半有序然后围绕它设计判断逻辑。