★ FEATURED ARTICLE 刷力扣的绕不开这道题搜索旋转排序数组。大家习惯简称“旋转数组”它在二分查找的变形题里出镜率极高面试里只要考二分基本就是从这道题往上加码。题目本身不难难的是把“旋转”这个动作在有序性上造成的破坏讲清楚然后把二分思路捋直否则代码背下来了换个条件照样错。这篇就按我实际刷题和给别人讲题的思路把搜索旋转排序数组从题目本质、核心规律到两种代码写法、边界坑位一次说透适合刚刷到二分的新手也适合准备面试想快速复盘的人。搜索旋转排序数组的题面其实不长一个原本升序排列的数组在某个未知的位置被旋转了一次比如[1,2,3,4,5,6,7]在索引3处旋转后就变成[4,5,6,7,1,2,3]现在给你一个target让你在这个数组里搜索找到返回下标找不到返回-1而且算法复杂度必须做到O(log n)。1. 破题前先想清楚旋转数组到底破坏了什么很多新手一上来就背“找到旋转点再二分”的模板没搞懂背后的原理导致题目稍微变一变就懵。所以先花点时间把旋转数组这个模型彻底吃透后面一切顺理成章。1.1 旋转不会改变“局部有序”这个事实数组被旋转之前是全局升序旋转一刀切下去数组被分成两段每段各自仍然保持升序。举例来说[0,1,2,4,5,6,7]以[4,5,6,7]和[0,1,2]两段拼合前一段的元素全部大于后一段的元素。这个特征非常重要整个数组不是全局有序但任意位置看至少有一半是有序的。这句话就是所有旋转数组二分解法的理论基础。你不需要找到确切的旋转点也能做二分因为每一轮你都能判断出哪半边是单调递增的然后往有把握的那一半收缩。可以类比成这样你手里有一叠编号连续的扑克牌从中间一分为二把下半叠直接放到上半叠前面。牌面整体乱了可每一叠内部还是按顺序排的。你找某张牌时永远可以判断目标是否落在某一叠内部如果不在它就一定在另一叠里。1.2 为什么暴力扫描不可行最直接的办法是for i in range(n)扫一遍找到就返回下标。这当然能过时间复杂度是 O(n)。但题目明确要求 O(log n)这就意味着面试官在期待你用二分。O(n) 的解法在这道题里不是“能不能做出来”的问题而是“有没有理解二分思想”的问题。很多人觉得刷题只是为了通过但面试官真正考察的是你在有序性被破坏后能不能依然找到利用有序性的方式。换个角度想[4,5,6,7,0,1,2]这个数组里你随便取中点nums[3] 7它会告诉你哪些信息它至少告诉你两件事中的一件左半边完全是升序的或者右半边完全是升序的。这就是突破口。1.3 关键结论任意中点总有一半是有序的这一点需要反复在心里默念它比任何代码模板都重要。假设数组长度为 n取mid (left right) // 2如果nums[left] nums[mid]说明左半边是严格升序的否则说明右半边是严格升序的。为什么会成立因为旋转数组只被切了一次最多只有一个“断裂点”。中点mid要么落在断裂点左边要么落在断裂点右边。如果落在左边那么[left, mid]这一段没跨过断裂点必然有序如果落在右边那么[mid, right]这一段没跨过断裂点也必然有序。用生活化的说法一叠牌被拦腰换位后你随便抽出中间一张这张牌的左边或者右边总有一边是没被“切断”的完整顺序段。2. 解法一先找旋转点再按需二分这个思路很好理解分两步走先找出旋转点也就是整个数组最小元素的位置此时左半段[0, pivot-1]是升序右半段[pivot, n-1]也是升序。接下来判断target落在哪一段对那一段做常规二分。第一步是“找旋转点”第二个“搜索目标值”两步都是二分总复杂度还是 O(log n)。2.1 找旋转点的二分策略找旋转点的本质是在数组里找到最左侧的、小于或等于其前一个元素的位置。也就是说我们要找那个“最小值”出现在哪里。用二分查找旋转点的核心比较条件是nums[mid]与nums[right]的大小关系如果nums[mid] nums[right]旋转点一定在mid的右侧所以left mid 1否则旋转点在mid或其左侧所以right mid。为什么和nums[right]比而不是和nums[left]比因为nums[right]永远位于旋转数组的右半段它是右半段中的某个位置。如果nums[mid] nums[right]说明mid跨过了旋转点旋转点在右边否则mid和right处于同一段内部旋转点一定更靠左。这个逻辑只要画一个数组就能想明白。旋转点查找代码def find_pivot(nums): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] nums[right]: left mid 1 else: right mid return left注意这里的循环条件是left right不是left right因为我们要的是“收缩到一个点”。当left right时这个位置就是旋转点。2.2 根据旋转点确定搜索区间拿到旋转点pivot后整个数组被分成两段左段[0, pivot-1]所有元素都大于等于nums[pivot]右段[pivot, n-1]所有元素都小于等于nums[pivot]。这时候要判断target落在哪一段。一个保险的做法是先看target和nums[pivot]的大小关系如果target nums[pivot]直接返回pivot如果target nums[0]说明目标在左段旋转点左侧到[0, pivot-1]里二分否则说明目标在右段旋转点右侧到[pivot1, n-1]里二分。因为左段整体是从小到大右段也是从小到大到了这里就退化成了普通的二分查找。完整代码如下def search(nums, target): n len(nums) if n 0: return -1 if n 1: return 0 if nums[0] target else -1 pivot find_pivot(nums) if nums[pivot] target: return pivot if target nums[0]: left, right 0, pivot - 1 else: left, right pivot 1, n - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1可以发现代码基本分两大块逻辑非常直白适合面试时先讲思路再写代码。缺点是想让代码简洁的话需要把“普通二分”这块单独抽成一个辅助函数不然主函数里会出现两处循环看起来有些啰嗦。2.3 这种解法的边界注意点有几个细节容易写错单独拎出来说一下如果数组没有发生旋转也就是pivot 0此时第二段就是整个数组第一段为空。这时target nums[0]会在整个数组里二分逻辑依然正确不需要特殊处理。需要注意的是第一个搜索区间[0, -1]是空区间不会进入循环所以不会出错。找旋转点时nums[mid]和nums[right]的比较必须用不能用。因为在没有任何旋转的纯升序数组里会把left一步步向右推最后得到pivot n-1虽然不影响普通情况的搜索但它在逻辑上不符合“pivot 是最小元素”的定义遇到重复元素的题目会直接出问题。不要忘了判断nums[pivot] target。我见过不少人在最后二分时忘记这一步结果target正好是旋转点元素时搜索区间把pivot排除在外直接返回-1。3. 解法二一次二分直捣黄龙先找旋转点的思路虽然清晰但代码里包含了两段几乎独立的二分逻辑面试手写的时候稍微紧张就容易漏掉细节。还有另一种更优雅的写法一轮循环里同时判断有序区间和目标位置不单独找旋转点。这种解法更短面试时也更常见因为逻辑链条紧凑能直接体现你对旋转数组规律的理解深度。3.1 每一轮循环里做三件事在常规二分基础上每轮循环多两步判断先确认哪半边是有序的再判断target是否落在这个有序半边里决定往哪边收缩。具体判断流程如下计算mid (left right) // 2如果nums[mid] target直接返回如果nums[left] nums[mid]说明左半边有序当nums[left] target nums[mid]时目标在左半边right mid - 1否则目标在右半边left mid 1否则说明右半边有序当nums[mid] target nums[right]时目标在右半边left mid 1否则目标在左半边right mid - 1。核心逻辑就一句话按照nums[left]与nums[mid]的关系锁定有序段再用区间端点判断target在不在这个区间里。3.2 一次二分的代码实现代码很短但是边界条件里每一处大小比较都要想明白def search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 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这段代码里有两处容易写错的点一处是判断左半边有序时target的比较范围是nums[left] target nums[mid]注意这里的左边界是闭的右边界是开的另一处是判断右半边有序时target的范围是nums[mid] target nums[right]左边界开右边界闭。这个开闭关系非常重要因为nums[mid]已经在前面被判断过不等于target了所以区间里排除mid是安全的。3.3 一次二分与二次二分的实战取舍两种方法各有优劣我放一张对比表面试前可以扫一眼对比项先找旋转点再二分一次二分直接搜索代码结构两段独立二分逻辑清晰易懂一个循环内嵌套多重条件判断紧凑理解成本低适合先讲给面试官听稍高需要对有序区间判断非常熟练边界情况处理需要额外处理pivot target天然兼容各种边界无需额外逻辑手写出错率容易漏掉nums[pivot] target的判断容易把区间开闭判断写反我个人的建议是如果你刚开始刷题先把解法一彻底搞懂因为它把“找最小值”和“普通二分”两个子问题拆开了每一块的逻辑都足够简单可以独立验证当你对旋转数组规律已经非常熟悉时就可以直接上手解法二因为它才是面试里最常被期望写出的解法——代码短、循环次数少、边界统一。4. 边界条件、坑位排查与实战扩展刚才两种解法都跑通了不代表这道题就算结束了。真正拉开差距的地方在于边界条件和题目扩展。我平时给别人review 代码时发现大部分错误不是出现在主体逻辑上而是出现在边界比较和循环条件的细节上。4.1 边界情况速查表场景数组样例预期结果易错点只有一个元素[1], target1返回0循环可以直接处理但是很多代码会单独开头判断只有一个元素且不存在[1], target2返回-1同上完全未旋转[1,2,3,4,5], target3返回2旋转点逻辑要退化得正常旋转后最小元素是第一个[1,2,3,4,5], target4返回3pivot0时要能正确处理target 正好是旋转点[4,5,6,7,0,1,2], target0返回4容易在区间判断时漏掉这个位置target 位于旋转点左侧[4,5,6,7,0,1,2], target5返回1区间划分要准确target 位于旋转点右侧[4,5,6,7,0,1,2], target2返回6区间划分要准确target 不存在[4,5,6,7,0,1,2], target3返回-1死循环风险建议你把这几种情况逐一在代码上跑一遍特别是“完全未旋转”和“旋转点在最左侧”两种情况。这两类情况最容易让第一次写旋转数组二分的人翻车因为它们的区间划分逻辑和标准二分很像但又不完全一样。4.2 最容易踩的几个坑第一个坑是比较对象选错。很多新手在判断哪半边有序时会用nums[mid]和nums[target]去比这完全是概念混淆。我们要判断的是“数组结构上哪一侧有序”这只能通过nums[mid]和数组端点nums[left]或nums[right]比较得出。target是你要找的值它只参与“目标在不在这个有序区间内”的判断不参与“哪半边有序”的判断。第二个坑是循环条件不清。找旋转点时用while left right搜索目标时用while left right。前者是因为旋转点一定存在我们要找的是一个位置而不是判断存在性后者是要确保left right时循环还能进去再检查一次nums[mid]。这两个条件不能混用混用了要么死循环要么漏搜索。第三个坑是二分区间更新成死循环。常见错误是在某一步写了left mid或者right mid而不是left mid 1/right mid - 1。在二分法里只要区间长度不小于2就必须往中间收缩否则left和right永远卡在原地。这道题里搜索目标值的循环是标准二分必须写成1/-1只有找旋转点时right mid才是合理的因为mid本身可能就是你想要的旋转点。第四个坑是重复元素带来的不确定性问题。力扣原题的数组里没有重复值但如果扩展成nums [1,1,1,0,1]这种二分就可能失效。原因是当nums[left]、nums[mid]、nums[right]三者相等时你无法判断旋转点在左还是在右必须退化成线性扫描。这不是这道题的重点但面试官很喜欢把它作为追问。遇到这种情况的判断条件通常写成if nums[left] nums[mid] nums[right]: left 1 right - 1这样逐步缩小区间虽然最坏复杂度退化为 O(n)但在没有重复或少量重复的数组上依然高效。4.3 从这道题延伸出去的相关题型搜索旋转排序数组不是孤立的一道题它和另外几个经典题共享同一个底层模型寻找旋转排序数组中的最小值对应的就是find_pivot那一段逻辑把二分思想单独抽出来考察算是搜索旋转数组的前置题。寻找旋转排序数组中的最小值 II在上一题基础上加入重复元素需要退化为线性处理正好验证你对重复值问题的理解。搜索旋转排序数组 II在原题基础上加入重复元素处理方式和“最小值 II”类似循环内加一个去重判断即可。如果能把这三道题放在一起刷一遍你对旋转数组二分的理解就会非常扎实。因为它们本质上都是围绕“数组被截断成两段、每段有序”这个模型展开解题框架完全一致只是目标从“找某个值”变成“找最小值”“找峰值”等等。4.4 答题时的表述建议面试里写出代码只是第一步关键还要能把思路讲清楚。我推荐的表述顺序是先说普通二分为什么用不了——数组不再是全局有序然后指出关键规律——任意中点把数组分成两半至少有一半是有序的接着说明策略——在每一轮里判断哪半边有序再判断 target 是否落在该半边落在哪个半边就收缩到哪个半边最后提边界——空数组、单元素数组、无旋转数组都能自动处理。这种讲法既体现了分析问题的过程又不会让面试官觉得你在背题。相比上来默写代码从规律推导出解法的逻辑链条才是面试官想听的。我个人刷这道题时最深的体会是不要急着看题解先自己画几个旋转数组观察中点和左右端点的关系。画上几轮之后你会很自然得出一半有序的结论代码就是结论的自然产物。踩过一次nums[left] nums[mid]还是nums[right]的比较坑之后我就养成一个习惯只要遇到旋转数组先问自己三个前提——哪个端点可以当作基准、哪一半有序、target 落在哪个区间里。这三个问题想清楚代码怎么写都不会偏。
阅读完成 · 觉得有帮助？
