作为一个常年跟数组、查找、排序打交道的程序员，我刷题和写业务代码时最常被问起的一个算法就是二分查找。尤其是"搜索插入位置"这类题，看似基础，却是我面试候选人和带新人时最愿意用的试金石——因为它能精准暴露一个人对循环不变量、边界区间和整数溢出的理解是否到位。今天借这个标题，把二分查找和搜索插入位置这一脉的技术细节从头到尾捋一遍，把我自己踩过的坑和沉淀下来的模板一并分享出来。
1. 边界条件决定一切：先从"循环不变量"理解二分查找
很多初学者写二分查找，代码能跑通纯属运气。今天输出结果对了，明天把数组长度从偶数改成奇数就死循环；这里把<=改成<，另一处就必须跟着把mid加一减一，否则直接越界。根本原因在于没有想清楚一件事：你的区间是左闭右闭还是左闭右开。
1.1 左闭右闭区间：最直觉也最容易出错的写法
约定区间[left, right]，也就是说left和right指向的元素都是"可能的目标值"，循环条件是while (left <= right)。当mid小于目标时，left = mid + 1；当mid大于目标时，right = mid - 1。为什么是+1和-1？因为mid已经被检查过了，它不可能是目标值，所以新的搜索区间必须把它排除在外。这一条，就是循环不变量的核心。
我见过最多的错误是：把right初始化为nums.length（这是左闭右开的心智），却用左闭右闭的<=循环。本来应该查nums[0]到nums[nums.length - 1]，结果多留了一个越界位，一旦目标比数组所有元素都大，mid就会一路涨到nums.length，直接数组越界。这种错误在IDE里编译不会报错，运行时却随机崩溃，调试起来非常恶心。
1.2 左闭右开区间：工程里更常见，但心智负担稍重
约定区间[left, right)，即right本身不参与检查，循环条件是while (left < right)。此时right初始化为nums.length是合法的，因为right只是边界、不是元素。当mid小于目标时，left = mid + 1；当mid大于目标时，right = mid（不是mid - 1）。为什么right不跳到mid - 1？因为mid已经检查过且偏大，但mid本身有可能是下一个区间的右边界，为了保持[left, right)的语义，我们把right收到mid即可。实际上对于查找失败的情况，左闭右开会自然收敛到left == right，这个位置恰好就是插入点。
对于工程代码，我推荐左闭右开，因为它和C++的迭代器范围、Python的切片语义天然一致；但如果你是备考PTA函数题或刷LeetCode，两者都行，关键是整套逻辑保持一致，不要混用。
2. 搜索插入位置：把"查不到"当成"定位目标"来解
"搜索插入位置"这道题的描述很简单：给定一个排序数组和一个目标值，如果目标值存在就返回下标，否则返回它会被顺序插入的位置。我第一次做这道题时，第一反应是"先二分查找，查不到再线性扫描找插入位置"，这样当然能做出来，但复杂度已经退化了。更好的思路是：二分查找本身就能同时回答"存在与否"和"插入位置"这两个问题。
2.1 先想清楚：插入位置的数学定义
对于一个升序数组nums和目标值target，插入位置满足：所有小于target的元素都在它左边，所有大于等于target的元素都在它右边。换句话说，我们要找的是"第一个大于等于target的位置"。当你把问题翻译成这句话，答案就清晰了：这不就是二分查找里"查找下界"的经典变体吗？所谓下界，就是满足nums[i] >= target的最小下标i。
2.2 套用二分框架：目标值存在与不存在统一处理
使用左闭右开区间[0, nums.length)，循环条件while (left < right)。每次取mid = left + (right - left) / 2（这一步是为了防止left + right整数溢出，虽然Java和C#里数组长度不会大到溢出，但这是习惯问题）。判断条件有两种情况：
- 如果
nums[mid] >= target，说明mid可能是答案，但左边可能还有更小的合法位置，所以right = mid； - 如果
nums[mid] < target，说明mid及其左边都不可能是答案，所以left = mid + 1。
循环结束时left == right，这个位置就是答案。你不需要在循环里单独判断"找到了没有"——因为当target存在于数组中时，第一次遇到相等元素时right会被拉到该位置；当target不存在时，left会一路推进到第一个大于target的位置。
2.3 用几个具体例子验证推导
拿nums = [1, 3, 5, 6]来验算：
target = 5：mid = 1，nums[1] = 3 < 5，left = 2；mid = 3，nums[3] = 6 >= 5，right = 3；mid = 2，nums[2] = 5 >= 5，right = 2；循环结束，返回2。正确。target = 2：mid = 1，nums[1] = 3 >= 2，right = 1；mid = 0，nums[0] = 1 < 2，left = 1；循环结束，返回1。正确，2插入在1和3之间。target = 7：一路left右移，最后left = 4，返回4，正好是数组长度，合法插入位。target = 0：right一路左移，最后left = 0，返回0，插到最前面。
这个推导过程就是我最建议读者亲自走一遍的环节。别只看代码，拿纸笔跟着常数个例子走三遍，你对二分查找的理解会立刻上一个台阶。
3. 一套可复用的C语言实现模板与PTA函数题的提交技巧
网上二分查找的模板五花八门，有的用<=，有的用<，有的每次把mid加一，看得人眼花缭乱。我个人的建议是：只记一套，把它写熟，然后所有变体都往这套上靠。下面给出我平时最常用的左闭右开C语言实现，这套代码可以直接用来写PTA函数题。
3.1 基础函数：直接返回插入位置
int searchInsert(int* nums, int numsSize, int target) { int left = 0; int right = numsSize; // 左闭右开，right不参与检查 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; // mid可能是答案，保留 } else { left = mid + 1; // mid不可能是答案，跳过 } } return left; // left == right，即插入位置 }这段代码返回的left天然就是插入位置。如果你明确知道target一定存在，想返回它的下标，把>=改成==然后提前返回即可；如果存在多个相等值想找最左边的，>=的写法依然是正确答案。
3.2 PTA函数题特有的两个坑
PTA（拼题A）平台和LeetCode不太一样，它的函数题会要求你填写特定函数名和参数列表，而且评测数据往往包含边界值。我在PTA上提交这类题目时遇到过两个隐蔽的坑：
第一个是返回类型。有些题目要求返回int，但也有变体要求返回位置同时通过指针回传状态，你要仔细看题目说明，别想当然。第二个是空数组。PTA的测试用例有时候会给出numsSize = 0，此时我的代码直接跳过循环返回0，合法；但如果你用左闭右闭并且初始化right = numsSize - 1，int right = -1在C语言里能编译，循环直接不执行，返回-1就不对了。所以看到空数组用例时，务必确认自己的初始条件能让返回值等于0。
3.3 顺手复习二分查找的朴素写法
如果只想判断target是否存在并返回下标，用经典的左闭右闭版本：
int binarySearch(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) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }这套写法的要点就一句：<=对应左右都闭，新一轮区间要排除已检查过的mid。这两段代码我建议你对照着看，一个管"查找是否存在"，一个管"找插入位置"，本质上是一枚硬币的两面。
4. 死循环与越界的完整排查链路：这些坑我帮你趟过了
二分查找的报错往往不是"答案错误"这么简单，而是"超出时间限制"或者运行时的野指针崩溃。我在这里复盘一次真实的排查过程，从现象倒推原因，你以后遇到类似问题可以直接套用这个排查路径。
4.1 现象一：程序卡死或超时，疑似死循环
有一次我写一个变体题，判断条件是if (nums[mid] < target) left = mid;。乍一看没问题：mid小于目标值，把左边界移到mid，缩小范围。但问题出在当left和right相邻时：假设left = 3, right = 4，mid = 3 + (4-3)/2 = 3，如果nums[3] < target成立，left = 3，区间纹丝不动，这就死循环了。
排查思路非常简单：在循环体里打印left、right、mid三个变量，看每一轮有没有缩小区间。只要出现mid == left且left被赋值为mid的情况，死循环就是必然的。修复方案是把left = mid改成left = mid + 1——因为mid已经被检查过了，它既然小于target，就绝不可能是答案，必须排除。
4.2 现象二：越界访问，返回结果飘忽不定
另一个常见现象是本地跑没问题，放到评测机上偶尔崩溃。这通常是因为right初始化和循环条件不匹配。比如你初始化right = numsSize（左闭右开），却用while (left <= right)（左闭右闭的循环条件）。当target大于数组所有元素时，left会一路增加到numsSize，然后下一轮循环还会进来一次，mid越界，nums[mid]访问野内存。
遇到这类问题，我的排查顺序是：先检查right的初值，再检查循环条件，最后检查mid两侧的边界赋值，三处必须属于同一套区间语义。用一个表格做对照：
| 区间语义 | 初始left | 初始right | 循环条件 | nums[mid] < target时 | nums[mid] > target时 |
|---|---|---|---|---|---|
| 左闭右闭 | 0 | numsSize - 1 | left <= right | left = mid + 1 | right = mid - 1 |
| 左闭右开 | 0 | numsSize | left < right | left = mid + 1 | right = mid |
| 左开右开（不推荐） | -1 | numsSize | left + 1 < right | left = mid | right = mid |
我个人的建议是把第三行直接从你的备选方案里删掉。左开右开虽然能规避一些边界问题，但对你理解循环不变量没有任何帮助，而且在工程代码里几乎见不到。
4.3 现象三：结果差一位，总是返回插入位置的前一个下标
这个坑我见过最多次。原因往往是你在循环结束后下意识地写了return left - 1或者return right。为什么会有这种冲动？因为很多人把"插入位置"和"最后一个小于等于target的位置"搞混了。想想看：插入位置前面那个元素，才是最后一个小于target的元素，两者相差1。如果你在思考时先找到了"小于target的分界点"，再手动加1，倒也没错；但如果你直接把二分查找的失败返回值（通常是left）减一，那就错了。
正确的做法是：把题目翻译成"找第一个大于等于target的下标"，直接返回left，根本不需要事后修正。如果你在调试中发现答案总是差1，回到问题定义重新审题，不要试图在答案上打补丁。
4.4 一个实用调试技巧：用断言检查区间合法性
在本地调试时，我习惯在循环开始处加一句断言：
// 断言：left和right必须始终合法 assert(left >= 0 && right <= numsSize && left <= right);这句断言能抓住大量越界和区间错乱问题。它只影响调试，不影响发布，但能让你在几轮迭代内就锁定是哪一行的区间更新出了问题。
5. 举一反三：从搜索插入位置出发，掌握二分查找的变体矩阵
只学会一道题是不够的。搜索插入位置这个题，往深了走可以派生出好几个高频变体，理解了这一脉，你就能一次性拿下一整类问题。
5.1 变体一：查找第一个等于target的下标
这是"搜索插入位置"的孪生题。当数组中存在多个相等的target时，我们要最左边的那个。思路是把条件从>=拆开：当nums[mid] >= target时，right = mid；当nums[mid] < target时，left = mid + 1。循环结束后检查left是否越界且nums[left] == target，如果是就返回left，否则返回-1。这个流程和搜索插入位置的代码几乎一模一样，只在最后多了一步验证。
5.2 变体二：查找最后一个等于target的下标
如果要求最右边的相等元素，可以有两种做法：一是用对称的逻辑，nums[mid] <= target时left = mid，nums[mid] > target时right = mid - 1；二是直接调用上面的"第一个等于"函数，再加一点小技巧。我习惯用第一种，但注意left = mid这种赋值必须配合while (left < right)并且mid要向上取整，也就是mid = left + (right - left + 1) / 2，否则又会出现前面说的相邻时死循环。
这时候你会发现，二分的"上取整"和下取整的选择不是玄学，而是由你赋值的方向决定的——你把left往右推，就得上取整防止卡住；你把right往左收，就下取整。这个规律理解清楚之后，你再也不会纠结什么时候mid + 1。
5.3 变体三：在旋转有序数组中查找目标值
比如[4,5,6,7,0,1,2]这种数组，它整体不是有序的，但分两段各自有序。经典的解法是先二分判断当前中点落在左半段还是右半段，再根据目标值的范围和有序段的关系收缩区间。这个题的代码细节比搜索插入位置复杂不少，但核心思想不变：每次都根据"已经确定有序的那一段"来判断目标值可能在哪一边。能把搜索插入位置的模板吃透，再去看旋转数组的题，你会发现自己理解速度快很多。
5.4 工程中的应用：不只是刷题
二分查找在工程里到处都是。我举几个实际例子：
- 在有序的日志时间戳列表里查找"第一条晚于某个时间点"的日志，这本质就是搜索插入位置。
- 在数据库的B+树索引中，查找某个主键应该插入的叶子节点，底层也是二分。
- 在连续数值区间上做概率采样（按权重随机选一个下标），先把权重数组转成前缀和，然后随机生成一个数，用二分找第一个大于等于它前缀和的位置。
- 在分布式存储的元数据分片中，定位一个Key应该路由到哪个分片，有序的Key区间加上二分就是最简单的路由表实现。
所以说搜索插入位置不是一个只存在于题目里的抽象问题，它和真实世界的"在有序序列中定位落点"是同一个操作，只是规模大了、约束多了而已。
5.5 自己出题：把模板变成你自己的工具
我建议读者做这样一件事：把上面给出的左闭右开模板背熟之后，自己造一些测试数据来验证，比如空数组、单元素数组、全部相等的数组、目标值小于所有元素、目标值大于所有元素。每个用例都手动推演一遍，并把推演结果和程序输出比对。这个过程本身比刷十道题还管用，因为它逼你遍历了所有边界分支。
等你能熟练地解释"为什么循环结束时left就是答案"，而不是"反正跑对了"的时候，二分查找于你而言就不再是背模板了，而是一把顺手工具。面试的时候，如果面试官追问"你的代码在边界情况下会不会越界？为什么不会？"，你能气定神闲地把区间语义讲出来，这一关就算彻底通关了。
我在实际编码中，凡是涉及有序序列定位的活，都会下意识地把这套左闭右开模板拿出来改一改，十几分钟就能落地一个可靠版本；在PTA上提交前，也会专门检查right的初值和循环条件是否匹配，这两个位置占了我二分错误的一半以上。希望这篇拆解也能帮你把二分查找的水面彻底踩实，后面再遇到各种变体题，你心里就有底了。
