二分查找与搜索插入位置：循环不变量与边界条件全解析-北京尧图网络

作为一个常年跟数组、查找、排序打交道的程序员我刷题和写业务代码时最常被问起的一个算法就是二分查找。尤其是搜索插入位置这类题看似基础却是我面试候选人和带新人时最愿意用的试金石——因为它能精准暴露一个人对循环不变量、边界区间和整数溢出的理解是否到位。今天借这个标题把二分查找和搜索插入位置这一脉的技术细节从头到尾捋一遍把我自己踩过的坑和沉淀下来的模板一并分享出来。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 5mid 1nums[1] 3 5left 2mid 3nums[3] 6 5right 3mid 2nums[2] 5 5right 2循环结束返回2。正确。target 2mid 1nums[1] 3 2right 1mid 0nums[0] 1 2left 1循环结束返回1。正确2插入在1和3之间。target 7一路left右移最后left 4返回4正好是数组长度合法插入位。target 0right一路左移最后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 - 1int 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 4mid 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时左闭右闭0numsSize - 1left rightleft mid 1right mid - 1左闭右开0numsSizeleft rightleft mid 1right mid左开右开不推荐-1numsSizeleft 1 rightleft midright 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 midnums[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的初值和循环条件是否匹配这两个位置占了我二分错误的一半以上。希望这篇拆解也能帮你把二分查找的水面彻底踩实后面再遇到各种变体题你心里就有底了。

二分查找与搜索插入位置：循环不变量与边界条件全解析

相关推荐

模型路由实战：如何用智能调度把Token成本砍掉60%

VDC是什么？一文读懂虚拟设计与施工和虚拟数据中心

校园网上店铺系统：SpringBoot+Vue前后端分离完整实战

更多资讯

ABB机器人RobotStudio安装全攻略：从下载到虚拟控制器跑通

claude-mem实战：给Claude装上持久记忆的MCP服务指南

工业异常检测基础模型：从判别式任务到健康语义感知

工业异常检测基础模型：从离群点到流形曲率的范式跃迁

从工具调用到技能体系：Agent稳定运行的工程化实践

CCKS2019中文NER实战：从BIO标注到BERT+CRF全流程避坑

今日更新

Agent Skills 完全指南：原理、写法、安装与实战避坑

Agent Skills 实战：从 Genkit 定义到 GKE 部署与排查

Agent Skills 实战：从设计到调试的完整指南

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？