搜索旋转排序数组这道题几乎每个刷力扣的人都绕不过去。我第一次做的时候第一反应是都旋转过了还怎么二分后来才发现旋转恰恰是这道题的题眼——它把数组切成了两段每段内部依然有序。如果你正准备面试、在刷力扣热题100或者想在二分查找这个考点上建立自己的解题模板这题值得放到进度单最前面。网上题库版本很多有标成第66题的也有写第33题的反正都是同一个 Search in Rotated Sorted Array力扣官网直接用题面就能搜到。今天我把完整推导、三种语言实现和相关变种题一起整理出来。搜索旋转排序数组的表面问题是在一个经过旋转的升序数组里找目标值真正考的是你对二分查找边界条件的理解。暴力遍历当然能过但面试官想听的是 O(log n) 的解法。接下来我会从旋转数组的结构讲起逐步拆到代码边界再延伸到几道高频变种题。1. 旋转数组的结构为什么一分为二后仍有有序段1.1 一次旋转动作究竟改变了什么先看一个最朴素的例子原数组是[0,1,2,3,4,5,6,7]在索引 4 的位置旋转就得到[4,5,6,7,0,1,2,3]。这种操作在很多算法书里叫循环右移你可以理解为把末尾的一段搬到开头也可以理解为把数组从某个切点断开后交换两部分的位置。旋转后数组看起来乱了但它有两个关键特征数组被切成了两段每一段内部仍然保持严格递增。第一段的所有元素都大于第二段的所有元素前提是确实发生过旋转且数组原本严格升序。举个例子就清楚[4,5,6,7,0,1,2,3]中[4,5,6,7]是一段[0,1,2,3]是另一段。4 到 7 递增0 到 3 也递增但 7 到 0 是断的。这个断点就是旋转点也叫最小值所在的位置。判断数组到底有没有旋转可以直接比较nums[0]和nums[nums.length-1]。如果nums[0] nums[last]说明旋转了如果nums[0] nums[last]说明数组整体没有旋转本来就是普通升序。这个细节后面写代码时很有用尤其是处理无旋转的测试用例。1.2 普通二分为什么在这里失效普通二分查找有一个前提整个数组单调有序。这样我们可以通过比较nums[mid]和target的大小直接决定继续搜索左半部分还是右半部分。但旋转数组不是全局有序的nums[mid]比target大时目标既可能在 mid 左边也可能在 mid 右边。我习惯用一个路况类比一条公路中间某处塌方了路面被分成两段每段内部的路标仍然连续但从断点处无法直达。你在其中一段上做判断不能只盯着当前路标得先搞清楚自己站在哪一段以及目标在哪一段。放到数组里就是mid左边和右边必然有一边是完整有序的我们要先判断出哪边有序再决定去留。1.3 两个有序段的使用策略假设搜索区间是[left, right]中间位置是mid。核心判断只有两句如果nums[left] nums[mid]说明左半段[left, mid]是完整递增的。此时先看target是否落在[nums[left], nums[mid])范围内。落在左段就去左半段找否则去右半段。如果nums[left] nums[mid]说明旋转点切在了左半段那么右半段[mid, right]才是完整递增的。此时看target是否落在(nums[mid], nums[right]]范围内。落在右段就去右半段找否则去左半段。为什么要先判断哪段有序因为有序区间内的判断是可靠的目标值如果落在有序区间的端点之间说明它一定可以在这段里用普通二分的思路继续收缩如果不在这个区间那它只可能出现在另一段。每次循环都能把搜索范围缩掉一半整体就是 O(log n)。2. 二分查找的判定细节为什么判断左段有序用 而不是 2.1 mid 落在哪一段是分水岭我用两个具体例子演示一下判定过程。例子 Anums [4,5,6,7,0,1,2], target 1初始left0, right6, mid3。此时nums[mid] 7nums[left] 4满足4 7所以左半段有序。再看target1是否落在[4,7)里显然不在于是left mid 1 4。下一轮mid5, nums[mid]1命中。例子 Bnums [5,6,7,0,1,2,4], target 6初始left0, right6, mid3。此时nums[mid] 0nums[left] 5不满足5 0所以左半段不是完整有序。那么右半段[3,6]也就是[0,1,2,4]是完整递增的。现在检查target6是否落在(0,4]不在于是rightmid-12。下一轮在[5,6,7]里找很快命中。这两个例子说明nums[left] nums[mid]这个判断本质上是在回答mid 是否和 left 位于同一个递增段里。如果是左段有序如果不是说明 mid 已经跑到了第二段真正的旋转点在 left 和 mid 之间。2.2 边界相等的情况两个元素时的特殊处理当区间缩小到只剩两个元素时比如nums[1,3]left0, right1, mid0此时nums[left] nums[mid]成立程序会走进左段有序分支。因为左段只有一个元素[1]它确实是有序的这个结果没问题。但如果用来判断nums[left] nums[mid]变成 false程序会错误地走进右段有序分支。虽然在一些特定写法里也能补救但很容易把思路绕进去。所以我个人强烈建议判断左段有序的条件写成nums[left] nums[mid]把等于的情况归为左段有序。等于是单个元素也算一段有序序列逻辑上更干净。2.3 别把 target 的等于号写丢再看两条区间判断条件的细节# 左段有序时 if nums[left] target nums[mid]: right mid - 1 else: left mid 1 # 右段有序时 if nums[mid] target nums[right]: left mid 1 else: right mid - 1为什么左段有序分支里target和nums[mid]比较时是严格小于因为在进入分支前我们已经单独判断过if nums[mid] target: return mid既然nums[mid]已经排除了等于 target 的情况那么在后续判断里只需要考虑严格小于或严格大于。如果你一样都写成了处理起来也不会有大错但逻辑会变得含糊调试时很难一眼看出问题。右段有序分支同理nums[mid] target是严格大于因为等于的情况已经被前置判断拦截了。这里我踩过不止一次把写错位置导致返回结果差一位。后来养成了习惯写完整段代码后先拿[3,1]、[1,3]这种两个元素的极端用例跑一遍再提交。3. 三种语言实现从逻辑到代码的完整映射3.1 Python 版本最直观的写法def search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid # 左半段有序 if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 # 右半段有序 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1这段代码看起来短但每一行都有讲究。mid left (right - left) // 2不使用(left right) // 2唯一原因是让相同逻辑迁移到 Java、C 时也能避免整型溢出。Python 的 int 没有溢出问题写成这样只是为了统一习惯。测试用例可以这样验证输入: nums [4,5,6,7,0,1,2], target 0 过程: mid 依次检查 7、0最终返回 4 输入: nums [4,5,6,7,0,1,2], target 3 过程: 所有元素检查完毕后退出循环返回 -1 输入: nums [1], target 0 过程: left0, right0, mid0, nums[0]!0, 返回 -13.2 Java 版本注意溢出和位运算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; }Java 里最容易翻车的点是left right溢出。当nums.length接近Integer.MAX_VALUE时left right可能超过 int 范围。所以计算 mid 必须写成left (right - left) / 2。我见过不少人在本地小数组上测试正常一提交就报错多半就是这里溢出了。还有一点Java 条件里不能像 Python 那样写链式比较必须把nums[left] target target nums[mid]拆开写。两种语言混着刷的人经常在这个地方手滑漏了后半句。3.3 C 版本和 STL 风格保持一致class Solution { public: int search(vectorint nums, int target) { int left 0; int right nums.size() - 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; } };C 写法和 Java 几乎一致唯一要留意的是nums.size()返回的是size_t类型无符号数。如果直接把它赋给 int在数组为空时nums.size() - 1会变成一个巨大值导致越界访问。所以要么先判空要么像上面这样用int right nums.size() - 1;并在进入前确认nums非空。3.4 时空复杂度与典型用例对比语言核心写法时间复杂度空间复杂度注意事项Python链式比较清晰O(log n)O(1)无溢出风险但需注意缩进Java拆开 比较O(log n)O(1)防止 leftright 溢出C拆开 比较O(log n)O(1)防止 size_t 类型转换问题补一组最常见的边界用例写完后务必自测[1,3] 找 3 - 1 [3,1] 找 1 - 1 [1,2,3,4] 找 2 - 1 无旋转的情况 [1,2,3,4] 找 5 - -1 [1] 找 0 - -1无旋转数组是很容易被忽略的输入。因为nums[left] nums[mid]全程成立每个循环都会走进左段有序分支左段就是整个数组判断逻辑会逐渐退化成普通二分查找所以不会出错。这也是模板设计时隐含的一个优点。4. 高频变种找最小值、允许重复、旋转点定位4.1 找旋转数组的最小值力扣原题里搜索旋转排序数组是 33 题找旋转数组的最小值在力扣是 153 题面试中经常成对出现。思路其实更简单我们不需要某个 target只需要不断缩小区间让 left 和 right 最终指向最小值。def findMin(nums): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[right]: left mid 1 else: right mid return nums[left]这个代码的内部逻辑是如果nums[mid] nums[right]说明 mid 在左段最小值在右段所以移动left mid 1否则 mid 可能在右段或者右段完全有序最小值在 mid 或 mid 左边就移动right mid。注意这里用的是left right不是left right。因为找最小值最终区间会收敛到left right如果再进入循环可能出现死循环。和左侧搜索 target 的模板不同找最小值天然适合左闭右开式收缩。4.2 允许重复元素原题从 33 变 81很多场景下数组并不严格递增可能有重复值比如[2,2,2,0,2,2]。这种情况下nums[left] nums[mid]虽然仍成立但无法区分 mid 到底在左段还是右段因为中间出现了大量相等元素旋转点被藏起来了。处理方式比较粗暴但有效当nums[left] nums[mid] nums[mid] nums[right]时我们无法判断哪侧有序只能把 left 和 right 同时向中间收缩一步比如left和right--然后再继续二分。这样会破坏 O(log n) 的严格保证最坏情况变成 O(n)但这也是唯一能保证正确性的通用办法。def searchWithDuplicates(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return True if nums[left] nums[mid] nums[right]: left 1 right - 1 elif nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return False这个变种在力扣是 81 题面试时如果先问你 33 题大概率会紧跟一句如果有重复元素该怎么改所以最好提前把这一版也准备好。4.3 找旋转点用二分定位断层位置严格意义上的旋转点就是nums[i] nums[i1]的那个位置。最简单的方法是线性扫描但既然题目强调 O(log n)我们还是用二分找最小值的位置最小值所在下标就是旋转点。举个例子[4,5,6,7,0,1,2]中最小值是 0下标为 4那么旋转点就在下标 4。旋转点往前的元素[4,5,6,7]是原数组尾部旋转点往后的元素[0,1,2]是原数组头部。一旦找到了旋转点整个数组的真相就还原了。实际项目里这种问题也不少见。我做过日志采集系统的时间戳数组、监控指标的采样序列因为服务重启或数据回填经常出现有序但分段的情况。这时候通用的查找逻辑基本就是在数组上做旋转点定位加区间二分。4.4 变种题对比一份模板解决四道题题目场景循环条件核心判断返回结果最坏复杂度搜索目标值(无重复)left rightnums[left] nums[mid]目标下标/-1O(log n)搜索目标值(有重复)left right相等时 left/right--是否存在O(n)找最小值(无重复)left rightnums[mid] nums[right]nums[left]O(log n)找旋转点left right同上最终下标即旋转点下标O(log n)可以把这个表格当成刷题自查清单。今天这篇博文主要解决第一行后三行是很好的延伸练习。5. 刷这题踩过的坑与落地模板5.1 循环条件用 left right 还是 left right很多初学者在这道题上迷茫不是因为判断逻辑不会写而是分不清循环条件。我的经验是分场景要查找某个确切值用while (left right)。循环结束后 left right说明没找到。要查找最小值、旋转点用while (left right)。循环结束后 left 和 right 重合这个位置就是答案。如果把查找 target 的代码改成left right那么循环提前结束最后还要补一句if nums[left] target: return left有些选手习惯这种写法也不是不行。但为了减少思考负担我建议查找值就用left right找位置就用left right形成肌肉记忆。5.2 最前面判断 nums[mid] target我之前犯过一个错误不在循环开头判等而是把等于情况混进区间条件里。比如if nums[left] target nums[mid]时移动 right否则移动 left最后在循环外面返回。这样写初看也没问题但遇到目标元素恰好就是 nums[mid] 时边界处理会变得非常绕到底是走 left 分支还是 right 分支你可以推导出来但很容易在面试白板上卡壳。正确做法是把if nums[mid] target放在最开头后续区间判断里只保留严格的和。这样每一步的逻辑都非常纯粹先回答中位数是不是答案再回答该去哪半边找。5.3 无旋转输入别翻车有些测试用例刻意不给旋转数组比如[1,2,3,4,5]。如果模板里有一句判断如果nums[left] nums[right]直接普通二分当然可以但即使不写也不会出错因为我们前面的nums[left] nums[mid]分支始终成立每次都把区间按普通二分的方式收缩。它不会漏掉任何情况。但要注意不能在代码里写如果nums[0] nums[last]就直接返回 -1因为 target 可能是正常存在于数组中的。我见过有同学试图用旋转标志提前过滤结果把无旋转但 target 存在的用例给过滤掉了。5.4 我最终固定下来的手写模板经过多次踩坑后我刷搜索旋转排序数组类题目时固定使用下面这套思路基本五分钟能写完1. 初始化 left0, rightn-1。 2. 循环 left right。 3. mid left (right-left)//2。 4. if nums[mid] target返回 mid。 5. if nums[left] nums[mid] 左段有序target 在 [nums[left], nums[mid]) 就收缩 right否则收缩 left。 6. else 右段有序target 在 (nums[mid], nums[right]] 就收缩 left否则收缩 right。 7. 循环结束返回 -1。这套模板的好处是所有等于号的位置都是固定的mid 与 target 的比较在开头左段有序判断用左段区间判断用 target mid右段区间判断用mid target 。只要把这四个位置记住代码就不会出现边界错误。再分享一个调试技巧。如果本地测试出现死循环通常问题出在两处一是该用left right却用了left right二是mid left (right - left) // 2写成了向上取整。遇到这种情况不要直接改循环条件先在纸上画一个长度为 4 或 5 的数组手动算一轮 left、mid、right 的变化很快就能定位是哪个分支没走对。搜旋转排序数组这道题看起来只是一道二分查找但它把有序性判断边界处理退化场景三个知识点全考了一遍。我后来刷力扣热题100凡是二分相关题目几乎都拿它当基准模板。面试前如果时间紧我只复习两题普通二分查找和搜索旋转排序数组因为由后者延伸出去的最小值、重复值、旋转点等变种都是同一套思维方式。