“旋转数组的最小数字”这道题我面试人的时候几乎必问。不夸张地说十个候选人里至少五个第一反应是遍历一遍找最小值剩下的一半里能想到用二分法但能把重复元素和边界条件一次性写对的人少之又少。这道题好在哪它考的本质只有一句话你会不会把“有序”这个已知条件用到极致以及在有序被破坏之后如何通过比较中间值和边界值逐步缩小搜索范围。剑指Offer原书上标的是“简单”面试里的区分度却极高这道题非常适合准备算法面试的求职者、想系统梳理二分法应用的开发者还有平时写业务代码、希望锻炼“减治”思维的工程师。1. 先理解旋转数组它到底破坏了什么有序性1.1 从一个最朴素的问题讲起所谓旋转数组就是把一个升序数组的若干个元素搬到数组末尾。举个最直接的例子原数组[1,2,3,4,5]如果把前两个元素[1,2]搬到末尾就得到了[3,4,5,1,2]这就是一个旋转数组。注意“若干个”完全可以是 0也就是说[1,2,3,4,5]本身也是旋转数组的特例只是旋转了 0 个元素而已。很多人第一次看到这道题会想那直接找相邻两个数里第一个突然变小的位置不就行了吗比如[3,4,5,1,2]中 5 后面的 1 就是“悬崖点”答案就是 1。这个朴素的思路没有错但它是线性的最坏情况要把数组从头到尾扫一遍复杂度 O(n)。面试官出这道题真正的意图是让你意识到这依然是一道可以二分查找的题前提是你得先想清楚“最小值在哪儿”这件事能不能通过一个中间位置来判断。理解旋转数组的关键在于把它看成两段升序子数组拼接在一起前半段整体大于等于后半段整体。所谓“旋转点”就是前一段的最后一个元素和后一段的第一个元素之间的“断层”而那个“后一段的第一个元素”恰好就是整个数组的最小值。只要你能在二分过程中不断逼近这个“断层”答案自然而然就出来了。1.2 关键性质找到“悬崖”就找到了答案假设数组没有重复元素并且确实发生过旋转那么数组一定满足这样一条性质左半段的所有元素都大于右半段的所有元素。例如[3,4,5,1,2]中[3,4,5]整体大于[1,2]。这个性质有什么用当你在区间[low, high]中取中间下标mid只要比较nums[mid]和nums[high]就能判断出mid落在左半段还是右半段如果nums[mid] nums[high]说明mid还在左半段而最小值一定在mid右边如果nums[mid] nums[high]说明mid已经在右半段最小值在mid左边或者就是nums[mid]自己。我会强烈建议你始终拿mid和右边界high比较而不是和左边界low比较。原因后面会专门展开。现在你只需要记住一个结论旋转数组的“悬崖”是能通过中间值和右边界的大小关系定位出来的这就是二分法在这个问题上能成立的根本前提。1.3 暴力解法可以做但面试不能停在 O(n)写一个暴力遍历版本很简单def find_min_brute(nums): return min(nums)或者正统地扫描一遍def find_min_brute(nums): res nums[0] for x in nums: if x res: res x return res复杂度 O(n)空间 O(1)。如果你的目标是“把题目做出来”这个解法没有错。但面试要的不是“能跑”而是“在数据规模变大时依然高效”。数组如果有 10 万个元素O(n) 还是能扛住的但如果面试官把场景换成“每次查询都要做一次做 10 万次”O(n) 就不合适了。我在面试中通常这样引导候选人“你发现这个数组有一部分是有序的吗有序的东西能不能用更快的办法去搜索”只要候选人说出“二分法”三个字这道题就已经通过了一半。剩下的全在处理细节。2. 二分法解题核心思路与无重复元素版本2.1 为什么这题能用二分法二分法的本质不是“数组必须有序”而是“通过一次比较能够排除掉一半的搜索空间”。普通二分之所以能用是因为数组有序时中间元素和目标值的大小关系能直接告诉你目标在左还是在右。旋转数组虽然整体不是有序的但它保留了“两段各自有序”的结构而且两段之间有明确的大小边界。正因为存在“左段所有元素都大于右段所有元素”这条性质我们同样能通过一次比较判断出最小值在哪一侧。这比随机猜要靠谱得多复杂度也可以降到 O(log n)。打个比方普通二分像在一本按拼音排序的字典里找字旋转数组二分则像在一本被从中间撕开再前后调换的字典里找字——虽然字典整体乱了但每一部分的内部顺序还在你依然能根据页码大小关系快速缩小寻找范围。2.2 循环不变量区间设计决定代码质量写二分最怕的是什么是写着写着忘记自己维护的是什么。我自己的习惯是先明确一个循环不变量在每一轮循环开始前最小值一定在区间[low, high]内。只要这个不变量始终成立循环结束时low就等于high答案就是nums[low]。基于这个不变量无重复元素版本的核心逻辑如下当nums[mid] nums[high]说明mid位于左段最小值在mid的右侧所以low mid 1当nums[mid] nums[high]说明mid位于右段最小值在mid的左侧或就是mid所以high mid不断缩小区间直到low high。注意两个细节。第一nums[mid] nums[high]时不能写low mid因为已经确定nums[mid]比nums[high]大它不可能是最小值必须排除掉。第二nums[mid] nums[high]时不能写high mid - 1因为最小值可能就是nums[mid]自己比如数组[4,5,1,2,3]里mid指向 1 时如果把 high 移到 mid-1就永远找不到 1 了。2.3 无重复元素代码实现与逐行注释def find_min(nums): low, high 0, len(nums) - 1 while low high: mid (low high) // 2 # mid 在左段最小值一定在 mid 右边 if nums[mid] nums[high]: low mid 1 # mid 在右段最小值在 mid 左边也可能就是 mid else: high mid return nums[low]这段代码很简单但你要能解释清楚为什么while low high而不是。因为我们的循环不变量是“区间内至少有一个候选值”当low high时区间里只剩一个元素它必然是答案继续循环没有意义。而mid (low high) // 2是向下取整这保证了当区间长度为 2 时mid会落在左侧元素上配合low mid 1或high mid的更新方式区间长度一定严格递减不会死循环。你可以手动跑一遍[3,4,5,1,2]初始low0, high4, mid2nums[2]5 nums[4]2于是low3此时区间[3,4]mid3nums[3]1 nums[4]2于是high3lowhigh3返回nums[3]1。每一步都稳扎稳打没有任何悬念。3. 含重复元素怎么办三种情况逐一拆解3.1 重复元素是如何“污染”二分判断的如果题目允许重复元素事情就从“简单”变成“中等”了。力扣上对应的是第 154 题剑指Offer原题也默认要考虑重复元素。重复元素带来的问题很直接当nums[mid] nums[high]时你无法判断mid到底是在左段还是右段。举个经典反例。数组[1,0,1,1,1]最小值是 0看起来像是[0,1,1,1,1]旋转了 1 位得到的。取mid2nums[2]1nums[high]1二者相等。此时最小值在 mid 的左侧。再看另一个数组[1,1,0,1,1]同样取mid2nums[2]0nums[high]1二者相等但最小值就是nums[mid]本身。同样都是nums[mid] nums[high]答案可能在中点的左边也可能就在中点。这种情况下常规的二分判断失效了必须引入额外的处理。3.2 high-- 的边界性和复杂度退化标准的解决办法是当nums[mid] nums[high]时执行high - 1把右边界向左移动一位。这个操作很好理解既然中间值和右边界值相等那么去掉右边界的那个元素不会影响最小值的搜索结果因为就算最小值就是那个值相同值在数组里还有其他位置可以兜底。但代价也很明显最坏情况下比如数组[1,1,1,1,1]这种全部相等的输入每一轮nums[mid]都等于nums[high]每次都只能把区间缩小 1整体复杂度从 O(log n) 退化成 O(n)。这是必须向面试官说明白的事情——你可以得到正确答案但要清楚最坏情况是什么并且知道为什么。我在实际编码时会把这种情况单独列出来宁可多写一个分支也不要把high - 1和low mid 1混在一个分支里。逻辑越清晰边界越不容易出错。3.3 完整版代码与测试用例表def find_min(nums): if not nums: raise ValueError(数组不能为空) low, high 0, len(nums) - 1 while low high: mid (low high) // 2 if nums[mid] nums[high]: low mid 1 elif nums[mid] nums[high]: high mid else: # nums[mid] nums[high]无法判断方向只能缩小右边界 high - 1 return nums[low]写完后一定要用下面这组测试用例验证输入数组期望结果说明[3,4,5,1,2]1常规旋转无重复元素[1,2,3,4,5]1旋转 0 位最小值在首位[2,2,2,0,1]0重复元素最小值在右段[1,0,1,1,1]0重复元素最小值在左段经典反例[1,1,1,1,1]1全部相等最坏情况验证 high-- 正确性[1]1只有一个元素我每次写完后至少会跑一遍这张表里的用例尤其是第二行和第四行它们分别对应“未旋转”和“最小值被重复元素夹在中间”这两个最容易翻车的场景。4. 新手踩坑实录四个高频问题与排查思路4.1 拿 mid 和 low 比较的典型错误很多人在没想清楚的情况下会下意识写出if nums[mid] nums[low]这样的判断。这个写法在有些用例里能碰巧得到正确答案但它并不总是成立。例如数组[1,2,3,4,5]nums[mid]3nums[low]13 1按照“mid 在左段就去右边找”的逻辑会把搜索区间移到右侧但最小值明明在最左边直接翻车。为什么会这样因为和high比较时我们能利用“右段最大值小于左段最小值”的性质而左边界low不一定位于左段起点它本身就在随着搜索过程变化。用low做参考会丢失“段与段之间的大小关系”这一关键信息。所以在无重复时标准答案几乎都是和high比有重复时再把相等分支单独拎出来处理。4.2 死循环是怎么来的手推变量变化二分法写错最常见的结果就是死循环。以错误的更新方式为例假设你在nums[mid] nums[high]时写了high mid - 1我们手动跑一下[3,4,5,1,2]初始low0, high4, mid2nums[2]5 nums[4]2走lowmid13没问题第二轮low3, high4, mid3nums[3]1 nums[4]2错误地执行highmid-12。此时low3high2区间直接为空循环结束返回nums[3]1。这个例子碰巧答案正确但换了[4,5,1,2,3]就会出问题因为第二轮 mid 指向 2 时如果把 high 挪到 mid-1就把真正的最小值 1 排除在区间之外了。再看另一个错误在nums[mid] nums[high]时写low mid而不是low mid 1。比如数组[2,1]初始low0, high1, mid0nums[0]2 nums[1]1如果lowmid0区间一直是[0,1]mid永远算出来是 0死循环。手推变量变化的目的是让你看清每个分支更新后区间是否严格缩小。要记住只要二分代码出现了某个分支没有让区间长度变小就一定有问题。4.3 空数组、单元素等输入异常的工程处理工程上写代码不能假设输入永远合法所以我建议函数入口先判空抛出异常或返回哨兵值都可以但要在注释或文档里写明约定。面试时可以先问面试官“数组一定非空吗”这不是套近乎而是体现你的工程意识。单元素数组[1]会直接跳过while循环返回nums[0]逻辑天然正确。这种情况不用特殊处理但测试用例里要覆盖到。两元素数组[2,1]是另一个特别容易暴露问题的用例因为mid会取到 0整个过程只比较一次就结束务必手动验证。4.4 五组必须过的验证样例我总结了一套自查清单无论题目怎么包装写完代码先跑这五组旋转 0 位的升序数组如[1,2,3,4,5]旋转 n-1 位的数组如[2,3,4,5,1]含重复元素且最小值在左段的数组如[1,0,1,1,1]含重复元素且最小值在右段的数组如[2,2,2,0,1]全部元素相等的数组如[1,1,1,1,1]。这五组样例基本能覆盖 90% 的边界问题。如果面试时时间不够我也会至少跑第 1、3、5 组它们分别对应“常规情况”“重复元素干扰判断”“最坏复杂度退化”三大考点。5. 思路迁移二分法的两个加分扩展5.1 面试官真正在考察的三个点在我面试别人的经验里这题真正想考察的不是你能不能背出模板而是三件事第一你有没有“减治”思维知道通过一次比较排除掉一半数据第二你会不会主动讨论边界条件比如“数组元素是否唯一”“数组是否非空”第三你能不能清楚说出自己的算法在最好、最坏情况下的复杂度尤其是重复元素导致的退化。答题节奏我建议这样先给出暴力解再自然过渡到二分写上两行时停下来问“如果所有元素都相同呢”然后补上high--分支。这个过程会让面试官觉得你不是在背题而是真的在思考。5.2 同套路变体搜索旋转数组与寻找峰值这类题有一个家族。力扣第 33 题“搜索旋转排序数组”要求查找目标值思路是判断 mid 落在左段还是右段后再看 target 是否在对应区间内第 81 题是它的重复元素版。第 162 题“寻找峰值”看上去完全不同但核心还是“根据中间值和相邻元素的大小关系决定往哪边收缩区间”本质上和本题的决策逻辑同源。刷完旋转数组最小数字之后建议立刻刷 33 和 162。你会发现它们的共同套路是先找到一个能通过比较确定的区间性质再决定舍弃哪一半。只要你把这种“二分决策”的思维练熟了家族的题都是一通百通。5.3 二分法求平方根从数组到单调区间最后说一个和数组无关的二分应用——求平方根。题目要求是给定非负整数x求sqrt(x)的整数部分或者精确到小数点后若干位。此时二分法依然适用因为答案落在[0, x]这个单调区间内每次比较mid * mid和x的大小即可缩小范围。def my_sqrt(x): if x 0: raise ValueError(输入不能为负数) if x 0: return 0 low, high 1, x while low high: mid (low high) // 2 if mid * mid x: low mid 1 else: high mid - 1 return high为什么要提这道题因为很多人学二分只停留在数组二分遇到“答案是一个数”的题目就懵了。其实二分的底层要求只有一个搜索空间是可单调收缩的。数组有序是满足这个要求的一种情况平方根问题也是。能把这个道理想通你就真正吃透了二分法。最后再分享一个我面试时的小习惯写二分法之前先在脑子或草稿纸上明确一句话——“我维护的区间是什么每一轮循环后最小值一定还在这个区间里”。想清楚这句话再动笔代码基本不会跑偏。这道题我前前后后讲过几十遍每一次都能在候选人代码里发现新的边界问题但所有问题都绕不开“区间收缩是否严格”和“相等时如何决策”这两个根因。希望这篇梳理能帮你少走弯路把旋转数组最小数字这题的思路真正内化成自己的东西。
