在算法岗面试和刷题里二分查找几乎是翻车率最高的一个思路都懂一提笔写边界就开始心里发虚写完跑一遍要么死循环要么漏答案要么返回了 -1 却找不到原因。更尴尬的是工程里也一样很多同学写二分查找是靠背模板换个题型两次一改就崩。这篇内容就是围绕一套不用去纠结 mid1、mid-1的二分查找模板展开从区间语义、循环条件、边界收缩一直讲到二分答案、对拍验证和排错技巧。不管你是刚开始学 C 二分查找的新手还是准备重新梳理 ACM 模板的老手或者只是想把这段逻辑用到业务代码里的人都能照着往下抄。这是我自己用了很多年、也反复给人讲过的一套写法全程只需要记住两个分支r mid和l mid 1。1. 二分查找为什么一看就会一写就废1.1 手写二分的三种经典翻车现场我先说几个几乎每个人都踩过的场景。第一种是死循环数组里明明没有目标值程序却卡住不退出光标一直转。第二种是漏答案目标值就在数组里程序却返回 -1。第三种是越界r mid - 1在某个时刻把下标减成了负数程序随机访问内存后表现得很诡异本机跑没事换台机器就报错。这三种问题的根因其实只有一个——你对当前区间里还剩什么这件事的定义和你写的边界收缩动作对不上。举个例子很多人初始写left 0, right n - 1循环条件写while (left right)然后在a[mid] target的时候写right mid。这三行单独看都没毛病放一起就坏了因为[left, right]是闭区间right mid意味着 mid 这个位置下一轮还会被检查而mid的计算方式又会让它在某些情况下不再变化于是循环原地打转。反过来如果初始写right n循环条件却用while (left right)那a[right]在最后一轮就越界了。这就是典型的区间定义和收缩动作不同步。记住一句话二分的正确性从来不靠运气靠的是循环不变量。每一轮循环开始时你的答案必须还留在你声明的区间里一个不能多一个不能少。所以后面我讲的所有内容本质都是在帮你维持这个不变量。一旦不变量成立边界加一还是减一就不是猜出来的而是推出来的。1.2 问题的根因区间定义和边界收缩不同步把上一条拆开看二分的边界问题可以归纳成一个两难mid这个位置到底是可能还是答案还是已经被排除。如果你认为它可能还是答案那收缩时就应该写r mid保留它如果你认为它一定不是答案那就写l mid 1排除它。麻烦在于同一个mid在找第一个大于等于 target 的位置和找 target 是否存在这两个问题里答案身份是不一样的。传统的闭区间写法[l, r]之所以难写就是因为太多人默认mid是已经被排除的于是写r mid - 1但同时又忘了l和r可能在某一轮交叉、也可能在mid 0时越界。开区间写法(l, r)也不轻松因为初始值和循环条件都得重新算一遍。真正的解法不是记住哪个加减一而是换一个区间语义让 mid 的身份在所有题型里都保持一致。这个语义就是左闭右开[l, r)后面第 2 章会详细展开。1.3 把查找统一成找第一个满足条件的元素我很早就想通一件事二分查找的所有题型本质都是同一个问题的特例——在具有单调性的序列里找第一个满足某个条件的元素。查找 target 存不存在找第一个a[i] target的位置再看a[i]是不是等于 target。找 target 第一次出现的位置同上判断相等即可。找 target 最后一次出现的位置找第一个a[i] target的位置答案就是它减一。找旋转数组最小值找第一个a[i] a[0]的位置。找峰值元素找第一个a[i] a[i1]的位置。二分答案找第一个让判定函数check(x)为真的 x。你看全部都是找第一个满足条件的。只要把这一个动作写死其余全是换条件。这就是我说不需要考虑 mid1、mid-1的底气——因为收缩逻辑只有固定的一套不需要你针对每个题型重新推。2. 左闭右开模板的核心设计与选型理由2.1 区间语义为什么用 [l, r) 而不是 [l, r]先说结论这套模板的骨架是int l 0, r n; // 区间为 [l, r)注意 r 是 n不是 n-1 while (l r) { int mid l (r - l) / 2; if (满足条件(a[mid])) r mid; // mid 可能是答案保留 else l mid 1; // mid 一定不是答案排除 } return l; // 第一个满足条件的位置也可能是 n为什么选[l, r)因为它有几个非常舒服的性质。第一初始r n天然表示一个越界哨兵不需要为找不到单独写返回 -1 的逻辑。第二区间长度永远是r - l循环终止时l r这时候 l 恰好就是答案位置。第三也是最重要的一点因为右端点是开区间r mid这个操作永远不会让右边界为负因为进入循环时一定满足l r于是mid l 0把r收缩到mid是安全的。反过来看闭区间[l, r]r mid - 1在mid 0时会让r变成 -1虽然大多数情况下mid 0意味着l也是 0循环本身也会结束但这种靠巧合安全的写法在变体里非常容易出事尤其是找最后一个大于等于这类需要反向收缩的题。左闭右开从语义上就规避了这个问题这是它比闭区间更稳的根本原因。2.2 循环条件为什么是 l r 而不是 l r[l, r)的长度是r - l。当l r时区间长度为零说明候选集合为空继续循环没有意义所以条件是while (l r)。这里有个容易混淆的点如果误以为[l, r]是闭区间就会写成while (l r)那样当l r时区间还有最后一个元素a[l]看起来合理但在[l, r)语义下a[r]是越界的最后一轮直接读越界内存。所以不是l r错了而是它和你的区间语义不匹配。我给你一个判断准则循环条件只需要问一句当 l r 时我的区间里还有元素吗。左闭右开下答案是没有所以用闭区间下答案是还有一个所以用。把这句话记住你永远不会写错循环条件。2.3 为什么只写 r mid不写 mid - 1这是整套模板的灵魂值得单独拎出来说。我们要找的是第一个满足条件的元素请考虑a[mid]满足条件的情况。此时mid本身可能就是最终答案也可能不是如果它左边还有满足条件的元素的话。无论哪种情况答案的位置一定不会超过 mid所以新的右边界应该收缩到 mid。如果你写r mid - 1就等于武断地宣布 mid 不是答案那当 mid 恰好就是第一个满足条件的元素时你就把它排除掉了答案丢失。那么问题来了r mid会不会导致死循环不会。因为mid的计算是下取整mid l (r - l) / 2当l r时必有l mid r。也就是说mid严格小于rr被赋值为mid后严格变小区间长度r - l严格缩短循环必然收敛。这正是下取整配r mid、上取整配l mid的搭配讲究下面 2.4 还会细说。再看a[mid]不满足条件的情况。由于序列有单调性a[mid]不满足意味着 mid 及其左侧所有元素都不满足所以左边界可以直接推到mid 1。这里的1是必须的——如果你写成l mid那么mid不再变化l和r会永远卡住直接死循环。所以你看到了整套逻辑里只有一个1而且它的位置是固定的、唯一的、不需要思考的满足条件动右边界不满足条件动左边界并加一。这就是不需要考虑 mid1、mid-1的真实含义——不是真的一次加减一都不写而是你不需要针对题型去纠结该加一还是减一规则永远只有这一条。2.4 mid 的计算l (r - l) / 2 与溢出先纠正一个非常常见的写法不要写mid (l r) / 2。当l和r都是接近INT_MAX的大整数时l r会发生有符号整数溢出结果变成负数mid就成了一个非法下标。业务代码里数组长度一般不会那么大但在竞赛题、OJ 题和大数据处理里这个坑是真实存在的。正确写法是int mid l (r - l) / 2;先算差值再折半加法结果一定不超过r不会溢出。这个写法还有个好处无论l、r正负mid都落在[l, r)内。再强调一次取整方向。(r - l) / 2是向下取整所以mid偏向l。这个方向的直接后果是mid一定小于r适合做r mid。如果你在做最大化答案的题时需要反向收缩l mid就必须把mid改成向上取整l (r - l 1) / 2否则mid永远停在l也会死循环。这一对搭配我在第 4 章会给出规避方案让你连上取整都不用记。2.5 返回值为什么是 l循环结束时l r这个位置就是第一个满足条件的位置。为什么因为我们全程维护了一个不变量答案永远落在[l, r)内。r mid时mid 仍被包含l mid 1时被排除的都是确定不满足的。等区间收缩到空唯一没被排除过的位置就剩下了l。这个返回值的妙处在于它天然处理了找不到的情况。比如数组是[1, 3, 5]你要找第一个大于等于 4 的位置二分结束会返回 2指向 5你要找第一个大于等于 9 的位置会返回 3也就是n一个越界哨兵。调用方只要一句if (pos n a[pos] target)就能安全判断存在性不需要额外写返回 -1 的分支也不会把 -1 混进下标运算里。提示把找不到编码成n而不是 -1是这套模板最实用的设计之一。它让你所有后续判断都能用统一的下标写法减少一半的边界讨论。3. 一套模板打穿四种二分题型3.1 查找目标值是否存在这是最基础的场景。注意同一个模板可以覆盖两种常见需求而且这两种需求的返回语义差别很大一定要分清楚。第一种需求是告诉我存不存在看代码bool contains(const vectorint a, int target) { int l 0, r a.size(); while (l r) { int mid l (r - l) / 2; if (a[mid] target) r mid; else l mid 1; } return l (int)a.size() a[l] target; }第二种需求是告诉我下标把位置返回出去。注意如果l n表示所有元素都小于 target调用方需要自己判空。我个人的习惯是统一返回l让调用方去判断而不是在函数内部纠结该返回 -1 还是 n因为 -1 一旦参与下标运算就是隐患。这里有个性能上的细节同样是O(log n)这套写法的分支预测比较友好因为两个分支的收缩动作不同但都不复杂实测在大数组上比手写递归版本稳定。当然真正快的是std::lower_bound和std::upper_bound工程代码里优先用标准库只有在需要自定义条件或者参加竞赛时手写才更合适。3.2 第一个大于等于 target 的位置lower_bound这其实就是 3.1 的主体部分我在这里把它正式命名一下因为后面所有题型都是它的变体// 返回第一个满足 a[i] target 的下标不存在返回 n int lowerBound(const vectorint a, int target) { int l 0, r a.size(); while (l r) { int mid l (r - l) / 2; if (a[mid] target) r mid; else l mid 1; } return l; }使用前必须确认一件事数组是升序的。如果数组是降序你只需要把条件反过来或者把整个数组的逻辑镜像一下比如把a[mid] target改成a[mid] target。降序数组里第一个小于等于 target 的位置就对应升序里的 lower_bound这个对应关系在很多题解里被写成复杂的分类讨论其实完全没必要。另外提醒一句当数组里有重复元素时lower_bound 返回的是最左边那个。如果你要的是最右边看下一节。3.3 最后一个小于等于 target 的位置这个需求在业务里非常常见比如找到最后一个不超过预算的方案找到最后一个不晚于截止时间的记录。以升序数组为例最后一个小于等于 target 的元素其实就是第一个大于 target 的位置减一int lastLE(const vectorint a, int target) { int l 0, r a.size(); while (l r) { int mid l (r - l) / 2; if (a[mid] target) r mid; else l mid 1; } return l - 1; // 可能为 -1表示所有元素都大于 target }注意这里返回l - 1可能得到 -1。这不是 bug而是语义本身决定的如果所有元素都大于 target那么最后一个小于等于根本不存在用 -1 表示是合理的。但调用方必须在做下标访问前判断if (pos 0)这是这套返回约定里唯一需要额外小心的地方。注意pos n和pos -1是两种不同的找不到。前者表示目标值比所有元素都大后者表示比所有元素都小。很多同学在业务里只处理了一种另一种直接数组越界。3.4 第一个大于 target 的位置upper_bound标准库的upper_bound返回第一个严格大于 target 的位置。实现上和 lower_bound 只差一个符号int upperBound(const vectorint a, int target) { int l 0, r a.size(); while (l r) { int mid l (r - l) / 2; if (a[mid] target) r mid; // 只把 改成 else l mid 1; } return l; }这一点值得反复强调lower_bound 和 upper_bound 的区别只有条件里的等号结构一模一样连r mid都不用改。这就是统一模板带来的红利。你如果还在为upper_bound 要不要写 mid1纠结说明还在用碎片化的记忆方式。顺带说个实用组合区间内等于 target 的元素个数等于upper_bound(a, target) - lower_bound(a, target)。这个公式在统计类题目里出场率极高建议直接记住不要每次重新推。3.5 旋转数组、峰值、缺失数字等变体怎么套变体题最大的诱惑是让你重新写边界但正确做法恰恰相反只改条件不动骨架。举几个例子。旋转数组找最小值假设是升序数组旋转而来把条件写成a[mid]是否小于最后一个元素因为最小值一定在比尾部元素小的那一段里。代码里条件就是这个比较r mid或l mid 1照旧。找峰值元素比较a[mid]和a[mid1]。如果a[mid] a[mid1]说明已经在下降段峰值在 mid 或它左边r mid否则l mid 1。你看仍然是这一个判断只是条件换成了比较。找缺失数字、找第一个坏版本这类题同理。我在 ACM 模板里给这种情况起了个名字叫换条件不换骨架这也是为什么很多人的二分模板在竞赛里从来不出错——因为骨架只有一套改的永远是那一行if。题型条件写法返回值第一个 targeta[mid] targetl可能为 n第一个 targeta[mid] targetl可能为 n最后一个 targeta[mid] target取反l-1可能为 -1旋转数组最小值a[mid] a[n-1]之类的单调性条件l峰值a[mid] a[mid1]l4. 二分答案把求解最值变成判定可行性4.1 二分答案的适用条件单调性判定函数二分答案听起来玄乎本质就是一句话如果某个解可行那么比它更宽松的解也可行于是可行与不可行之间有一条清晰的分界线而我们要找的就是这条分界线上的那个最值。典型的题型有最小化最大值比如把数组分成 k 段让每段和的最大值最小和最大化最小值比如在若干位置里选点让最近两点距离最大。这两类题的共同特征是直接求出答案很难但给定一个猜测值 x判断x 这个方案行不行很容易。这把求最优降维成了判可行而判可行是单调的二分就派上用场了。判定函数check(x)的单调性可以从两个方向看如果 x 越大越容易满足那可行区间就是[ans, inf)我们找的是第一个满足的位置如果 x 越小越容易满足那可行区间是(-inf, ans]我们找的是最后一个满足的位置。这两种正好对应下面两节。4.2 判定函数的写法与check要点写check有几个反复被踩的点我列出来提醒一下。第一check里不要用浮点做中间计算能用整数就整数避免精度导致的边界抖动。第二check的时间复杂度乘以二分次数才是总复杂度如果你写了个O(n^2)的 check整体就退化了能用贪心就用贪心。第三也是最容易错的check必须严格满足单调性且边界值要单独验证。很多题的 check 在极端输入下x 非常小或者非常大会返回错误结果而这个错误直接导致二分区间收敛到错误的位置。提示写完 check 之后先用暴力枚举小数据把所有 x 的 check 结果打出来看它是不是一个先假后真或者先真后假的序列中间只要有反复横跳二分必错。4.3 整数二分的两种终点找最小 / 找最大前面说过一个麻烦找最后一个满足的时候传统写法要上取整容易出错。我在这套模板里给了一个统一办法——不去找最后一个满足的而是去找第一个不满足的然后减一。这样全程只用下取整、只用r mid和l mid 1。找最小可行值check 随 x 增大越来越容易满足int l lo, r hi 1; // 注意 r 取 hi1形成 [lo, hi1) while (l r) { int mid l (r - l) / 2; if (check(mid)) r mid; else l mid 1; } return l; // 第一个可行的 x找最大可行值check 随 x 增大越来越难满足int l lo, r hi 1; // 在 [lo, hi1) 里找第一个不可行的位置 while (l r) { int mid l (r - l) / 2; if (!check(mid)) r mid; // 不满足就是我们要找的分界 else l mid 1; } return l - 1; // 分界前一个位置就是最大可行值看到没有第二段是找最大但我全程没有出现mid - 1只有最后返回时减了一次。这和标题说的不需要考虑 mid1、mid-1完全一致——因为加减一被固定在了两个不会思考的位置循环里的l mid 1和返回时的l - 1。中间那一段最容易出错、最需要推导的收缩逻辑被彻底消除了。注意hi 1这个哨兵必须在值域安全范围内。如果hi是INT_MAX加一会溢出这时候要么改用更小的值域边界要么用 long long 承接。4.4 浮点二分与迭代次数控制浮点二分没有加减一的烦恼但换了另一种坑精度。很多人写while (r - l 1e-8)结果在某些数据规模下因为浮点误差卡住或者多跑几百轮甚至出现l和r的差值因为精度极限而永远大于阈值的情况。我的做法是干脆放弃用差值判断改成固定迭代次数double l lo, r hi; for (int i 0; i 100; i) { double mid (l r) / 2; if (check(mid)) r mid; else l mid; } return l;每迭代一次区间减半100 次之后区间长度是初始的2^-100倍对double来说早就到精度极限了多迭代几次也没意义所以 100 次完全可以放心。这个写法的好处是循环次数确定、不会卡死、调试时容易估计。如果题目要求精度 1e-6迭代 60 次就绰绰有余2^-60 约等于 8.7e-19。5. 常见问题与排查技巧实录5.1 死循环速查表死循环是二分最让人抓狂的问题因为程序不崩、没报错就是不出来。我把常见成因整理成表遇到卡住时从上往下对照。现象可能原因修复一直不退出l mid而不是l mid 1不满足条件时改成mid 1一直不退出用了上取整的 mid 却配r mid下取整配r mid上取整配l mid一直不退出循环条件写成l r但区间是左闭右开改成l r循环早退区间初值写成r n - 1左闭右开应写r n结果偏小一格返回时漏了语义偏移检查返回l还是l - 1排查方法很简单在循环里打印l、r、mid三个值看哪一轮开始l和r不再变化。只要出现mid r或者mid l就说明取整方向和收缩动作不匹配对号入座即可。5.2 边界越界与返回 -1 的坑越界的来源主要有三个。第一个是初始r n - 1配左闭右开语义导致最后一个元素永远取不到。第二个是返回l - 1之后没判断负数就用来访问数组。第三个是mid用(l r) / 2在大数下溢出成负数下标。这三个我在前面都提过对应的修法。关于返回 -1 这个坑我想多说一句使用习惯。我见过太多代码写成找不到就返回 -1然后调用方直接a[result]这里如果没判断在所有元素都大于目标值时就会访问a[-1]而且这类 bug 在小数据测试里往往不出现上线后遇到特定输入才炸。所以我的建议是二分函数尽量不返回 -1返回位置加一个越界判断把是否存在的判断权交给调用方。这不是洁癖是真实线上事故教出来的习惯。注意当你要判断的数组是vector时a.size()是size_t无符号类型和int比较会产生隐式转换警告。稳妥写法是int n (int)a.size();之后再用 n。5.3 重复元素、数据范围、long long 溢出有重复元素时二分的每一个位置都可能有多个正确答案这时候必须明确你要的是最左还是最右。lower_bound 给最左upper_bound 减一给最右用错了就是结果看起来对但又不太对很难查。建议在函数命名上就写清楚语义比如firstGE、lastLE别都用binarySearch。数据范围方面要注意的是值域二分。当hi接近10^18时l (r - l) / 2里的加法虽然安全但hi 1这个哨兵可能溢出int必须用long long。我在竞赛里养成的习惯是只要二分是在值域上做的一律用long long承接宁可浪费一点也绝不留溢出隐患。还有一个隐蔽问题是判定函数内部也可能溢出。比如 check 里做累加求和如果数组元素和会超过int范围二分本身没问题但 check 给出的结论就是错的最终表现是二分收敛到看起来合理但其实错误的位置。这类问题必须靠 data 范围的估算提前拦下而不是靠调试。5.4 调试方法小数据暴力对拍想把二分写对光靠肉眼检查容易漏。最有效的办法是对拍写一个暴力实现在极小数据上随机生成测试用例把两者结果比一遍。以第一个大于等于 target 的位置为例暴力实现就是从头扫一遍int bruteFirstGE(const vectorint a, int target) { for (int i 0; i (int)a.size(); i) { if (a[i] target) return i; } return a.size(); }对拍脚本我一般用 Python 写生成随机数组和随机查询import random for _ in range(2000): n random.randint(1, 8) a sorted(random.randint(0, 5) for _ in range(n)) t random.randint(-1, 6) expect next((i for i, v in enumerate(a) if v t), n) # 把 a、t、expect 喂给你的二分实现比较结果关键在于要让数据小、密、有重复因为边界 bug 大多出现在长度为 1、全相等、目标值比所有元素都小或都大这几种极端情况上。我做过的对拍里超过一半的 bug 都是被数组只有一个元素这种用例抓出来的。6. 实战复现从零手写并验证模板6.1 代码实现把前面所有内容收拢成一份可以直接粘进项目的 C 实现。我加上了详细注释方便你日后回看时不用重新推#include vector using namespace std; // 在升序数组 a 中返回第一个满足 a[i] target 的下标 // 不存在则返回 n越界哨兵 // 前置条件a 升序允许重复元素 int firstGE(const vectorint a, int target) { int n (int)a.size(); int l 0, r n; // 区间 [l, r) while (l r) { int mid l (r - l) / 2; // 下取整防溢出 if (a[mid] target) { r mid; // mid 可能是答案保留 } else { l mid 1; // mid 确定不是答案排除 } } return l; // l r即第一个满足条件的位置 } // 返回最后一个满足 a[i] target 的下标不存在返回 -1 int lastLE(const vectorint a, int target) { int n (int)a.size(); int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] target) r mid; // 找第一个 target 的位置 else l mid 1; } return l - 1; // 它的前一个就是最后一个 target }Python 版本逻辑完全一致只把溢出防护去掉Python 整数天然不溢出可以拿来快速验证思路def first_ge(a, target): l, r 0, len(a) # [l, r) while l r: mid l (r - l) // 2 if a[mid] target: r mid else: l mid 1 return l这两份代码的结构完全对得上你换成 Java 或者其他语言时只要保证三件事不变区间左闭右开、循环条件l r、收缩规则是r mid或l mid 1就不会出错。6.2 测试用例设计写完之后我通常用下面这组用例手工过一遍覆盖的都是容易翻车的边界空数组a []任何 target 都应返回 0等于 n。这套模板天然支持因为初始l r 0循环一次都不进直接返回 0。单元素命中a [5]找 5返回 0。单元素未命中偏小a [5]找 3返回 1。单元素未命中偏大a [5]找 9返回 1。全相等重复a [2, 2, 2, 2]找 2返回 0找 3返回 4。目标值恰好等于首元素、尾元素。目标值比所有元素小、比所有元素大。把这些用例在纸上推一遍尤其是空数组和全相等这两种基本就能确认模板是对的。很多同学不做这一步结果在真实题目里遇到目标值比所有元素都大就直接越界。6.3 对拍脚本手工用例之外我建议跑一次完整对拍。思路是同一个输入同时喂给二分实现和暴力实现比较结果import random def brute_first_ge(a, target): for i, v in enumerate(a): if v target: return i return len(a) ok True for _ in range(5000): n random.randint(0, 12) a sorted(random.randint(0, 6) for _ in range(n)) t random.randint(-2, 8) got first_ge(a, t) want brute_first_ge(a, t) if got ! want: print(MISMATCH, a, t, got, want) ok False break print(ALL PASS if ok else FAILED)注意这里我故意把数据范围设得很小值 0 到 6长度 0 到 12因为小范围内的重复和边界组合最密集能以很小的样本量覆盖最常见的错误。跑了 5000 组全通过我对这份实现的信任度就很高了可以直接拿去写题或者放进工具函数里。7. 一些用久了的个人体会这套写法我用了很多年最大的感受是二分的难点从来不在算法本身而在你能不能把一件事说清楚。当你能明确说出我在维护一个左闭右开的区间里面始终包含第一个满足条件的元素那些加减一的纠结就自动消失了因为每一步收缩都是被不变量推出来的不是背出来的。关于 mid-1最后再补一个我个人特别喜欢的技巧。当你需要在任何题型里避免反向收缩时可以给右端点补一个哨兵把找最后一个满足统一转换成找第一个不满足再减一。这个转换看起来只是符号游戏实际效果是把所有需要上取整、需要写mid - 1的地方全部消灭掉了。我带的几个刚学算法的人改用了这个思路之后写二分就没再死循环过。如果你现在还是习惯闭区间写法也不用立刻全盘推翻。可以先挑一个下午拿这份模板把第一个大于等于最后一个小于等于最小值最大化最大值最小化这四类题各刷两道体会一下同一骨架换条件的感觉。等你发现改一行if就能覆盖一道新题的时候大概就不会再想回去纠结边界了。8. 关于这份模板的扩展与注意事项这套模板还可以继续往下扩展。比如在二维矩阵里做二分本质是把行或列当成有序数组条件换成这一行是否包含大于等于目标的值再比如用二分配合离散化把稀疏的大值域问题映射到紧凑下标上这套结构同样适用只是 check 或者说条件函数要多包一层映射。不过有几个坑是无论怎么扩展都要守住的。第一单调性必须在写代码之前就用逻辑证明一遍不能靠感觉是单调的。第二check 函数要单独测试尤其是边界输入别让它和二分互相污染错误。第三值域上界的哨兵值要留够空间宁可用 long long 也别抠那点内存。第四任何返回位置的地方调用前都判断一下是否越界pos n或者pos 0这半行代码能省掉你一整晚的调试。写到这里这份模板能覆盖的场景基本就说完了。剩下的就是动手找一个你之前写崩过的二分题用这套骨架重写一遍再拿第 6 章的用例过一遍。你会发现那种每次写二分都要深呼吸一下的感觉慢慢就没了。