彻底搞懂二分查找：check函数与边界条件详解

二分查找这名字凡是写代码的没有不知道的。但就这么个基础算法年年面试、年年刷题、年年有同事在边界条件上写崩。我自己带过好几个实习生让他们写一个“在有序数组里找第一个大于等于 target 的下标”交上来的版本五花八门能一次跑对的不到一半。而且错的那一半你让他单步调试他还真不一定能看出来自己错在哪。今天我想好好聊聊二分查找板子这件事重点讲 check() 函数在设计这套板子里的核心位置以及怎么把“背板子”变成“真正理解边界为什么这么写”。这篇东西最适合三类人看一是刚开始刷算法题、被各种 left/right 边界搞到怀疑人生的学生二是工作中偶尔要手写二分、但每次都靠临时推演不敢直接落笔的开发者三是准备面试、想把基础算法讲清楚原理而不是只会背代码的人。我会从最常见的翻车场景切入把死循环的成因、check() 函数的设计原则、三个通用板子的适用场景全部拆开讲明白最后给几个可以直接抄走的实战案例。1. 为什么一个“简单”算法能难住这么多程序员1.1 从一次现场翻车说起去年我带过一个同学做一个小需求在一个按时间排序的日志 ID 数组里找出“时间戳大于等于某个阈值”的第一条记录。需求描述得很清楚这就是典型的 lower_bound。他写出来的代码长这样int findFirst(vectorint arr, int target) { int l 0, r arr.size() - 1; while (l r) { int mid (l r) / 2; if (arr[mid] target) { r mid; } else { l mid; } } return l; }看着是不是挺像那么回事但实际上这段代码在某些输入下会死循环。问题出在else分支里l mid配合mid (l r) / 2的向下取整。当l 2, r 3且arr[2] target时mid 2然后l mid 2l 和 r 永远卡在 2 和 3退不出去。这种错误太典型了它不是粗心而是对二分查找的“收敛机制”缺乏本质理解。1.2 大多数人翻车的三个固定套路我把这些年见过的二分错误归纳成三类。第一类是边界符号混乱。while (l r)、while (l r)、while (l 1 r)到底该用哪个r mid还是r mid - 1l mid还是l mid 1每一行看起来都对组合到一起就是错的。第二类是返回位置拿不准。循环结束后到底返回 l 还是 r还是返回 mid不同写法结果不一样甚至同一个写法的不同输入也会给出不同答案。第三类是逻辑判断反了。把 check() 的条件写反找到的不是第一个满足条件的位置而是最后一个不满足条件的位置差一个下标结果完全错误。这三类问题的根源其实是同一个没有把二分查找看成一个“在布尔序列上找翻转点”的过程。大多数人的思维停留在“在数组里找一个目标值”于是每一步都在纠结“等不等号”这种表层问题。1.3 换个角度看二分从“找数字”到“找分界点”我想让你把二分查找理解为另一件事维护一个候选区间区间里的每个元素都会经过 check(mid) 的判定返回 true 或 false。如果这个布尔序列是单调的——要么一路 true 到某个位置后全是 false要么一路 false 到某个位置后全是 true——那么二分的任务就是找出这个翻转点的位置。举个例子数组[1, 3, 5, 7, 9, 11]我们要找第一个大于等于 6 的位置。把每个元素和 6 比较得到的布尔序列是1 3 5 7 9 11 F F F T T T二分就是在找第一个 T 出现的位置也就是下标 3。至于“下标 3 这个位置的值是 7”反而不是你要关心的核心。一旦建立这个视角check() 函数的地位自然就凸显出来了——整个二分框架只负责收敛区间业务逻辑全部收进 check() 里。框架可以背check() 必须会写。2. check() 函数在二分框架里的真实角色2.1 check() 是什么判定问题与搜索问题的转换check(mid) 的本质是把一个“搜索问题”转化成“判定问题”。搜索问题是“值在哪”判定问题是“这个位置满不满足条件”。计算机科学里这叫 decision problem 与 search problem 的归约但在工程里你不需要记这些术语只需要记住一点二分能工作的前提是你能写出一个对任意 mid 都能给出确定 true/false 答案的判断函数。这个函数通常长这样bool check(int mid) { // 根据题意判断位置 mid 是否满足条件 return arr[mid] target; // 只是举例 }它的输入是一个候选位置输出是“这个位置在布尔序列中落在哪一侧”。二分框架根据这个输出去收缩区间。2.2 一个完整板子的框架拆解不管外面包了多少变化一套完整的二分板子永远由三个部分组成区间初始化、循环收缩、check() 决定走向。拿最常用的左闭右开板子举例// 在 arr 中找第一个 target 的下标arr 已升序 int lowerBound(const vectorint arr, int target) { int l 0, r (int)arr.size(); // 1. 区间 [l, r) while (l r) { // 2. 循环收缩 int mid l (r - l) / 2; // 取中点 if (arr[mid] target) { // 3. check(mid) r mid; // mid 满足条件答案在左侧 } else { l mid 1; // mid 不满足答案在右侧 } } return l; // 循环结束后 l 就是答案 }注意看这套板子里真正有业务语义的只有一行arr[mid] target。剩下全是模板。所以你把板子背熟之后解题的注意力就应该完全放到这一行 check 怎么写、边界往里收一收会不会漏答案上而不是每次从 while 循环开始重新发明二分的旋钮。2.3 为什么 check() 必须能回答“单调性”问题“check(mid) 返回 true 还是 false”这个判定本身天然要求背后的布尔序列是单调的。如果不单调二分就会像一个在波浪里捞针的人左右横跳最后捞到哪全凭运气。这里说的单调不是指数组的数值单调而是指经过 check 之后得到的布尔序列单调。我之前遇到过有人想在“先升后降”的数组里找最大值用二分套了一个 check判定条件是arr[mid] arr[mid 1]。这个判定本身是对的因为它把数组变成了false false false true true的形状——前半段不存在相邻下降后半段处处相邻下降于是在“找第一个 true”的语义下可以二分。这就是 check() 单调性的精髓不直接看原序列看的是 check 之后构成的布尔序列。所以在动手写 check() 之前先花十秒钟问自己一句如果我沿着数组从左到右依次调用 check(0), check(1), ..., check(n-1)返回的结果会不会是先一段 true 后一段 false或者先一段 false 后一段 true如果答案是“会”放心用二分如果答案是“不会它来回跳”趁早换线性扫描或别的算法。3. 三个通用板子按场景直接选3.1 闭区间板子最直观适合精确定位闭区间板子用l 0, r n - 1循环条件while (l r)更新时l mid 1或r mid - 1。它的特点是循环结束后 l rmid 走完所有可能位置最适合“精确判断某个值是否存在”的场景。// 精确查找返回值等于 target 的下标不存在返回 -1 int exactSearch(const vectorint arr, int target) { int l 0, r (int)arr.size() - 1; while (l r) { int mid l (r - l) / 2; if (arr[mid] target) return mid; if (arr[mid] target) { l mid 1; } else { r mid - 1; } } return -1; }这个板子的缺点是一旦你要做的是“找第一个/最后一个满足条件的位置”l mid 1这种“跳过”操作很容易让你漏掉边界。我建议精确定位之外的需求尽量别用闭区间板子避免同一套代码既要管等号又要管不等号把简单事情搞复杂。3.2 左闭右开板子STL 同款函数题首选左闭右开板子用l 0, r n循环条件while (l r)更新时r mid或l mid 1。它的好处是循环结束时l r不用纠结返回谁而且语义跟 C STL 里的lower_bound、upper_bound完全一致直接对标标准库实现。// 找第一个 target 的下标等价于 std::lower_bound int lowerBound(const vectorint arr, int target) { int l 0, r (int)arr.size(); while (l r) { int mid l (r - l) / 2; if (arr[mid] target) { r mid; } else { l mid 1; } } return l; }如果想找“第一个 target 的下标”等价于std::upper_bound只需要把 check 改成arr[mid] target。可以看到框架一行不动变的只有 check 里的不等号。这就是把 check 独立出来带给你的自由度。3.3 开区间板子红蓝染色最不容易写错开区间板子用l -1, r n循环条件while (l 1 r)更新时l mid或r mid。这个板子看着有点怪但它是三个里最不容易踩死循环坑的因为它把 left 和 right 都当成“已经确定的区域”循环区间是 (l, r)永远不包含左右两端。// 同样是找第一个 target 的下标 int lowerBoundOpen(const vectorint arr, int target) { int l -1, r (int)arr.size(); while (l 1 r) { int mid l (r - l) / 2; if (arr[mid] target) { r mid; // 右侧收缩r 始终是“满足条件”的边界 } else { l mid; // 左侧扩张l 始终是“不满足条件”的边界 } } return r; }我个人非常推荐刚开始学二分的人从这个板子入手。它的思考方式很粗暴直接左边染蓝不满足右边染红满足每次把 mid 染成对应颜色最后蓝红交界处的红色那边就是答案。你不需要记mid 1还是mid - 1因为左右更新都只是l mid和r mid不存在跳过一个位置的问题。三个板子的对比如下板子类型初始化循环条件mid 更新习惯适用场景死循环风险闭区间l0, rn-1l rlmid1 / rmid-1精确查找低但要跳步左闭右开l0, rnl rlmid1 / rmidlower_bound/upper_bound低开区间l-1, rnl1 rlmid / rmid通用找分界点极低这三个板子并不是互相矛盾的三种算法它们只是同一个数学过程的三种编码形式。关键在于选定一个之后每次写二分都用它不要这题用闭区间、那题用左闭右开最后所有边界语义在脑子里搅成一锅粥。4. 整数二分的死循环陷阱mid 取整方向的本质4.1 死循环是怎么发生的一段现场还原回到开头那个翻车案例。代码是while (l r) { int mid (l r) / 2; if (arr[mid] target) { r mid; } else { l mid; } }我们假设某一刻l 2, r 3区间里还有两个候选位置。计算mid (2 3) / 2 2mid 落在了左端点上。如果 check(2) 为 true执行r mid 2此时l r循环退出没问题。如果 check(2) 为 false执行l mid 2区间没有任何变化下一次循环还是l 2, r 3mid 还是 2check(2) 还是 false于是死循环。问题就出在“当区间长度为 2 时向下取整的 mid 永远等于左端点”。如果这时候 check(mid) 为 false要把左侧边界往右收结果却收了等于原地不动。4.2 取整方向与更新方向的配合规则要避免死循环核心原则只有一条mid 取整方向必须和“可能原地踏步的那一侧更新”相反。具体来说如果你写的是l mid左侧边界可能原地踏步那么 mid 必须向上取整也就是mid l (r - l 1) / 2。这样在区间长度为 2 时mid 会落在右端点l 至少能往前挪一步。如果你写的是r mid右侧边界可能原地踏步那么 mid 应该向下取整也就是mid l (r - l) / 2。这样区间长度为 2 时mid 落在左端点r 至少能往回挪一步。如果两边都写l mid 1和r mid - 1那 mid 取整方向无所谓因为两边都不会原地踏步。你可以把 mid 想象成天平支点支点偏左时左侧更新容易“够不着”右侧新区间支点偏右时右侧更新容易“够不着”左侧新区间。所以 l 和 r 谁有“原地保留”的可能mid 就往相反方向偏。4.3 另一个必须注意的细节溢出int mid (l r) / 2在 l 和 r 都很大的时候可能溢出。很多教材用l (r - l) / 2来避免这个问题这行代码值得养成肌肉记忆。它跟(l r) / 2在数学上完全等价但不会超过 r 的数值范围在高危场景下更安全。顺带说一句如果你用 Python 写二分(l r) // 2其实不需要担心溢出因为 Python 的整数是任意精度的。但为了代码风格统一我一般还是写成l (r - l) // 2。4.4 快速自检法两状态手推每次写完一个二分板子别急着提交先拿一个只有两个元素的输入手推一遍。比如数组[1, 3]target 分别取0, 2, 5从l 0, r 2或对应的区间形式开始手动模拟一遍看能不能正常退出。如果手推嫌麻烦就在代码里临时加一段调试输出打印每一轮的 l、r、mid、check(mid) 结果。尤其是看到某些输入下 l 和 r 连续两轮完全没变那你的取整方向大概率配错了。5. check() 函数的判别式设计从“可二分性”说起5.1 哪些问题可以用二分布尔单调性检查不是所有问题都能套二分判断标准就是前面说的“可二分性”。一个经典例子是分巧克力问题有若干块矩形巧克力要切出 k 块边长相同的正方形问正方形最大边长是多少。这个问题乍一看和“在数组里找数字”毫无关系但你可以定义check(x) “当正方形边长为 x 时能不能切出至少 k 块”。显然x 越小每块切出来的数量越多check 越容易为 truex 越大每块切出来的数量越少check 越容易为 false。于是布尔序列是true true ... true false false ... false的形状二分找“最后一个 true”就是最大边长。把原问题转化为“随某个参数单调变化的判定问题”这是二分答案类题目的核心。check() 函数在这里不是判断数组某个位置而是判断一个候选答案是否可行。5.2 设计 check() 的三个原则第一个原则判别式要清晰边界包含关系要明确。比如判定条件是 target还是 target虽然只差一个等号但找出来的位置差了一位。写之前明确你要的是“第一个满足条件”还是“最后一个满足条件”再决定等号在哪边。第二个原则check() 内部不要做高复杂度操作。二分本身只有 O(log n) 轮但每轮都要调用一次 check()如果 check() 内部是 O(n)整体就是 O(n log n)。比如分巧克力问题里check(x) 需要遍历所有巧克力统计块数这是 O(n) 的整体复杂度就是 O(n log maxLen)可接受。但如果你的 check() 里又套了一层二分或者排序复杂度可能飙到 O(n log²n)在数据量大时可能超时。第三个原则能用乘法别用除法能转整数别碰浮点。二分答案如果涉及到实数域比如求 sqrt 的近似值浮点精度和迭代次数需要额外控制。整数域的二分答案尽量保持整数运算避免把精度问题带进二分框架。5.3 处理“边界外”的情况写 check() 还有一个容易漏掉的点边界外的位置。比如要找第一个 target 的位置如果整个数组都 target那应该返回 n数组长度如果整个数组都 target应该返回 0。用左闭右开板子时这两种情况其实自动处理了全部 target 时 l 一路右移到 n全部 target 时 r 一路左移到 0。用开区间板子也一样r最终会是 n 或 0。所以我特别推荐用这两套板子它们把边界情况隐含在区间定义里不用单独写 if 去判断。5.4 check() 与二分的等价变换陷阱同一个需求check 条件可以写成好几种等价形式要小心不要变换出错。举个例子找第一个 target的位置。写成arr[mid] target然后r mid找到的是第一个满足的位置。等价地也可以找最后一个 target的位置然后 1。这时候 check 变成arr[mid] targetl mid最后返回l 1。两种写法答案一样但 mid 取整方向完全不同第一种需要向下取整第二种需要向上取整。如果你从网上抄了两种板子拼在一起极其容易写出arr[mid] target配合r mid这种“语义错位”的代码。我的建议是只记一种语义映射别在两种等价形式之间来回切换。比如我自己的习惯永远是“找第一个满足条件的位置”所有题都往这个语义上靠靠不上的再思考能不能转换成这个语义。6. 实战应用从 PTA 函数题到竞赛题的变形6.1 场景矩阵先判断你的题属于哪一类我把二分常见的应用场景整理成一张表拿到题先对号入座场景典型问题二分的对象check(mid) 的语义找的方向精确查找判断某个值是否存在数组下标arr[mid] target直接返回lower_bound找第一个 x 的位置数组下标arr[mid] x第一个 trueupper_bound找第一个 x 的位置数组下标arr[mid] x第一个 true最大值最小化将数组分成 m 段使每段和的最大值最小答案值能否用不超过 mid 的最大段和完成分段最后一个 false最小值最大化在数轴选若干点使最近距离最大答案值能否用不小于 mid 的最小距离选点最后一个 true二分答案分巧克力、切木板、装水问题答案值当前答案是否可行根据题意第六行“二分答案”是最常见的变形它的二分对象不再是数组下标而是可能的答案区间。这里我展开细讲。6.2 完整案例分巧克力问题题目大意是有 n 块长方形巧克力第 i 块尺寸为 h[i] × w[i]。要切出 k 块边长相同的正方形问正方形最大边长是多少。这是一道非常经典的二分答案入门题。写 check(x) 的思路是对每块巧克力以 x 为边长横着能切h[i] / x块竖着能切w[i] / x块每块能贡献(h[i] / x) * (w[i] / x)个正方形。把所有块数加总看是否 k。bool check(int x, const vectorint h, const vectorint w, int k) { long long cnt 0; for (int i 0; i (int)h.size(); i) { cnt (long long)(h[i] / x) * (w[i] / x); if (cnt k) return true; // 提前退出避免爆 long long } return false; }注意这里用了long long因为 h[i] 和 w[i] 可能都是 1e9 量级乘积可能超过 int 范围。这种细节在实际编码里非常重要很多人不是不会二分而是栽在乘法溢出上。二分答案部分的写法int maxSide(int n, int k, vectorint h, vectorint w) { int l 1, r 100000; // 边长的可取范围是 [1, 1e5] while (l r) { int mid l (r - l 1) / 2; // 向上取整避免死循环 if (check(mid, h, w, k)) { l mid; // mid 可行尝试更大边长 } else { r mid - 1; // mid 不可行必须缩小 } } return l; }这里我选的语义是“找最后一个可行的边长”。因为参考了上一章的规则当l mid可能原地踏步时mid 必须向上取整。所以mid l (r - l 1) / 2配合l mid和r mid - 1永远不会死循环。这和 lower_bound 模板里 mid 向下取整的理由正好对称。6.3 PTA 风格函数题的评判点热词搜索里有“二分查找 pta 函数”这确实是个经典考点。PTA 的函数题通常只要求学生实现一个查找函数比如int binary_search(int a[], int n, int x);题目给定的参数是数组、长度和目标值要求返回 x 的下标找不到返回特定的哨兵值。这种函数题考察的就是你对板子的掌握程度。我批改过不少学生的代码最常见的错误有三类一是循环条件写错导致答案差 1二是返回值写错返回了 mid 而不是 l三是在数组里存在多个相同值时没有返回题目要求的那个位置。应对这种函数题的方法很简单先把标准板子原样默写出来再根据题目要求调整 check 条件。不要现场从零推演那样太容易出错。把板子当作“语法糖”你的精力应该花在读题上——题目要的是第一个、最后一个、还是任意一个这个决定只影响 check 的一行代码。6.4 再进一步不只是数组答案本身也能二分二分思想还能推广到更抽象的领域比如在一个单调函数上找零点在浮点数域上求根在矩阵上做二维二分甚至在答案空间很大的优化问题里通过二分枚举最优解。我之前做过一个“最大值最小化”的题把长度为 n 的数组切成 m 段每段内部求和要求各段和的最大值尽量小。这种题第一眼不好下手但你给一个候选最大值 midcheck(mid) 就是“贪心地从左往右分段看能不能在每段和不超过 mid 的前提下分成不超过 m 段”。这个判定是单调的mid 越大越容易满足mid 越小越苛刻。于是二分 mid 就可以得到最小化后的最大值。这类题的核心就是你要敢把“答案本身”当作二分对象然后用 check() 去验证这个答案可不可行。这种思维方式一旦建立很多原本看起来没有头绪的优化题都会瞬间变成“一个二分 一个贪心”的套路组合。7. 把板子吃透的几条实操经验7.1 固定一套不要来回换前面给了三个板子但不是让你全记住再在考场上挑一个用。相反我强烈建议你只固定其中一套把它练到肌肉记忆。我自己长期用的是左闭右开加开区间两种闭区间只用在精确查找。对初学者我更推荐从开区间开始因为它对死循环的免疫性最强调试成本最低。你可能会担心开区间板子的l -1, r n看起来很怪但用两周就会发现它的优雅之处不需要记忆任何 1 -1 跳步只需要区分“当前 mid 染蓝还是染红”。染色逻辑和自然语言描述完全一致出错率直线下降。7.2 自己写一个对拍器背板子最大的问题是你以为自己会了但一换输入就露馅。我建议你花 20 分钟写一个对拍器一个基准实现用 STL 的std::lower_bound或暴力线性扫描另一个用你的板子然后跑随机数据对比结果。拿 Python 举个例子import random def my_lower_bound(arr, target): l, r 0, len(arr) while l r: mid l (r - l) // 2 if arr[mid] target: r mid else: l mid 1 return l # 对拍 for _ in range(10000): arr sorted(random.randint(0, 100) for _ in range(random.randint(1, 20))) target random.randint(0, 100) # 暴力版 expected len(arr) for i, v in enumerate(arr): if v target: expected i break got my_lower_bound(arr, target) if got ! expected: print(error, arr, target, expected, got) break else: print(all ok)这种对拍能一次性暴露你所有边界错误。跑 10000 组随机数据都没问题基本可以放心把这个板子用到正式代码里。7.3 调试技巧打印候选区间如果对拍出错别瞎猜直接在循环里打印l, r, mid, check(mid)的结果。看它是在第几步开始原地踏步或者在哪一步把答案区间排除掉了。二分循环最多跑 log n 次日志不会太长肉眼完全能盯过来。对二分这类“状态简单、边界致命”的算法我从来不觉得打日志丢人。恰恰相反二分是这个世界上最适合打日志调试的算法之一——它每次决策都极其清晰只要打印几行你立刻能看出自己的区间收缩逻辑哪里和预期不一致。7.4 最后分享一点个人心得二分查找的板子之所以值得反复研究不是因为算法本身难而是因为它是少数几个“一行代码错位就全盘崩溃”的基础算法。它逼你去理解不变量、理解边界、理解“判定”和“搜索”之间的转化。我自己刷了这么多年题之后回头看二分的学习过程教会我的并不是那几行循环代码而是一种下意识地思考方式面对一个难以直接求解的问题时先问自己能不能枚举可能的答案再问这个答案的可行性是否随参数单调变化如果是就直接二分它。这套思考方式的价值会远远超出二分查找本身体现在你日后处理各种优化问题、调度问题、分配问题里。哪怕你已经工作多年偶尔还是会遇到不得不手写一个二分答案的瞬间那时候你就会感谢自己当年把这个板子抠得足够细。