1. 先读懂题意它考的不是“查找”是“第一个不小于target的位置”LeetCode 35 这道搜索插入位置我刷过的次数不止一两回它标着 Easy但翻车概率一点都不低。我第一次提交时满脑子都是“找到 target 就返回下标找不到就把 left 填上去”结果 target 比整个数组都大时返回了一个看上去像数组越界的值——C 语言的数组越界不会立刻报错判题系统却稳准狠地给了我一个 WA。后来我把这题归为“二分查找类的入门必修”因为它的难点不在读懂题目而在想清楚插入位置到底对应数组里的哪个下标。题目描述很简单给你一个升序排列的整数数组 nums 和一个目标值 target如果 target 在数组里就返回它所在的下标如果不在就返回它被按顺序插入后应该在的位置。LeetCode 给 C 语言留的函数签名是int searchInsert(int* nums, int numsSize, int target)返回值是一个 int。题目自带的几个示例是输入nums [1,3,5,6],target 5输出 2输入nums [1,3,5,6],target 2输出 1输入nums [1,3,5,6],target 7输出 4输入nums [1,3,5,6],target 0输出 0前两个例子好理解第三个和第四个才是关键target 压根不在数组里但你仍然要返回一个合法下标而且这个下标可能等于数组长度。这就是“插入位置”和普通“查找结果”最大的不同。1.1 把“插入位置”翻译成一个二元判定条件插入位置不是“target 前面的那个位置”也不是“跟 target 相邻的位置”。它的严格定义是第一个满足nums[pos] target的下标 pos。如果全部元素都比 target 小pos 就是numsSize。这个定义同时覆盖了“target 存在”和“target 不存在”两种情况。二分查找的所有逻辑都应该建立在这条定义上而不是建立在“找相等元素”上。举个例子nums [1,3,5,6]target 2。逐个扫描的话nums[0]1 2nums[1]3 2所以第一个不小于 2 的下标是 1答案就是 1。target 5时nums[2]5 5所以返回 2。target 7时四个元素都小于 7返回 4。target 0时第一个元素 1 就已经大于 0返回 0。一旦换了这套语言题目给的所有情况全都能统一处理不用再区分“找到了”还是“没找到”。1.2 为什么不能把这道题当成普通查找题普通的二分查值题目里会保证 target 一定存在你要做的只是在数组中把这个值挖出来。这道题偏偏不保证于是网上不少题解会这么写先二分找 target找到了直接返回找不到就返回 left。这么做确实能过样例但你要注意它把“不存在时插入到哪”这个问题扔给了循环结束后的 left而 left 到底代表什么很多人其实没想明白。我在前面给出的定义之所以重要是因为它直接给出了目标我们要找的是判定序列中第一个 True 的位置不是“相等”的位置也不是“大于”的位置。本文后面给出的 C 语言代码全部围绕nums[mid] target这个比较条件展开目的就是让 left 最终停在第一个 target的位置上。另外要提醒一句题目只说是“排序数组”并没有保证元素互不相同。碰到nums [1,3,3,3,5]、target 3这种情况如果按“找到就返回任意一个下标”写返回值可能是 1、2 或 3都能过但如果按“第一个不小于 target”来写返回值稳定是 1。这个稳定性在后面的延伸题里会变得非常重要因为很多查找类变体题要求的正是这种精确语义。2. 为什么必须二分从暴力解法看出题人到底在逼你干什么2.1 暴力版本有多简单代价就有多大最简单直接的思路从头到尾扫描。碰到nums[i] target就返回 i扫完了就返回numsSize。代码只有七八行正确性也不难证明int searchInsert(int* nums, int numsSize, int target) { for (int i 0; i numsSize; i) { if (nums[i] target) { return i; } } return numsSize; }问题是这道题在 LeetCode 的说明里明确写了要求时间复杂度必须为 O(log n)。翻译成人话就是你只能通过一次次折半把查找区间缩到不能再缩。O(n) 的线性扫描在概念上没错但它完全没有利用“数组有序”这条信息在一个规模很大的列表上会吃满线性时间。我实习面试的时候遇到过类似的问题面试官问完暴力解法后紧接着就是“能不能更快”你一旦写出二分他就知道你抓住了排序数组的核心红利。2.2 有序数组给了我们什么红利二分能成立的真正前提不是“数组有序”这四个字而是“可以把判定结果看成一个单调序列”。我们定义一个谓词P(i)表示nums[i] target。因为数组升序P 的结果肯定是一串 False 后面跟着一串 TrueFalse, False, ..., False, True, True, ..., True目标就是找到第一个出现 True 的下标。对这种“灰转白”只发生一次的单调序列最理想的搜索方式就是二分每次看中点如果中点还是 False说明答案在右边左边界直接挪到中点加一如果中点已经是 True说明答案在中点或更左右边界挪到中点减一。每次排除一半查找空间log2(数组长度)步内必定收敛。2.3 把复杂度的账算清楚数组长度 n暴力法是 O(n)二分法是 O(log n)。n100 时差距不明显n10^5 时暴力最坏要跑 10 万次循环二分最多 17 次n10^9 时二分也就 30 次左右。这道题虽然不会真的拉一个上亿长度的数组过来压测但 O(log n) 的要求会时刻提醒你不要用线性扫描敷衍。我本地测试时哪怕想着“反正数组短扫描无所谓”提交到 LeetCode 也会有压力测试用例让你感受到差距。所以别偷懒老老实实二分。2.4 边界思考为什么不需要特判最后一个元素很多人会忍不住先判断一下target是否大于nums[numsSize-1]然后预先返回numsSize。这种做法在二分模板里是多余的因为循环终止条件自然会处理它。以闭区间模板为例当数组所有元素都小于 target 时left 会一路右移直到left numsSize时循环结束这时 left 正好等于numsSize也就是题目要求的插入位置。特判写多了反而容易埋 bug一旦有人写错数组下标拿nums[numsSize]这种越界位置来比较C 语言不会马上崩但结果是未定义行为谁知道判题机会判出什么。3. C语言实现一套能把边界写对的二分模板3.1 我为什么选“闭区间 [left, right]”二分查找的写法主流有两种闭区间left right和左闭右开left right。两种都能过但我个人强烈推荐闭区间理由有三。第一初始left0、rightnumsSize-1语义最直观搜索区间就是数组真实下标范围。第二循环结束后 left 和 right 的位置关系非常干净left right 1这个等式可以帮助你快速判断答案。第三空数组时right-1循环天然不进入直接返回 0不需要额外写特判。正是它处理边界时“不用额外 if”这个特性让我这种容易手抖的人少踩了一半的坑。左闭右开模板在空数组时虽然也容易处理但它要求你在返回前多做一次“去重判断”代码更容易绕晕。3.2 完整代码可以直接编译运行的版本#include stdio.h int searchInsert(int* nums, int numsSize, int target) { int left 0; int right numsSize - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { // nums[mid] 不可能是结果mid 左边更不可能继续往右找 left mid 1; } else { // nums[mid] targetmid 可能是答案但也可能答案在更左边 right mid - 1; } } // 循环结束时left 是第一个满足 nums[left] target 的下标 return left; }没有提前 return 的奇技淫巧没有numsSize 0的特判整个函数就一个 while。唯一要盯住的是两个分支nums[mid] target时往右缩else时往左缩。注意这里else包含了nums[mid] target的情况说明即使命中了也要继续往左搜因为我们希望拿到的是“第一个不小于 target”的位置而不是随便一个命中位置。3.3 循环不变式这段代码为什么是对的如果你只抄代码不理解它换个条件马上又错。我当时为了彻底搞懂把循环不变式写在注释里整个循环维护两件事——left 左边不含 left的所有元素都严格小于 targetright 右边不含 right的所有元素都大于等于 target。初始时left0左边没有元素条件自然成立rightnumsSize-1右边没有元素条件也自然成立。每次循环取 mid如果nums[mid] target就把 left 挪到mid1于是新的 left 左边还是全部小于 target如果nums[mid] target就把 right 挪到mid-1于是新的 right 右边还是全部大于等于 target。每轮都在维持这个性质直到left right搜索区间为空此时 left 恰好是“左边全小于、右边全大于等于”的分界点也就是答案。这是我见过对二分最省事的理解方式不要背循环里的1、-1是为什么背你维护的那个不变量。只要不变量成立代码的正确性就是稳定的。3.4 一个 C 语言特有的细节mid 的表达式int mid (left right) / 2;是新手最爱写的版本但这个写法有个隐患在真正大数组的二分里left right可能超出 int 能表示的范围。C 标准规定有符号整数溢出是未定义行为一旦发生程序行为完全不可预期。改用left (right - left) / 2后先算差再折半left 加上一个不会超过 right 的值整个过程都不会越过 int 上限。LeetCode 原题里 numsSize 一般不会大到触发溢出但面试官经常拿这个细节试探你答不上来很掉分。这也是我不把两个数相加直接写在中间的原因。本地练习时我会刻意把数组长度拉到接近INT_MAX的范围做一次测试确认这种写法不会飘。4. 边界条件复盘那些最容易翻车的case4.1 我把测试用例分成六类先给一张表每一行都是我实际提交前会先在本地跑过的 case场景数组target期望返回值循环结束时的 left空数组长度 0任意00小于所有元素[1,3,5,6]000存在于数组首部[1,3,5,6]100存在于数组中部[1,3,5,6]522不存在且落在中间[1,3,5,6]211大于所有元素[1,3,5,6]744重复元素[1,3,3,3,5]311前六行来自题目自带的示例和推导最后一行是我自己加进去的重复元素在题目里不违反“排序数组”的约束。按照“第一个不小于 target”的定义答案应该是第一个 3 所在的下标 1。如果你的代码返回了 2 或 3虽然这道题的判题系统可能仍然算你 AC但它说明你的代码语义并不是严格的 lower_bound一旦遇到变体题就会出问题。4.2 常见错误写法一提前 return 命中位置很多人写到这里会忍不住加一句if (nums[mid] target) return mid;。在本题这个提前返回不会改变正确性因为只要命中任意一个命中位置都能作为答案。但它坏在一点破坏了“第一个不小于 target”的语义。数组有重复元素时提前返回的可能不是第一个。后续你要扩展这道题去实现“找第一个等于 target 的下标”时这种写法必须推翻重来。我从读者提问里看到过不少人在 35 题里这样写下一个题遇到“在排序数组中查找元素的第一个和最后一个位置”又卡住了。所以我的建议是既然题目没有要求返回任意命中位置干脆别提前 return让循环统一收缩最后拿 left 说话。4.3 常见错误写法二循环条件写错导致漏答案还有一个高频失误是把while (left right)写成while (left right)。对于本模板当你使用 left right 时循环结束时 left 等于 right但你没有验证这个位置算不算答案必须再补一轮判断。尤其 target 存在且刚好是最后一个元素时比如nums[1,3,5,6]、target6left right 的写法很可能会在到达正确答案之前退出循环。很多人最后靠 patch 一个额外 if 才过代码出来很难看。闭区间模板保持是最稳的空数组时right -1直接不循环也不会访问越界。我自己写题时会把所有的二分模板统一成同一种避免在不同代码之间来回切换时把边界条件搞混。4.4 实验验证手推一遍最容易错的case拿nums[1,3,5,6],target2走一遍流程初始left0, right3mid1nums[1]3 2所以right0再算mid0nums[0]1 2left1此时left1, right0循环结束返回left1。答案正确。再看target7mid1时3 7left2mid2时5 7left3mid3时6 7left4循环结束返回 4。整个过程一次都没有触碰nums[4]因为left4时 while 的left right已经不成立。想让数组越界都难——这是闭区间模板最大的好处。5. 本地验证与调试经验二分代码是这样被调对的5.1 一个值得长期保存的测试 main光在 LeetCode 网页上提交看不出问题在哪。我的习惯是把函数和测试用例都写到本地用 assert 批量验证。下面这段代码可以直接保存为search_insert.c#include stdio.h #include assert.h int searchInsert(int* nums, int numsSize, int target) { int left 0; int right numsSize - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; } int main(void) { int a1[] {1, 3, 5, 6}; assert(searchInsert(a1, 4, 5) 2); assert(searchInsert(a1, 4, 2) 1); assert(searchInsert(a1, 4, 7) 4); assert(searchInsert(a1, 4, 0) 0); int a2[] {1}; assert(searchInsert(a2, 1, 0) 0); assert(searchInsert(a2, 1, 1) 0); assert(searchInsert(a2, 1, 2) 1); int a3[] {1, 3, 3, 3, 5}; assert(searchInsert(a3, 5, 3) 1); // 空数组right -1循环不进入直接返回 0 assert(searchInsert(NULL, 0, 10) 0); printf(all tests passed\n); return 0; }编译命令我一般用gcc -stdc11 -Wall -Wextra -o test search_insert.c ./test看到 all tests passed 才算完。这里有个小细节searchInsert(NULL, 0, 10)之所以安全是因为函数第一行就算出right -1while 判断left right直接失败全程没有解引用指针。如果哪天有人把函数改成先访问nums[numsSize-1]这个测试会立刻踩空指针所以它是有意义的。5.2 二分代码调试的核心把收缩过程打出来如果断言没过光盯着代码看很难发现哪里缩错了。我的习惯是写一个临时调试函数把每轮的 left、right、mid 和nums[mid]全部打印出来void debug(const char* label, int* nums, int n, int target) { int left 0, right n - 1; printf(%s target%d\n, label, target); while (left right) { int mid left (right - left) / 2; printf( left%d right%d mid%d nums[mid]%d\n, left, right, mid, nums[mid]); if (nums[mid] target) left mid 1; else right mid - 1; } printf( result%d\n, left); }调用debug(case-2, a1, 4, 2)能看到 target2 时每一步如何把 right 从 3 压到 0、再把 left 从 0 抬到 1。眼睛盯着输出很多边界错误当场就能看出来如果某一步 left 跳到了数组范围外那多半是分支条件写反如果 right 一直没动可能是 else 分支没进来。这个调试函数写完可以留着以后做别的二分题直接套。5.3 C 语言里坑爹的越界为什么不能赌说句老实话C 语言的数组越界在本地经常“看起来没事”你在 left 已经等于 numsSize 时去读nums[left]它可能恰好读到相邻栈空间的一段垃圾数据程序不崩甚至输出还正常最后提交判题才 WA。所以我在写 C 版二分时有个强迫症凡是能通过循环条件天然避免越界的写法坚决不写额外的边界 if写完后再用 AddressSanitizer 编译一遍gcc -stdc11 -fsanitizeaddress -g -o test search_insert.c ./testASan 一旦发现越界访问会直接报错比任何肉眼 review 都管用。这道题如果越界基本就是left mid 1后下一次循环去读了nums[left]把 while 条件检查好、或者像我这样用闭区间让循环天然退出就彻底根治了。6. 延伸这题背后是 lower_bound 思想远不止一个 Easy6.1 改一行就是 upper_boundsearchInsert 这个实现本质就是 C 里的lower_bound返回第一个target 的元素位置。如果你把分支里的改成即if (nums[mid] target) left mid 1;它就变成了upper_bound返回第一个target 的位置。以nums[1,3,5,6]为例target3原来的 searchInsert 返回 1第一个 3改完返回 2第一个 5。这个变换比背两个函数还划算因为循环不变量完全一样只是把“等于也继续往右缩”和“等于不往右缩”换了一下。面试时如果被问“有没有重复元素”你直接把这个改动摆出来比现场写新函数快得多。6.2 拿它来回答“最后一个小于 target 的位置”既然 left 是第一个target 的位置那么left - 1就是最后一个target 的位置前提是left - 1 0。比如nums[1,3,5,6]target3left1left-10nums[0]1就是最后一个小于 3 的元素target0时 left0left-1-1说明没有元素小于 0。这种“相邻下标配对”的用法在做区间统计时特别常见先lower_bound拿到起点再upper_bound拿到终点两个下标相减就是元素个数重复元素也能一起算完。比如统计数组中有几个 3就是upper_bound(3) - lower_bound(3)一行代码的事。6.3 同一个模板通吃的大批题目刷到后面你会发现旋转数组的最小值、山峰数组的峰值、在排序数组中查找元素的第一个和最后一个位置考的全是同一个东西给定一个单调的布尔判定序列找第一个 True 或最后一个 False。35 题把它放在最前面是帮你把循环不变量和 left/right 的分界语义练熟。你真正记住的不是代码而是“left 左边全不满足、right 右边全满足”这个模型。一旦面试题变成“arr[i] 和 i 的关系在某点发生变化”你就能立刻套用这个模板把新问题还原成一次标准的二分搜索。最后分享我自己的一个经验二分题最忌讳的是凭感觉改1、-1每改一次边界就可能换一种坏法。我后来习惯先写注释把循环不变量和退出条件写清楚再动手写 while。弱化记忆负担之后这类题的正确率才稳定下来。搜索插入位置只是第一步但它是你吃透二分这条线的钥匙。