做算法题的人都知道LeetCode 33 题《搜索旋转排序数组》是个经典门槛很多人口语化地叫它“搜索平移递增数组”。第一次看到这类题目的人通常会愣一下数组明明不是整体有序的怎么用二分等到摸清规律之后又会发现它其实只是把二分查找的“判断条件”换了个花样核心骨架一点没动。今天就拿这个题目当引子把平移递增数组的搜索思路、无重复和有重复两版代码、以及那些容易让人栽跟头的边界情况一次讲透。这篇文章适合正在刷题准备面试的开发者也适合想补一补算法基础、单纯想弄明白“为什么这题能用二分”的读者。我会从定义开始讲内容不绕弯子最后还会给出一套可以直接拿去抄的模板代码以及我自己在实际面试和刷题过程中踩过的坑。1. 先把“平移递增数组”这五个字嚼碎1.1 什么样的数组叫平移递增数组先看定义。一个严格递增的数组比如[1, 2, 3, 4, 5, 6, 7]如果把它从某个位置“切断”再把前半段搬到后面去比如从 3 和 4 之间切断变成[4, 5, 6, 7, 1, 2, 3]这就是一个典型的平移递增数组。英文原题里叫 Rotated Sorted Array直译是“旋转排序数组”国内很多资料也叫它“循环有序数组”。这类数组有一个很关键的结构特征它整体不再单调递增但如果你把它从头到尾看一遍可以分成两段每一段内部依然是递增的。用[4, 5, 6, 7, 1, 2, 3]举例第一段是[4, 5, 6, 7]第二段是[1, 2, 3]。而且因为原始数组是递增的所以平移之后左半段的所有元素都大于右半段的所有元素前提是没有重复元素。这个“左段都大于右段”的性质是后面所有二分判断的基础。如果不做任何处理你要在一个可能平移过的数组里找一个数最简单的办法就是从头遍历但那就是 O(n) 的复杂度。而这一类题目存在的意义就是想利用数组“部分有序”的特点把查找效率提到 O(log n)。二进制搜索之所以能用靠的不是“数组整体递增”这个表面现象而是“借助局部信息可以确定性地排除一半元素”的能力。平移数组恰恰保留了这一点只是判断逻辑相对复杂了一些。1.2 为什么这个问题值得单开一篇因为它是二分查找从“常规”走向“变形”的第一个分水岭。普通人搜有序数组会写while (left right)然后比较中间值和目标值但遇到平移数组如果还用原来的逻辑结果往往是一顿操作猛如虎最后发现返回了 -1。原因很简单你无法直接根据nums[mid]和nums[left]的大小关系判断目标在左边还是右边因为数组在某个位置断成了两截你首先得搞清楚“当前 mid 落在哪一段”。这个题目经常和另外两兄弟一起出现在面试里一个是“搜索旋转排序数组”也就是本文要讲的另一个是“寻找旋转排序数组中的最小值”再往后还有带重复元素版本对应 LeetCode 81 题。面试官往往先让你写无重复版然后追问“如果有重复元素怎么办”考察你对时间复杂度的敏感度。这一整套连环问下来能比较真实地反映一个人对二分边界的理解深度所以它成为高频题是有道理的。另外从工程角度看二分思想在有序数据检索、数据库索引、甚至各种二分答案的算法中都反复出现。把这道题吃透相当于掌握了一种“在局部有序的数据中做决策”的思考方式这在排查线上问题时非常实用。比如你手头有一个日志文件时间戳大体有序但中间有断层你想快速定位某条记录思路和这个题目是相通的。1.3 暴力解与二分解的分水岭先看暴力解代码非常简单def search_brute(nums, target): for i, num in enumerate(nums): if num target: return i return -1这个解法的复杂度是 O(n)对于大多数实际场景其实够用尤其是在数组规模不大的时候。但算法题不会让你这么轻松面试官会追问一句“能不能快一点”这时候就要考虑二分。二分解的核心出发点只有一个每次把搜索区间砍掉一半。问题是平移数组不像普通有序数组那样“中间值一出来方向立刻明确”你必须多做一步——判断哪一半是有序的然后再决定目标值可能在哪个范围。这个判断不需要特别复杂的数学推导只需要抓住一个事实在任意一次二分中mid会把当前区间切成左右两半因为整个数组只有一处断层所以左右两半中至少有一半是严格有序的。你只需要找出那个有序的半区然后判断目标是否落在里面如果落在里面就继续在这个半区里搜如果不在就去另一半搜。一个生活化的类比是你有一本字典被人从中间撕开然后把前半本装订到了后面。现在你想查一个词翻开中间位置发现当前这一页属于“后半本”还是“前半本”你能立刻判断出来——因为字典内容是按字母顺序的如果这页是大写字母 M那说明你翻到的位置属于断裂后的“后半区”而你查的词如果在 M 之前就一定在另一个分区里。这里的“是否能立刻判断”对应到代码里就是“哪半段是有序的”这个条件。2. 核心思路拆解如何在“半有序”中玩转二分2.1 观察结构左右两段都是递增先再强调一遍平移数组的结构特点。以[6, 7, 1, 2, 3, 4, 5]为例它的原始递增数组是[1, 2, 3, 4, 5, 6, 7]从 5 和 6 之间被切断后平移得到。你可以看到左段[6, 7]严格递增右段[1, 2, 3, 4, 5]严格递增左段的最小值 6大于右段的最大值 5。这个“左段最小值大于右段最大值”非常关键。它意味着当你把数组对半切开时如果mid落在了左段那么从left到mid这一段必然是有序的如果mid落在了右段那么从mid到right这一段必然是有序的。你不需要知道旋转点具体在哪只需要根据nums[mid]和nums[left]或者nums[right]的大小关系判断当前这一刀切在了哪一段。具体判断规则可以写成如果nums[mid] nums[left]说明mid落在左段注意这里要包含等号后面会细说否则说明mid落在右段。为什么这个规则成立因为左段的所有元素都大于右段的所有元素所以当nums[mid]大于等于nums[left]时它不可能来自右段只可能来自左段反过来如果nums[mid]小于nums[left]由于整个左段都大于右段而left位置又一定在左段那么mid就只能来自右段。有了这个判断之后下一步就顺理成章了如果mid落在左段且left到mid这一段是有序的那么就检查target是否落在[nums[left], nums[mid])之间。如果是搜索区间收缩到左半否则搜索右半。如果mid落在右段且mid到right这一段是有序的那么就检查target是否落在(nums[mid], nums[right]]之间。如果是搜索区间收缩到右半否则搜索左半。这套逻辑的核心是把“全局无序”通过一次判断转换成“局部有序”然后在局部里套用常规二分。这也是整道题最值得记住的思路不要试图一次性定位目标而是先定位有序区间再决定去哪个区间找。2.2 判别有序区间的小技巧上面说的判断方式有一个等价写法很多题解也这么用直接判断nums[left] nums[mid]是否成立。如果成立说明左半有序如果不成立说明右半有序。这个说法更简洁编码时也更不容易绕晕。但这里有个细节容易被忽略等号。为什么要用而不是考虑一个长度为 2 的数组[3, 1]left 0right 1mid 0。此时nums[mid] 3nums[left] 3。如果写成nums[mid] nums[left]那么会错误地进入“左半有序”分支。实际上左半只有[3]一个元素它当然有序所以严格来说也不算错。但如果你把条件写反或者漏掉等号在一些边界场景下会进入错误分支比如[1, 3]mid 0nums[mid] nums[left]此时左半[1]确实有序判断应该为真。所以稳妥起见统一用或这类含等号的比较。另外一个小技巧是mid的求法建议写成mid left (right - left) / 2不要写成(left right) / 2。前者可以避免left right溢出虽然刷题时不一定遇到但这是好习惯面试时主动写出来也会加分。至于left right还是left right作为循环条件个人更推荐left right因为它天然对应“搜索区间为空”的退出条件配合返回 -1 比较方便。用left right时如果不小心处理最后一位容易死循环需要额外小心。2.3 时间复杂度与空间复杂度分析无重复版本的时间复杂度是 O(log n)计算方法和普通二分完全一样每轮循环把搜索区间缩小一半直到区间大小为 0。递推式是 T(n) T(n/2) O(1)根据主定理结果是 O(log n)。空间复杂度是 O(1)因为只用了几个指针变量。有重复版本要复杂一些。当数组里出现大量重复元素时可能出现一种尴尬情况nums[mid] nums[left] nums[right]此时你既不能判断左半有序也不能判断右半有序只能尝试把区间缩小一点点比如left或者right--。一次只能排除一个元素所以最坏情况下时间复杂度会退化到 O(n)。经典的退化例子是[1, 1, 1, 1, 1, 2, 1, 1, 1]目标值是 2旋转点在中部但二分的每一步都会因为三个位置的值相同而陷入“无法判断”只能一个位置一个位置地挪。所以面试里如果被问到有重复版本的时间复杂度一定要点出这个退化风险。这不是代码写得不好而是数据本身提供的信息量不足导致你无法稳定地对半分割。换句话说信息论上就没有办法保证 log n这是一个理论限制不是什么玄学。3. 可直接抄的代码实现与测试3.1 无重复元素版代码对应 LeetCode 33先放出最朴素、最稳的无重复版本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关键点逐条拆解nums[mid] target先判断这个放在最前面没有争议。nums[left] nums[mid]用来判断左半段是否有序注意等号。这里“左半段有序”指的是从left到mid这一段内部是递增的。由于平移数组两个分段各自递增只要mid和left在同一段里这一段就一定有序。如果左半段有序就检查target是否落在[nums[left], nums[mid])这个左闭右开的区间里。这里用了target nums[mid]而不是因为nums[mid]已经在前面比较过了。如果你用了可能会重复搜索自己逻辑上虽然无伤大雅但容易造成混乱。如果左半段无序那右半段必然有序因为整个数组只有一个断点这时候检查target是否落在(nums[mid], nums[right]]之间。这套代码的判断顺序先看“哪半有序”再看“目标在哪”符合前文讲的思路也最容易记住。3.2 带重复元素版代码对应 LeetCode 81带重复元素时核心变化是在判断有序之前先处理“三个位置都相等”的干扰情况。def search_with_duplicates(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] and 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和上一版相比几乎只多了if nums[left] nums[mid] and nums[mid] nums[right]这一个分支。它的作用是当三个位置的值都一样时无法判断哪边有序于是把两端各缩进一步放弃最左边和最右边两个元素。虽然这一步只能排除一个或两个候选位置但至少避免了错误判断。这里有个值得讨论的写法有的题解会写成if nums[left] nums[mid]: left 1也就是遇到相等时只动左边界。这种写法也可以但要注意它可能会在极少数场景下把正确结果跳过。最稳妥的还是“两端都向内收缩”因为左边界和右边界都可能是旋转点附近的有效元素。不过实际面试里写哪种一般都能过关键是讲清楚“为什么遇到相等时要退化成线性缩小”。还有一个容易忽略的点当nums[mid] ! target但nums[left] nums[mid] nums[right]时你收缩区间后并不会跳过target因为收缩的只是两端那些已经等于nums[mid]的元素。比如[1, 0, 1, 1, 1]目标值 0 在中间第一步mid指向 1三个位置都是 1执行left、right--之后搜索区间变成[0, 1]下标 1 的位置就是目标 0 所在的位置下一步就能找到。这个例子很适合拿去测试自己的代码。3.3 测试用例设计刷题时很多人喜欢写完直接提交报错再改。我更习惯先把典型用例列出来逐一在本地跑一遍这样可以避免反复提交。针对这道题推荐至少覆盖以下场景输入数组目标值期望输出说明[4,5,6,7,1,2,3]14目标在右半段[4,5,6,7,1,2,3]73目标在左半段末尾[1,2,3,4,5]32未平移的普通递增数组[2]20只有一个元素[2,1]11长度为 2旋转点紧挨边界[1,0,1,1,1]01有重复二分受影响[1,1,1,1,1]2-1全是重复元素找不到目标[5,1,3]32左半有序但右半也有序验证分支每一组用例都要确认返回值是索引还是布尔值因为 LeetCode 33 要求返回索引81 题只要求返回是否存在两者容易搞混。我自己最开始刷 81 题时就是因为习惯性返回mid而不是True导致整个逻辑改动较大。建议写之前先看清楚题目要求。4. 高频率踩坑与面试问法4.1 边界和循环条件为什么容易写错写二分最容易翻车的地方就是边界。拿这道题来说最常见的错误有两类一类是循环条件写错。while (left right)在退出时left会大于right这时搜索区间已经为空说明没找到返回 -1 即可。如果你写成while (left right)那么在区间只有一个元素时循环就结束了但此时这个元素可能还没有被检查过。所以要么改用left right要么在循环外补一次对nums[left]的检查。为了避免额外判断我建议统一用left right。另一类是判断target是不是在有序半区时边界取值错。比如左半段有序时正确判断是nums[left] target nums[mid]这里target可以等于nums[left]但不能等于nums[mid]。如果你写成 nums[mid]理论上多比较一次也无所谓因为后面还会通过nums[mid] target拦截但逻辑上容易让人犯迷糊。面试时边界一致性能体现出你思维的严谨度所以尽量用左闭右开与右开左闭的写法自洽即可。还有一个隐藏较深的坑mid的计算。如果left和right都是很大的整数left right可能溢出虽然刷题平台的数据通常不会触发但面试官会盯着看。写成left (right - left) // 2之后不仅安全还从侧面说明你有防御性编程的意识。4.2 有重复之后为什么会退化到线性复杂度这个问题几乎是必问的。回答思路是这样的当nums[left] nums[mid] nums[right]时你无法判断旋转点在哪一边。举个例子数组[1, 0, 1, 1, 1]中left 0mid 2right 4三个位置全是 1。你能确定目标 0 在左半还是右半吗不能。找最小值问题的退化也是同理当三个位置相等时你既不能排除左半也不能排除右半只能一点点缩小区间。所以最坏情况下比如数组在大量 1 中间夹着一个 2或者数组里全是同一个数二分的每次操作都只能移动一步整体复杂度变成 O(n)。这在面试里不算减分项只要你提前说出来反而显示你考虑到了边界退化。4.3 和“寻找旋转数组最小值”的关系很多面试官讲完搜索元素的题目后会顺手让你写“寻找旋转排序数组中的最小值”。这道题和搜索元素共享同一个结构基础但目标不同代码也简单得多def find_min(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]的关系如果nums[mid] nums[right]说明旋转点在右半段最小值在mid右边否则最小值在mid或mid左边。注意这里循环条件用的是left right因为目标是缩到同一个位置不需要额外返回 -1。这两道题放在一起练收益很高。因为它们都考察同样的能力面对局部有序的数据能否根据一两个比较操作确定一个方向性结论。搜索元素的题目是“判断目标是否在某一半”找最小值是“判断最小值在某一半”思路同源。建议大家先把找最小值的逻辑画清楚再去写搜索元素会发现后者的代码也没那么可怕。4.4 刷题与面试时的实战建议最后聊一点软技能。面试时遇到这道题我建议按这个顺序讲先承认这是一道二分查找变形题然后快速说明暴力解是 O(n)但题目考察的是能否利用数组局部有序的特点优化到 O(log n)。接着讲你的判断思路每次在mid处把数组切开观察左半和右半哪个是有序的再根据目标值与有序区间端点的关系决定搜索方向。讲到这一步面试官通常已经认可你的思路接下来就是代码细节。写代码时有一个小技巧先写无重复元素版本跑通之后再问面试官“如果有重复元素呢”然后增加一行if nums[left] nums[mid] nums[right]的分支。这样做既能展示你的代码是逐步迭代的又能体现你对复杂度退化的理解。不要一上来就写带重复的版本那样容易显得思路混乱。我在实际面试中见过不少候选人思路完全正确但代码里的小毛病很多。最常见的是while条件写错、等号漏掉、以及返回值搞混。这些细节恰恰是区分“背过题”和“真理解”的地方。你要是能把边界条件讲明白比如为什么nums[left] nums[mid]必须带等号为什么退化时left不会跳过目标面试官基本就会给你过了。我个人刷这道题的感受是二分的难点从来不是循环怎么写而是“如何通过局部信息做出全局判断”。平移递增数组恰好是训练这种判断力的第一道坎。如果你能把这个题吃透后面遇到“把有序数组从任意位置切断再搜索”的变体基本都能举一反三。至于带重复元素的版本多跑几组用例感受一下它从 log n 退化到 n 的过程以后再看到类似题型就不会慌了。