搜索旋转排序数组的C语言实现：二分查找变形与边界细节

第一次在 LeetCode 上刷到第 33 题“搜索旋转排序数组”时我的第一反应是直接线性扫描反正数组长度不大一个 for 循环跑过去一样能过。直到仔细看了题目要求时间复杂度必须控制在 O(log n)才意识到这道题真正想考的就是二分查找的经典变形。用 C 语言刷这题又比用其他语言多了一层“折磨”标准库里没有现成的二分函数所有边界、下标、等号都得自己一点点抠但恰恰是这个过程把二分查找的原理彻底吃透了。这篇文章就把我完整的解题思路、C 语言实现细节和踩过的坑整理出来不管是刚开始刷 LeetCode 的 C 语言初学者还是想理顺二分查找变形思路的读者应该都能从里面拿走点东西。1. 旋转数组的两个不变量为什么“半有序”也能二分1.1 旋转的本质一列有序数据被“拦腰折断”再拼接先说清楚什么是旋转排序数组。给定一个升序排列的数组比如[0, 1, 2, 4, 5, 6, 7]在某个未知的下标 k 处切断把前半段整体移动到后半段后面得到的结果就是旋转排序数组。比如在 k 3 处切断把[0,1,2]挪到末尾就得到[4,5,6,7,0,1,2]。这里有个很容易被忽视的特点旋转之后的数组并不是完全无序而是由两段各自升序的子数组拼接而成。第一段是[4,5,6,7]第二段是[0,1,2]段与段之间的唯一“断层”出现在7和0相邻处也就是nums[i] nums[i1]的位置这个位置就是旋转点。用一个生活化的例子理解想象一列火车车厢每节车厢按编号顺序排列。有人在中途把整列火车拆开把前面几节车厢整体换到了队尾。车厢内部相对顺序没变变了的只是整列车的排列起点。所以旋转数组的本质是“两个连续递增段”的组合而不是单纯的无序数组。1.2 不变量一任意切一刀必有一半完全有序这是整个二分思路能成立的基石。假设当前搜索区间是[left, right]取中点mid观察nums[left]和nums[mid]的大小关系如果nums[left] nums[mid]说明从left到mid这一段没有发生断层也就是说左半段[left, mid]是严格升序的。反过来如果nums[left] nums[mid]说明旋转点藏在左半段里那么右半段[mid, right]一定是完整的升序段。道理并不复杂整个数组只有一个下降沿而mid只能落在两个递增段中的某一段。无论mid落在哪里它所在的那一段整体都是有序的另一段才包含旋转点。这个“每次必然存在一个有序的一半”的性质正是二分查找能用上的关键。标准二分要求整个数组有序本质上是为了保证每次比较之后能确定性地排除一半旋转数组虽然整体不是单调的但任意一次分割后我们总能找到那一半有序区间进而判断目标值是否属于它从而排除另一半。所以二分查找并不要求数组处处有序它真正需要的是“通过一次比较能确定目标值不在其中一半”。1.3 不变量二整个数组只有一个下降沿旋转数组还有一个重要特征最多只有一个位置满足nums[i] nums[i1]。在没有任何旋转的情况下下降沿不存在整个数组就是普通升序数组此时直接跑标准二分即可。在发生旋转后这个唯一的下降沿就是旋转点本身。这解释了为什么很多题解里会花力气去“找旋转点”——因为只要定位到唯一的下降沿整个数组就相当于被拆成了两个标准升序区间之后的事情就简单了。不过找旋转点并不是唯一思路后面会详细对比两条路线。先把这两个不变量记在心里后面所有代码都不会超出这个逻辑框架。2. 先找旋转点还是边查边判断两条路线到底选哪条2.1 路线A先定位旋转点再做两次标准二分这是思维上最直接的一条路先用二分找到最小值所在下标也就是旋转点pivot。因为最小值一定在下降沿之后的位置上。找到pivot后数组被分成[0, pivot-1]和[pivot, numsSize-1]两段每一段内部都是严格升序的直接对这两段分别做标准二分查找即可。找旋转点最小值下标的核心代码int findMinIndex(int* nums, int numsSize) { int left 0, right numsSize - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; } else { right mid; } } return left; }这里有一个很容易踩的细节比较对象必须是nums[mid]和nums[right]而不是和nums[left]比。用right比较的好处是当整个数组没有旋转、完全升序时nums[mid] nums[right]永远为假代码会不断把right向左收缩最终收敛到下标 0也就是最小值位置完全正确。如果用nums[mid]和nums[left]比较无旋转时会一直把左边界往右推最后找到的是最大值而不是最小值直接就错了。找到pivot之后写一个标准的二分查找函数然后对两段分别调用int binarySearch(int* nums, int left, int right, int target) { while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } int search(int* nums, int numsSize, int target) { int pivot findMinIndex(nums, numsSize); int res binarySearch(nums, 0, pivot - 1, target); if (res ! -1) { return res; } return binarySearch(nums, pivot, numsSize - 1, target); }注意pivot可能为 0此时binarySearch(nums, 0, -1, target)的区间是空的循环条件left right直接不成立返回 -1没有任何问题。C 语言里right是 -1 不会越界访问因为进入循环体才会访问数组而这种情况压根进不去。2.2 路线B在二分循环里直接判断目标落在哪一段路线B不单独找旋转点而是把“判断目标值落在哪一段”的逻辑直接写进二分循环里。每次取中点后先判断左半段是否有序再判断 target 是否位于有序段内。完整代码如下int search(int* nums, int numsSize, int target) { if (numsSize 0) { return -1; } int left 0, right numsSize - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } if (nums[left] nums[mid]) { // 左半段 [left, mid] 有序 if (target nums[left] target nums[mid]) { right mid - 1; } else { left mid 1; } } else { // 右半段 [mid, right] 有序 if (target nums[mid] target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }这段代码的核心逻辑是先确定哪一半完全有序再判断 target 是否落在这个有序段内部。如果落在内部就继续在这段里二分如果不在就去包含旋转点的那一半里继续找。注意两个判断里的等号位置判断target nums[left]时带等号因为 target 可能等于左端点判断target nums[mid]时不带等号因为nums[mid]已经在上一步比较过不等于 target 了。右半段同理target nums[mid]不带等号target nums[right]带等号。2.3 两条路线的对比与个人选择维度路线A先找旋转点路线B边查边判断代码量较长需要三个函数短一个函数完成理解成本思路直观容易上车需要想清楚区间归属主要风险findMin 的比较对象容易写错等号位置容易写错扩展性方便扩展到旋转点相关题目方便扩展到有重复元素版本我的建议是理解阶段先用路线A把旋转数组的“两段升序”结构彻底想明白上机或面试时写路线B函数短、变量少不容易在细节上翻车。两条路线时间复杂度完全一样都是 O(log n)空间 O(1)不存在性能差异纯粹是代码风格和思维习惯的取舍。3. C语言实现里的三处关键细节中点、等号与循环不变性3.1 中点计算为什么必须写成 left (right - left) / 2这是二分查找里最经典的一个细节。很多初学者习惯写成mid (left right) / 2在绝大多数测试用例下不会出问题但理论上存在整数溢出风险。C 语言的 int 是固定位数有符号整数当left和right都接近INT_MAX时left right会溢出结果变成负数mid直接算错数组访问就越界了。虽然 LeetCode 的数组长度通常不会大到触发溢出但在工程习惯上left (right - left) / 2是更稳妥的写法先求区间长度再取一半结果永远落在[left, right]内无论 left 和 right 是多少都不会溢出。这不是这道题独有而是所有二分查找的统一习惯从竞赛到生产代码都推荐这么写。既然用 C 语言刷题一开始就养成这样的习惯后面写任何二分都不会踩坑。3.2 等号归属nums[left] nums[mid] 里的等号救了多少次判断“左半段是否有序”时正确写法是nums[left] nums[mid]而不是nums[left] nums[mid]。这个等号极其关键专门用来处理区间长度只有 2 的场景。举个例子数组为[3, 1]target 为 1。第一次循环left 0, right 1, mid 0此时nums[left] nums[mid] 3。如果判断条件写成3 3为假代码会错误地认为右半段有序从而走进 else 分支但右半段[1]虽然确实有序判断target nums[mid] target nums[right]时1 3为假于是执行right mid - 1 -1循环结束返回 -1明明数组中存在 1 却找不到这就是典型的等号 bug。写成后3 3为真说明左半段只有一个元素的[3]有序虽然 target1 不在这个区间内代码会执行left mid 1 1继续搜索右半段这时nums[1] 1命中目标。为什么left mid时左半段要视为有序因为区间[left, mid]只有一个元素时单独一个元素天然是升序的没有下降沿存在。等号正是对这种情况的显式承认。类似的边界意识还体现在 target 判断区间的等号上target nums[left]要带等号target nums[mid]不能带等号因为 mid 处的值已经排除掉了。3.3 循环条件与收缩方式保证循环不变式成立循环条件使用left right配合left mid 1或right mid - 1的收缩方式可以保证不会死循环。原因很直白nums[mid]已经在循环开头比较过它不可能等于 target等于就直接返回了所以在缩小范围时mid 本身一定要从候选区间里排除否则区间无法严格收缩left right的循环可能在特定场景下无限循环。这里可以总结一条循环不变式每次循环开始前如果 target 存在于数组中那么它的下标一定落在[left, right]区间内。循环体内所有分支都维护这个不变式结束时要么返回正确下标要么区间为空返回 -1。心里有这条不变式写代码的时候就不容易晕。C 语言环境下还有一个细节numsSize为 0 时right numsSize - 1 -1循环条件0 -1为假函数直接返回 -1不会崩溃。不过为了代码可读性我习惯在函数开头显式判断一次空数组逻辑更清晰。4. 用四组边界用例实测最容易写崩的场景逐一推演光看代码不理解边界刷题很容易“背模板但写不对”。我把自己调试过程中真正容易翻车的几组用例拿出来一步步推演一遍。4.1 数组 [3, 1]target 1这就是等号救命的场景这是所有二分查找旋转数组题目里最经典的边界用例。数组长度为 2旋转点恰好在下标 1。手动模拟代码过程left 0, right 1, mid 0nums[0] 3不等于 target1。nums[left] 3 nums[mid] 3成立认为左半段[0, 0]有序。判断target nums[left] target nums[mid]即1 3 1 3为假执行left mid 1 1。第二轮left 1, right 1, mid 1nums[1] 1命中返回 1。如果写成nums[left] nums[mid]第 2 步就出错了会走 else 分支以为右半段有序但target nums[mid] target nums[right]是1 3 1 1为假执行right mid - 1 -1循环退出返回 -1。同样的逻辑target 换成 3 也逃不掉所以这组用例是我每次写完后的第一道自测题。4.2 数组 [4, 5, 6, 7, 0, 1, 2]target 0最常规的旋转场景这是题目自带的示例走一遍完整流程帮助建立手感left 0, right 6, mid 3nums[3] 7不等于 0。nums[left] 4 7成立左半段[4,5,6,7]有序。判断0 4 0 7为假执行left 4。left 4, right 6, mid 5nums[5] 1不等于 0。nums[left] 0 nums[5] 1成立左半段[0,1]有序。判断0 0 0 1为真执行right 4。left 4, right 4, mid 4nums[4] 0命中返回 4。观察这个过程会发现每次循环都在稳定的缩小搜索区间而且判断分支完全由“哪一半有序 target 是否在其中”决定没有一次是靠猜的。4.3 单元素数组 [1]target 0空区间与单元素边界数组只有一个元素时left 0, right 0进入循环后mid 0nums[0] 1不等于 0。然后判断nums[left] nums[mid]即1 1成立接着判断0 1 0 1为假执行left 1。此时left 1, right 0循环条件1 0为假退出返回 -1正确。如果 target 是 1则在第一步就直接命中返回 0。这也说明left right的循环条件对单元素数组是兼容的不需要额外特判。4.4 未旋转数组 [1, 2, 3, 4, 5]target 3特殊情形必须能正确处理题目允许 k 0也就是数组没有旋转。此时整个数组就是标准升序数组代码应当像普通二分一样工作。模拟一遍left 0, right 4, mid 2nums[2] 3直接命中返回 2。如果 target 不在数组中比如 target 6二分也会正常收缩到空区间返回 -1。没有旋转时nums[left] nums[mid]在每一轮都成立代码实际上退化成了标准二分行为完全正确。以上四组用例覆盖了长度为 2、长度正常、单元素、无旋转四种典型边界每次写完代码后把这几个用例跑一遍基本能挡住大部分边界错误。5. 复杂度分析、重复元素变体与同类题的延伸5.1 时间复杂度和空间复杂度路线A和路线B的时间复杂度都是 O(log n)每次循环都会将搜索区间缩小一半二分查找的基本性质保证了这一点。空间复杂度是 O(1)全程只用了几个整型变量没有额外开辟数组也没有递归栈开销。这也是 C 语言解法的天然优势——代码可以做到极简内存占用。不过需要留意一点当题目扩展为“有重复元素”时时间复杂度并不总是 O(log n)。以 LeetCode 81 题为例如果nums[left] nums[mid] nums[right]三个关键位置的值都相同此时既无法判断左半段是否有序也无法判断右半段是否有序只能把 left 和 right 同时往中间收缩一位放弃这部分信息。这种收缩可能导致最坏情况下每次只排除一个元素时间复杂度退化到 O(n)。所以面试时如果提到有重复的版本一定要把“最坏会退化”这一点讲清楚。5.2 变体LeetCode 81 —— 搜索旋转排序数组 II81 题是包含重复元素的版本核心修改就是在判断有序之前加一个并列条件当nums[left] nums[mid] nums[mid] nums[right]时无法判断方向直接left和right--跳过重复值后继续循环。while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; if (nums[left] nums[mid] nums[mid] nums[right]) { left; right--; } else if (nums[left] nums[mid]) { if (target nums[left] target nums[mid]) right mid - 1; else left mid 1; } else { if (target nums[mid] target nums[right]) left mid 1; else right mid - 1; } }这个并列判断放在最前面避免后续因为值相等而产生错误的“有序判断”。每次left一个单位所以最坏情况下循环次数会达到 O(n)但平均来看仍然非常快。5.3 变体LeetCode 153 / 154 —— 找旋转点本身旋转数组的最小值问题本质上就是找旋转点。第 2 节里写的findMinIndex函数就是 153 题的答案。154 题是带重复元素的版本同样的思路在nums[mid] nums[right]时无法判断最小值在哪边直接right--跳过重复值最坏也是 O(n)。这四道题串起来正好构成一个完整的“旋转数组二分查找”家族33 是基础查找81 是重复元素版查找153 是找旋转点154 是找旋转点的重复元素版。把本文的两个不变量想明白了四个题都可以用同一套思维模型推导出来。5.4 给 C 语言刷题者的一个额外建议建议在本地写一个简单测试程序把search函数和几个边界用例放在一起编译运行#include stdio.h int main(void) { int nums1[] {4,5,6,7,0,1,2}; int nums2[] {3,1}; int nums3[] {1}; int nums4[] {1,2,3,4,5}; printf(%d\n, search(nums1, 7, 0)); // 期望 4 printf(%d\n, search(nums2, 2, 1)); // 期望 1 printf(%d\n, search(nums3, 1, 1)); // 期望 0 printf(%d\n, search(nums4, 5, 3)); // 期望 2 printf(%d\n, search(nums4, 5, 6)); // 期望 -1 return 0; }每个用例都提前在注释里写好期望值编译运行后一眼就能看出哪里不对。比起直接在网页编辑器里反复提交试错这种本地调试排查边界问题的效率要高得多。我个人在实际写这个题的时候最开始也经常在[3,1]这种用例上栽跟头后来把等号归属和收缩边界彻底想清楚之后再遇到任何旋转数组的变体都能靠那两条不变量推导出正确写法。刷二分查找这类题最重要的不是背模板而是把“为什么每次能排除一半”这个理由刻在脑子里代码自然会写对。