做 LeetCode 153 这道题的时候我一开始还挺不屑的一个找最小值的题直接遍历一遍不就完事了吗直到我看了题目要求——时间复杂度必须是 O(log n)才意识到这不是在考你会不会写循环而是在考你有没有真正理解二分查找的适用条件。更关键的是用 C 语言写这道题和用 Python、Java 写完全是两种体验没有现成的min()函数、没有容器封装、数组传进来就是一个指针加上一个长度所有边界都得自己抠。这篇文章就围绕“旋转排序数组的最小值”这个经典场景把我用 C 语言刷这道题的全过程、踩过的坑、总结出来的套路一次性讲清楚。1. 题目背后的本质旋转数组到底在考什么1.1 旋转排序数组到底是什么LeetCode 153 的题目描述很简洁一个原本按升序排列的数组在某个未知的旋转点被翻转了一下比如[0,1,2,4,5,6,7]在下标 3 处旋转后变成[4,5,6,7,0,1,2]现在要求找到这个数组中的最小值。很多人第一次看到“旋转”这个词会觉得抽象其实你可以把它想象成一副原本排好序的扑克牌从中间某个位置切一刀然后把后面半摞直接搬到前面来。搬完之后整副牌仍然是两段有序的前半段比如[4,5,6,7]内部递增后半段比如[0,1,2]内部也递增唯一的“断点”就出现在两段交界的地方。这个“断点”恰好就是最小值所在的位置。因为旋转点就是原来数组的最小元素被挪到了某个位置而它前面的所有元素都比它大后面的所有元素也都比它大在无重复元素的前提下。所以从本质上说这道题问的不是“最小值是多少”而是“断点在哪里”。1.2 为什么不能直接遍历我见过不少初学者包括当年的我第一反应都是写一个for循环扫描所有元素维护一个min变量。这在 C 语言里甚至只需要几行代码而且一定能过测试用例——前提是题目没要求复杂度。但 LeetCode 153 明确要求 O(log n)这里的逻辑是这样的如果数组长度是 100 万线性扫描需要 100 万次比较而二分查找只需要大约 20 次因为 log2(1000000) ≈ 20。C 语言虽然运行很快但复杂度决定了它在数据规模增长时的表现。更实际一点说面试中如果你上来就写线性遍历面试官大概率会追问一句“还能更快吗”然后这道题就变成了一个尴尬的开场。关键在于旋转排序数组虽然整体不是完全有序的但它局部有序而且我们确切知道最小值一定在某一段里。这种“信息足够、可以排除一半”的结构正是二分查找发挥作用的场景。1.3 用二分查找的切入点拿什么做比较基准二分查找的核心是“每次干掉一半”。在标准的有序数组二分里我们用target和中间元素nums[mid]比较在旋转数组里没有目标值只有“找最小值”这个目标那该拿什么作为基准呢我的答案是拿nums[high]当前区间的最后一个元素作为哨兵。这个思路是这么来的——随便选一个中间位置mid如果nums[mid] nums[high]说明中间位置落在了旋转点左侧那一段较大的一段那么最小值一定在mid的右边因为断点没有出现在左边反之如果nums[mid] nums[high]说明中间位置落在了旋转点右侧那一段较小的一段最小值一定在mid本身或者它的左边。这一步是整个算法的灵魂。理解了“为什么跟nums[high]比而不是跟nums[low]比”后面所有边界处理都会顺畅很多。2. C语言题解实现循环不变量与边界控制2.1 完整题解代码与复杂度分析直接上代码这是我最推荐的写法短小、清晰、不出错int findMin(int* nums, int numsSize) { int low 0; int high numsSize - 1; while (low high) { int mid low (high - low) / 2; if (nums[mid] nums[high]) { low mid 1; } else { high mid; } } return nums[low]; }时间复杂度 O(log n)空间复杂度 O(1)。这可能是 LeetCode 上最短的解法之一了但越短的代码对边界条件的要求越高。我们一行一行拆开讲。2.2 循环不变量每一轮都保证答案在 [low, high] 里写二分最容易犯的毛病是“循环条件凭感觉写边界调整靠试错”。正确的方式是先想清楚一个循环不变量每一轮循环开始时数组的最小值一定依然在闭区间[low, high]里。只要这个性质始终成立循环结束时low high答案自然就是nums[low]。验证一下上面的分支当nums[mid] nums[high]时说明mid位于旋转点左侧的大数段。因为nums[mid]都比当前区间最后一个元素还大而最小值一定小于等于nums[high]所以最小值不可能在mid或者在mid左边直接把low移到mid 1。当nums[mid] nums[high]时说明mid位于旋转点右侧的小数段最小值要么在mid要么在mid左边所以把high移到mid注意不是mid - 1。这里最微妙的地方就是high mid而不是high mid - 1。因为nums[mid]完全有可能就是最小值本身你把high跳到mid - 1就会把正确答案丢掉。我在本地测试时就踩过这个坑写成了high mid - 1结果在[3,4,5,1,2]这种用例上返回了 3 而不是 1原因就是第一次循环时mid 2nums[2] 55 nums[4] 2不成立走了左分支low 3第二次循环时mid 3nums[3] 1 nums[4] 2然后high mid - 1 2区间变成了[3,2]循环退出返回nums[3] 1。哎看起来碰巧对了但换个长度就崩了。所以记住当mid可能是答案时区间收缩不能用排除法而要保留mid。2.3 mid 的三种写法为什么必须防溢出C 语言里求两个整数的中间值最直观的写法是(low high) / 2。这在大多数情况下没问题但问题是low high可能溢出。在 C 语言标准里有符号整型溢出是未定义行为Undefined Behavior。虽然常见编译器比如 GCC在默认情况下会做回绕处理但标准不保证你不能赌。LeetCode 的数组长度虽然一般只有几千但当你把代码扩展到更通用的场景比如numsSize接近INT_MAX的一半时low high就可能超过int的上限。所以更稳妥的写法是int mid low (high - low) / 2;。先算差值再除以 2最后加上low这样每一步都在安全范围内。还有一种写法是int mid low ((high - low) 1);用右移代替除法。这里要特别提醒 C 语言初学者右移运算符的优先级比加法低所以必须加括号。如果不加括号写成low (high - low) 1实际解析成了(low high - low) 1也就是high 1逻辑就完全错了。这种错误在本地跑测试用例时很容易被掩盖因为某些输入可能碰巧得到相同结果但在另一些输入上就会翻车。我建议新手一律用low (high - low) / 2别去秀位运算的操作少个括号就少一个 bug。2.4 为什么用 nums[high] 而不是 nums[low]我见过很多题解写的是if (nums[mid] nums[low]) low mid 1; else high mid;这种写法可以工作但有一个隐藏陷阱当数组完全没有旋转时比如[1,2,3,4,5]最小值在最左边可这个逻辑依然在二分最后也能得到正确答案。问题在于它需要额外注意“等号”的处理以及分清楚“哪一半是递增的”逻辑上更绕。用nums[high]的好处是它对“未旋转”和“已旋转”两种情况一视同仁不需要特判。原因在于nums[high]始终是当前区间右端的元素无论数组怎么旋转最小值都不会超过它。而nums[low]在某些分支里可能已经是最小值了拿它做比较基准会引入歧义。举个具体的反例如果你用和nums[low]比较在数组[2,1]上就会出现问题low 0, high 1, mid 0, nums[mid] 2 nums[low] 2于是low mid 1 1返回nums[1] 1这没问题但在[1,2]上mid 0, nums[0] 1 nums[0] 1low 1返回 2直接错了。这说明这种写法必须对“等号”做特殊判断而用nums[high]就完全没这么多事。3. 用C语言刷这道题真正要留心的细节3.1 函数签名里的指针与长度是两回事很多刚开始用 C 语言刷题的人会对int findMin(int* nums, int numsSize)这个签名感到困惑为什么传入的是指针而不是数组为什么还要单独传一个长度因为在 C 语言中数组作为函数参数传递时会退化为指向首元素的指针。也就是说int* nums和int nums[]在函数参数中是等价的编译器不关心数组到底有多长它只给你一个首地址。numsSize是额外的约定告诉你这个数组有多少个元素完全靠调用方自觉。这个设计对刷题的影响是你一定不要写出越界访问。在 Python 里nums[-1]能拿到最后一个元素在 C 语言里nums[-1]是未定义行为它可能返回一个垃圾值也可能直接让程序崩溃。写二分查找时每次访问nums[mid]之前都想一下mid是否真的落在[0, numsSize - 1]范围内尤其是当low和high调整出错时mid可能瞬间变成负数。另外既然nums是指针那么nums[mid]本质上就是*(nums mid)这是指针运算的语法糖。理解这一点对排查问题非常有帮助。比如我调试时就遇到过一种情况循环写错了low跑到了high 1然后mid也跟着越界读出来的nums[mid]是内存里完全不相干的数值程序却没有立刻崩溃——这就是 C 语言最有迷惑性的地方越界不一定报错但会给出错误结果。3.2 C语言常见错误自查从这道题蔓延开去这道题代码很短但恰恰因为短初学者容易在几个不起眼的地方翻车。我结合自己刷题的经验列几个高频问题循环条件写成low high。如果你用的是low high那么循环结束后low high直接返回nums[low]如果写成low high就必须在循环内部处理low和high交叉的情况否则可能陷入死循环或者漏掉答案。两种写法都能做对但要保持一致别混着来。忘记else分支。有些新手只写了if (nums[mid] nums[high]) { low mid 1; }然后以为剩下情况会自动处理结果编译能过运行却死循环。C 语言不会因为你“没写 else”就自动执行别的逻辑没有分支时while条件不变自然就死循环了。返回了mid而不是nums[low]。在low high的循环条件下循环退出时low high返回谁都行但如果你在中途用break跳出循环mid可能不是最终答案这时候返回mid就会出错。所以我习惯统一返回nums[low]让逻辑简单一点。缓冲区的问题。如果为了调试在循环里加printf记得加\n或调用fflush(stdout)否则输出可能因为缓冲区没有刷新而看不到。这和fgets、printf的缓冲机制是一类问题平时写小工具不觉得刷题时想在代码里打日志定位问题就会被这个细节坑到。3.3 从 C 语言的角度看这段代码的“内存成本”有人可能会问这个二分查找在 C 语言里只用了三个int变量是不是真的不占内存是的low、high、mid都是局部变量分配在栈上。nums是传进来的指针它指向的内存在堆上或者在全局区由调用方管理。这里顺带说一个 C 语言初学者常有的疑问函数调用时局部变量到底存放在哪答案是栈Stack。栈空间在大多数嵌入式环境或桌面环境下是有限的但一个深度为log2(n)、只占三个int的二分查找栈开销可以忽略不计。如果你非要用递归去写这个二分查找理论上也不会爆栈但递归版本需要额外的函数调用帧堆栈的使用量更大。更重要的是递归版本在边界处理上更难把握容易在返回条件上出问题。我的原则是能用迭代写的二分就不要用递归。这不仅仅是效率问题更是可读性和可调试性的问题。在看代码的high/low mid 1逻辑时可以展开讲讲“为什么 mid 永远不等于 high”。在low high的条件下mid low (high - low) / 2因为high - low 1所以(high - low) / 2最多是(high - low - 1)除以 2 向下取整恒小于high - low因此mid high。这个结论保证了high mid时区间至少缩小一个元素循环必然终止。这也是 C 语言里不需要担心死循环的数学依据。4. 变式与扩展一道题带出一类二分题4.1 含重复元素的版本LeetCode 154LeetCode 153 的升级版是 154区别在于数组中允许重复元素。原题里我们依赖“nums[mid] nums[high]时一定走左分支”但有了重复元素后nums[mid] nums[high]的情况就变复杂了——你无法判断mid到底在大数段还是小数段。解决办法是遇到相等的情况把high向左移动一位。因为即使nums[high]就是最小值由于nums[mid] nums[high]mid位置的值也是同样的最小值所以把high去掉不会弄丢最小值。这个思路严谨而且代码改动极小int findMin(int* nums, int numsSize) { int low 0, high numsSize - 1; while (low high) { int mid low (high - low) / 2; if (nums[mid] nums[high]) { low mid 1; } else if (nums[mid] nums[high]) { high mid; } else { high--; } } return nums[low]; }这里的high--是退化为线性扫描的最坏情况比如所有元素都相同时每次只能去掉一个元素时间复杂度变成 O(n)。但这是可接受的因为当重复元素大量存在时信息量本身就不足。4.2 求旋转点下标对二分返回位置的思考LeetCode 153 只要最小值但如果面试问你“返回最小值的下标”怎么办答案是把return nums[low]改成return low就行。因为我们的循环不变量保证了退出时low就是最小值的位置。这一点很有意思二分查找到最后low不仅是值的位置而且它本身就蕴含了“数组旋转了几次”的信息。旋转次数等于最小值的下标如果旋转次数小于数组长度。所以这道题的解法天然能回答旋转次数的问题不少笔试会在这上面做文章要求你额外输出旋转次数。4.3 在旋转数组中搜索目标值LeetCode 33 的启发做完了 153我建议紧接着做一下 LeetCode 33搜索旋转排序数组。这道题是“找值”而不是“找最小值”但核心思想一脉相承先判断mid落在哪一段有序区间然后根据target与两端的大小关系决定往哪边收缩。我当初刷完 153 再去做 33 时感觉难度直接从中等降到了简单因为我已经习惯了“拿哪一段的什么位置做比较基准”的思考方式。如果你现在做 153 有点吃力也别急着写下一题先把“为什么用nums[high]”想透再做 33 会轻松不少。在 33 里判断条件通常是先看nums[low] nums[mid]判断左半段是否有序然后再根据target是否落在[nums[low], nums[mid]]范围内决定。它比 153 多一层 if-else但骨架是一样的每次排除一半区间永远包含目标。5. 实测踩坑记录与调试技巧5.1 我调试这道题时遇到的两个典型错误第一个错误是把循环条件写成while (low high)没错但我在分支里写成了low mid。表面上看这么做和high mid是对称的但在某些情况下会死循环。比如在[3,4,5,1,2]这个输入上第一轮low0, high4, mid2nums[2]5nums[4]25 2于是low mid 2。第二轮low2, high4, mid3nums[3]1 2high3。第三轮low2, high3, mid2nums[2]5 nums[3]1lowmid2这时候low还是 2high还是 3直接死循环。原因在于当mid可能不是答案时你不能把low直接移动到这个可能不是答案的位置上。正确做法是low mid 1因为nums[mid] nums[high]已经排除了mid自己。第二个错误是使用int mid (low high) / 2;。这道题的数组长度在 LeetCode 上不会触发溢出但这种写法会给你一种“反正没事”的错觉。直到我在另一个项目里用它处理一个长度接近 20 亿的数组是的这种需求确实存在程序出现了诡异的行为最后定位到是整型溢出。从那以后我凡写二分一律low (high - low) / 2没有任何例外。5.2 本地验证用的测试用例清单不管是在 LeetCode 网页上直接提交还是本地用 GCC 编译测试我都建议准备这样一组用例输入数组期望结果备注[1]1只有一个元素最小边界[1,2]1未旋转偶数长度[2,1]1旋转 1 次也是峰值情况[3,4,5,1,2]1标准示例[4,5,6,7,0,1,2]0题目原始示例[5,1,2,3,4]1最小值在第二位[2,2,2,0,1]0含重复元素用于 154[1,1,1]1全等元素用于 154本地测试时我习惯写一个main函数把这些用例做成一个二维数组循环调用findMin用assert验证结果。因为 LeetCode 的测试环境不会告诉你具体败在哪个用例上而本地的 assert 可以精确到是哪一行。5.3 编译选项与调试建议如果你在本地用 GCC 或 Clang 编译这道题的代码我强烈建议打开警告选项gcc -Wall -Wextra -stdc99 -g find_min.c -o find_min-Wall和-Wextra能帮你捕捉“未初始化变量”“比较结果恒为真”等低级问题-g生成调试信息方便配合 GDB 查看low、high、mid的变化。调试二分查找还有一个很有效的笨办法在循环里打印出每一轮的low、high、mid、nums[mid]、nums[high]。刚打印出来可能觉得信息太多但你会很快看出规律——哪个变量没有按预期缩小哪个分支判断写反了一目了然。打印的时候记得带换行不然缓冲区会让你怀疑人生。写在最后的一个小技巧这道题我前前后后写了不下五遍每一遍都会对“二分查找的边界条件”有新的理解。如果只让我分享一个经验那就是写二分查找之前先在注释里写下循环不变量——你凭什么说答案一定在[low, high]里只要这句话写清楚了代码几乎不会出逻辑错误。C 语言的威力在于它能让你精确控制每一个字节、每一次内存访问但也正因如此它不会替你兜底。nums[mid]访问的下标、low high的溢出、high mid之后的死循环每一个细节都是 C 语言给程序员出的考题。把这套边界思维练扎实了你收获的绝不只是这一道题的答案而是以后写任何区间类算法时都不再心虚的底气。
