企业官网建设流程全解析

我早年学二分查找，吃过不少亏。最开始的写法是背下来的while (left <= right)，遇到"第一个大于等于 x 的位置"这类题，就得当场推演 mid 到底该不该加一，推完还得拿几组边界数据手算验证，一次写对全靠运气。后来换成左闭右开[left, right)，边界情况少了一半，可脑子里还得挂着一句咒语：右边是开区间上界，赋值时不能减一。真正让我彻底扔掉 mid+1、mid-1 这两根拐杖的，是开区间写法配合红蓝染色模型——把二分从"在数组里找数字"重新理解成"给格子染色、找分界线"，你会发现代码里再也没有加减一的位置，模板短到可以背下来，而且四类常见的边界需求全都套同一套骨架。这篇就把这套二分查找模板从思路到代码、从原理到题单，完整地拆一遍，C++ 和 Python 都会给，零基础也能跟得上。

1. 二分查找真正的难点从来不是"找没找到"，而是边界怎么写

二分查找的思想一句话就能讲完：每次把搜索范围砍掉一半。可为什么这么简单的思想，能在各种题库里制造出大量的错误提交？原因几乎从来不在于"我没有理解二分"，而在于边界收缩规则和区间语义不匹配。你脑子里的模型和代码里的变量根本不是一回事，于是写出来的东西在某些输入上恰好对，在另一些输入上就开始表演。

1.1 传统写法的三种典型死法

先看最常见的闭区间写法：

int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (a[mid] == target) return mid; else if (a[mid] < target) l = mid + 1; else r = mid - 1; } return -1;

这段代码本身没问题，但它有一个隐形约束：l和r表示的是"还可能包含答案的闭区间"。所以当你判定a[mid] < target时，mid这个位置已经被排除，必须跳到mid + 1。一旦你想把return mid改成别的返回逻辑，比如"找最后一个小于等于 target 的位置"，加减一的关系立刻变得模糊。

第一种死法：死循环。典型症状是把l = mid + 1写成l = mid，同时循环条件还是l <= r。当r == l + 1时，mid == l，如果判定成立又不推进l，区间长度永远不变，程序卡死。这类 bug 在本地小数据上跑不出来，一交上去就超时。

第二种死法：漏答案或错一位。想找"第一个大于等于 x 的位置"，很多人会写成l <= r配合r = mid，结果区间在某一刻变成l == r == 答案，但循环条件不允许退出，或者退出后的返回值取错了端点，最终差一位。差一位是二分查找最经典的故障。

第三种死法：越界。r = mid - 1在mid == 0时会把r变成-1，如果后面还拿r当数组下标用（比如a[r]）就直接段错误。闭区间写法下所有"减一"的地方都是潜在的负下标来源。

三种死法看起来是三个问题，本质是同一个问题：用具体的加减一运算去维护一个语义模糊的区间。

1.2 把区间语义写在纸上：不变量才是模板的骨架

我后来强迫自己养成一个习惯：写二分之前，先在纸上写两句话，一句描述left的含义，一句描述right的含义，这两句话必须在整个循环过程中永远成立。这就是循环不变量。

举个具体例子。我要在升序数组里找第一个大于等于 x 的位置，那么我可以约定：

• left始终指向一个"确定小于 x"的位置；
• right始终指向一个"确定大于等于 x"的位置。

这个约定一旦定死，代码的每一行都必须维护它：判定mid位置的元素小于 x，说明mid可以安全地充当新的left；判定mid位置的元素大于等于 x，说明mid可以安全地充当新的right。注意这里的关键——我直接把 mid 赋值给 left 或 right，没有加减一，因为我要的语义是"这个位置确定是哪一类"，而不是"排除这个位置"。

那么问题来了：left一开始指向哪里？答案是-1，因为没有任何真实元素能保证"确定小于 x"。同理right一开始是n。这就是开区间模板的全部秘密来源：把两个哨兵放到数组外面，让"确定"这个词在数学上永远成立。

下面我把三种主流写法的差别列成表，你可以对照看看自己平时用的是哪一种：

从表里能看出一条很清晰的演化路线：区间的开闭程度越高，需要手动维护边界的次数就越少。开区间写法之所以能做到零加减一，是因为它把"排除"这件事交给了区间本身的语义——(left, right)天然不包含left和right，所以把mid赋给它们之后，mid自动被排除，不需要你再去加一减一。

另外说一句，左右端点的命名习惯上，right有时候会写成r或者hi，我建议统一用left/right，因为在二分答案的题里还会出现lo/hi，两套命名混在一起很容易看错。

2. 开区间模板：先把两个指针放到数组外面

前面把道理讲完了，现在看代码。这套模板我最推荐的做法是把它抽成一个高阶函数，把"每次判断什么"单独做成一个回调，因为二分查找最常变的部分就是判断条件本身，而骨架永远不变。

2.1 为什么初始值是 -1 和 n

很多人第一次看到left = -1, right = n会本能地紧张：这不是越界了吗？会不会访问到数组外面？

不会，因为这两个值只会作为边界存在，永远不会被当成下标去访问数组。left和right在循环里只承担两件事：参与区间长度计算、在边界判定中被赋值。真正被访问的下标只有mid，而mid永远是left和right之间（不含端点）的整数，必然落在[0, n-1]里。

我用长度算术验证一下。设L = right - left。循环能进去的条件是L >= 2。取mid = left + (right - left) / 2（整除，向下取整）：

• 因为L >= 2，所以(right - left) / 2 >= 1，得mid >= left + 1；
• 又因为(right - left) / 2 <= (right - left) - 1（当L >= 2时成立），得mid <= right - 1。

所以left < mid < right，mid严格在开区间内部。这就保证了无论怎么赋值，访问a[mid]都是安全的，而且区间每次至少缩短一个格点，不可能出现死循环。这个结论值得亲手推一遍，推完你就不会再担心越界了。

顺带说一个 C++ 的细节：我写mid = left + (right - left) / 2而不是(left + right) / 2。虽然在这个模板里left从-1开始、right最多是n，两个数相加一般不会溢出 32 位整数，但养成用差值形式的习惯没坏处，因为一旦你把这套模板迁移到二分答案（数值范围动辄 1e18），left + right就真的会炸。

2.2 循环条件 left + 1 < right 到底在保证什么

while (left + 1 < right)这句话翻译成人话是：当left和right之间还存在至少一个格点时，继续探索。

对比一下闭区间写法的while (left <= right)：它保证的是"区间内还有元素"。两种条件的差别在于，开区间写法允许left和right相邻（right == left + 1）时退出循环。而循环退出那一刻，根据我们的不变量，left是最后一个"红色"，right是第一个"蓝色"，它们恰好是分界线两侧的邻居——这正是我们要的答案。

这个设计的精妙之处在于：退出条件本身就是答案的形态。你不需要在循环外面再写一堆if去判断"是不是没找到""要不要返回 -1""如果全部满足怎么办"。所有这些情况都已经被"最后一个红色和第一个蓝色相邻"这一句话涵盖了，你只需要在最后检查一下right是否等于n（表示整个数组都不满足），就可以应对所有边界。

2.3 完整模板与逐行拆解

先看 C++ 版本，我把它写成一个模板函数，因为泛型能让它同时服务整数下标和long long数值：

// 返回最小的满足 check(i) 为真的下标 i // 前提：check 在 [0, n) 上单调，即存在分界点 p // i < p 时 check(i) 为假，i >= p 时 check(i) 为真 // 若不存在满足 check 的下标，返回 n template <typename F> int firstTrue(int n, F check) { int left = -1, right = n; // 不变量：left 是"假"，right 是"真" while (left + 1 < right) { // 区间 (left, right) 内还有未判定的格点 int mid = left + (right - left) / 2; if (check(mid)) { right = mid; // mid 是真，作为新的右哨兵 } else { left = mid; // mid 是假，作为新的左哨兵 } } return right; // 分界线 }

Python 版本更短，因为不用操心类型：

def first_true(n: int, check) -> int: """返回最小的满足 check(i) 的下标 i；若都不满足则返回 n""" left, right = -1, n while left + 1 < right: mid = (left + right) // 2 if check(mid): right = mid else: left = mid return right

逐行拆一下：

• left = -1, right = n：两个虚拟哨兵。-1位置上"一定不满足"，n位置上"一定满足"。这两个位置是虚构的，check永远不会在它们上面被调用。
• while (left + 1 < right)：只要两个哨兵还没贴在一起就继续。
• mid = left + (right - left) / 2：取中间位置，向下取整。用差值形式防溢出。
• if (check(mid)) right = mid;：mid是"真"，说明分界线在mid或者更左，把右哨兵拉过来。注意——mid本身可能是答案，所以不能写成mid - 1，这就是模板不需要减一的根本原因。
• else left = mid;：mid是"假"，说明分界线在mid右边，把左哨兵推过去。注意——mid一定不是答案，所以不能写成mid + 1吗？其实写成mid + 1也不会错（因为你要找的答案不在mid），但那是一个额外的信息，而这个模板选择不使用它。统一用left = mid让两条分支在形式上对称，减少记忆负担。
• return right：函数名firstTrue已经说明了一切，返回第一个满足条件的位置。返回n意味着无解。

再写两个使用示例，让你看出"四类需求套一个骨架"是怎么回事：

// 第一个 >= x 的位置 int lowerBound(const std::vector<int>& a, int x) { return firstTrue((int)a.size(), [&](int i) { return a[i] >= x; }); } // 第一个 > x 的位置 int upperBound(const std::vector<int>& a, int x) { return firstTrue((int)a.size(), [&](int i) { return a[i] > x; }); }

lowerBound和upperBound的差别只有 lambda 里的一个等号。你不再是"写两套边界逻辑"，而是"改一个判断条件"。这个转变听起来不起眼，但它把二分查找从一个需要反复调试的算法，变成了一个几乎不可能写错的工具——因为骨架已经被验证过无数遍了，你唯一可能错的地方只剩下check写得对不对。

3. 红蓝染色法：把"查找"翻译成"找分界线"

模板会写了，但很多人的下一个疑问是：我怎么知道check该写什么？什么时候该>=，什么时候该>？这里我推荐用染色模型来思考，它能把抽象的"第一个满足条件的"变成一张可视化的图。

3.1 每个下标只有两种颜色，分界线唯一

想象数组a的每个下标位置都是一块还没上色的空白格子。规则是：满足check的格子染成蓝色，不满足的格子染成红色。由于check具有单调性，染完之后整排格子的样子必然是"左边一片红、右边一片蓝"，中间有一条分界线。

二分查找在干什么？它每次挑一个格子，问一句check(mid)，然后立刻知道这个格子的颜色，并且顺带确定它左侧或右侧一大片的颜色：如果mid是蓝色，由于单调性，mid右边全是蓝色；如果mid是红色，mid左边全是红色。于是每次询问都能把一片格子染好色，这就是"砍掉一半"的真正含义。

用这个视角看开区间模板，left就是"我已知的最后一个红色"，right就是"我已知的第一个蓝色"，中间那些还没染色的格子构成开区间(left, right)。循环结束时中间没有待染色的格子了，right就是分界线，一切顺理成章。

3.2 四类需求转成同一个 check

题目里常见四种问法，全都可以用同一套骨架解决：

• 问：第一个>= x的位置。染色规则：a[i] >= x染蓝。
• 问：第一个> x的位置。染色规则：a[i] > x染蓝。
• 问：最后一个< x的位置。不被单独处理，而是先求第一个>= x的位置，再减一。
• 问：最后一个<= x的位置。同样不单独处理，先求第一个> x的位置，再减一。

后两类是这套模板最舒服的地方。传统写法里，"求最后一个小于 x 的位置"和"求第一个大于等于 x 的位置"是两套需要分别推边界的逻辑；而在染色模型里，它们只是同一个分界线的两种读法——分界线左边是红色区，红色区的最后一个位置当然就是"最后一个不满足 check 的位置"。

再加上"计数"这个用法：小于 x 的元素个数，等于第一个>= x的位置（因为下标从 0 开始）。这个恒等式在写题解时经常能省掉一个循环。

我把映射关系整理成表，方便你贴在代码注释里：

3.3 关于单调性，一句必须记住的警告

染色模型成立的前提是单调性：存在一个分界点，左边全红、右边全蓝。如果数组里check的结果是"红蓝红蓝"交替的，那二分彻底失效，返回什么都有可能。

这也是为什么二分需要"有序数组"——有序保证了a[i] >= x这种条件的单调性。但反过来，二分需要的并不是数组有序，而是你的check单调。这个认识上的转变非常重要，因为它直接打开了二分答案的大门：二分答案的搜索空间是一堆候选数值，从"数值大小"本身看不出有序无序，但check关于数值是单调的，照样能二分。

提示：每次写check之前，先在心里过一遍"如果check(mid)为真，那么mid + 1也一定为真吗"。答不上来就别写二分，先去想别的算法。

4. 二分答案：这套模板真正值钱的地方

如果说在有序数组里查找只是二分的入门用法，那二分答案才是它的主战场。我在实际做题时，二分答案的出现频率远高于普通查找，而开区间模板在二分答案里的优势比在数组查找里还要明显，因为二分答案的答案范围经常是1e9甚至1e18级别的，边界少写一个加减一，影响的就是完全不同的量级。

4.1 从"查找数组"到"查找答案"，中间隔着单调性

二分答案的思考流程是这样的：

1. 先想清楚答案是一个什么数值，它的取值范围是什么（下界lo，上界hi）。
2. 写一个判定函数check(x)，含义是"答案为x时是否可行"，或者更常用的是"答案不超过x是否可行"。
3. 验证check关于x是否单调。
4. 用开区间模板二分。

第二步的两种写法值得展开讲。有的题适合写"答案 <= x 是否可行"，此时check是关于x单调递增的真值序列（x越大越容易满足），染出来是"左边红右边蓝"，直接套模板返回第一个蓝色的x。有的题适合写"答案 >= x 是否可行"，此时真值序列是单调递减的（x越小越容易满足），染出来是"左边蓝右边红"，需要把区间反过来或者把条件取反。

我个人的习惯是永远统一成"左边红右边蓝"，也就是坚持写"x可行吗"且让x越大越可行。如果题目天然是反的，我就在心里做一次镜像转换，或者干脆把check取反。这样做的好处是双指针同向，left = mid/right = mid这套写法不用改。

4.2 两道例题的 check 推导

例一：完成旅途的最少时间（类 2187）。有n辆车，第i辆每趟耗时time[i]，问至少多少时间能完成totalTrips趟。

答案显然是一个时间值。下界是1（至少得跑一趟），上界可以用"全部用最快的那辆车"来估：min(time) * totalTrips。check(t)的含义是"时间t内能完成的总趟数是否不少于totalTrips"，总趟数等于Σ floor(t / time[i])。t越大，每一辆车能跑的趟数越多，总趟数越大，单调性成立。

long long minimumTime(std::vector<int>& time, int totalTrips) { long long lo = 1; long long fastest = *std::min_element(time.begin(), time.end()); long long hi = fastest * (long long)totalTrips; // 一定可行 long long left = lo - 1, right = hi + 1; // 开区间 while (left + 1 < right) { long long mid = left + (right - left) / 2; long long trips = 0; for (int t : time) { trips += mid / t; if (trips >= totalTrips) break; // 防止累加溢出 } if (trips >= totalTrips) right = mid; else left = mid; } return right; }

这段代码里有三个细节值得说。第一，lo = 1是答案下界，所以虚拟左哨兵取lo - 1 = 0；hi是保证可行的上界，所以虚拟右哨兵是hi + 1。注意这里的hi + 1和lo - 1是"哨兵"而不是"收缩操作"，它们出现的位置是初始化，不在循环里，所以完全不违反"不需要 mid±1"的原则。这一点经常被初学者混淆。第二，trips用long long，因为趟数可能到1e9量级。第三，trips += mid / t之前加了提前退出，避免在极端数据下把多个1e9加起来。这种小优化在二分答案里很常见，因为check会被调用O(log(hi))次，每次都是O(n)，常数优化直接体现在总时间上。

例二：两球之间的磁力（1552）。给定若干位置，选m个位置放球，问"任意两球之间最小距离的最大值"是多少。

这是"最大化最小值"的典型题。答案是一个距离值，范围大概从1到max(pos) - min(pos)。check(d)的含义是"能否选出m个位置，使得任意两球距离都不小于d"。判定方法是贪心：把位置排序，从左往右扫，只要当前位置与上一个选中位置的距离不小于d就选它，最后看选中的数量是否达到m。d越大越难满足，所以是"左边蓝右边红"的反向单调——这时候我把check反着写：check(d)表示"距离d不可行吗"，让d越大越容易满足，就回到统一的形态。或者更直接一点，用"右边红左边蓝"的模板镜像版本：

int maxDistance(std::vector<int>& pos, int m) { std::sort(pos.begin(), pos.end()); int lo = 1, hi = pos.back() - pos.front(); int left = hi + 1, right = lo - 1; // 注意：这里左右哨兵位置对调了 while (left > right + 1) { int mid = right + (left - right) / 2; // check: 距离 mid 是否不可行（即选不满 m 个球） int cnt = 1, last = pos[0]; for (int i = 1; i < (int)pos.size(); i++) { if (pos[i] - last >= mid) { cnt++; last = pos[i]; } } if (cnt < m) right = mid; // 不可行，答案更小 else left = mid; // 可行，答案更大 } return left; }

我写这段代码是为了告诉你：当单调性方向相反时，你可以把左右哨兵的含义整体翻转，代价是循环条件要跟着改成left > right + 1，mid的计算方向也要反过来。这是完全可行的，但我一般不推荐，因为多一套方向就多一个出错点。更稳妥的写法是保持模板不变，把check定义为"距离d是否太远导致选不满"，即check(d) = (选不满)，这样d越大check越容易为真，方向就统一了。"用取反把方向掰直"是我这些年最常用的技巧之一。

4.3 写 check 之前先问自己三个问题

二分答案翻车的概率远高于普通二分，因为骨架不会错，错的永远是check。我总结了一套自查三步：

1. 答案是整数还是浮点？如果是整数，坚持用整数二分，不要引入浮点。比如求平方根，用整数二分求"最大的满足i * i <= x的i"，比写浮点二分加精度判断稳得多。浮点误差会让你在x = 2147395599这种数据上栽跟头。
2. check 是单调的吗？方向是哪边？一定要能用一句话说清"为什么x变大（或变小）之后check的结果不会反复横跳"。说不清就说明问题不满足二分性质。
3. 上下界对不对？下界必须在答案范围内（比如答案最小可能是1，就不能把lo设成0然后用lo - 1当哨兵还指望它一定不可行）。上界必须保证check(hi)为真，或者至少保证答案不会超过hi。很多二分答案的 WA 都是上界估小了。

注意：check里的累加一定要考虑溢出。Σ floor(t / time[i])这种求和，在极端数据下每项都可能到1e9，n到1e5，累加就是1e14，32 位整数直接溢出成负数，然后check结果全乱。看到"求和"两个字，先问一句"会不会超 int"。

5. 题单串讲：把四类需求各刷一道

模板和原理讲完了，接下来是我认为最有效的固化方式——按需求类型各找一道题手写一遍。不要抄题解，就用自己的模板套，套完对着暴力解法对拍。

5.1 数组查找类：从最朴素的开始

704. 二分查找是最基础的模板题，check(i) = a[i] >= target，返回right，然后判断right < n && a[right] == target。这道题的意义不在于难度，而在于让你体会"返回的位置需要额外确认一次"这个模式。很多新手在这里会问"为什么不能直接返回right"，因为right == n表示所有元素都小于target，此时不存在目标值。

34. 在排序数组中查找元素的第一个和最后一个位置是四类需求的最佳练习场。第一个位置就是第一个>= target，最后一个位置就是最后一个<= target，也就是第一个> target减一。写两个 lambda，共用同一个骨架，五行代码搞定：

std::vector<int> searchRange(std::vector<int>& a, int target) { int n = a.size(); int l = firstTrue(n, [&](int i) { return a[i] >= target; }); if (l == n || a[l] != target) return {-1, -1}; int r = firstTrue(n, [&](int i) { return a[i] > target; }) - 1; return {l, r}; }

35. 搜索插入位置本质上就是第一个>= target的位置，直接返回right，连判断都不用。这道题特别适合用来验证你的模板是否正确——如果你还需要改骨架才能过，说明你还没把"四类需求共用一套骨架"这件事消化掉。

153. 寻找旋转排序数组中的最小值是我最喜欢的"非典型查找"例子。旋转排序数组形如[3,4,5,1,2]，它的特点是存在一个下降点。观察发现，以a[0]为参照，性质a[i] < a[0]在整个数组上是单调的：前面全为假，后面全为真。所以check(i) = a[i] < a[0]，返回right，如果right == n（数组完全有序，没有下降点），那答案就是a[0]。

int findMin(std::vector<int>& a) { int n = a.size(); int p = firstTrue(n, [&](int i) { return a[i] < a[0]; }); return p == n ? a[0] : a[p]; }

这道题的价值在于它打破了"二分必须查找某个值"的思维定势，二分查找的是"性质第一次发生翻转的位置"，这跟染色模型完全咬合。

5.2 二分答案类：从模板题到底层思维

875. 爱吃香蕉的珂珂：答案是用餐速度k，范围[1, max(piles)]。check(k) = Σ ceil(piles[i] / k) <= h。这里ceil要写成整数形式(p + k - 1) / k，不要用std::ceil转浮点，大数值下会失精度。

1011. 在 D 天内送达包裹的能力：和 875 几乎同构，答案是最小载重，check(w) = 用载重 w 需要的天数 <= D。天数计算用贪心：能装就装，装不下就开新的一天。这道题和 875 一起刷，你会发现二分答案的骨架和数组查找完全一样，变的只有check。

410. 分割数组的最大值：把数组切成k段，使"各段和的最大值"最小。答案范围[max(a), sum(a)]，check(x) = 能否用不超过 k 段让每段和都不超过 x。判定同样是贪心扫一遍。这道题的check写法值得琢磨：贪心为什么是最优的？因为段数越少越容易满足条件，而贪心在给定上限下能得到最少段数，这是"下界最优"的经典论证。

69. x 的平方根：验证"整数二分优于浮点二分"的最佳例子。要的是"最大的满足i * i <= x的i"，用check(i) = (long long)i * i > x求第一个不满足的位置，再减一。注意i * i要用long long计算，x接近2^31 - 1时i能到 46340，平方后仍在 int 范围内，但用 long long 更保险。

5.3 我在这些题上踩过的坑

第一个坑是**check写反**。在 1552 那类"最大化最小值"的题上，我一开始把check(d)写成"距离d可行"，导致单调方向是递减的，但骨架按递增写，结果返回值恰好是最大可行距离的"上一位"。那次的教训是：写check之前先画一条数轴，标出真值段的朝向。

第二个坑是上界估小。在 2187 类题目里，我一开始把上界写成max(time) * totalTrips，思路是"最慢的车跑完全部趟数"。这在数学上确实可行，但数值会到1e18级别，虽然long long兜得住，但mid计算和trips累加都很贴近溢出边界。后来改成min(time) * totalTrips，数值小了一个数量级，安全性和常数都更好。上界宁可选一个"明显可行"的紧上界，而不是"勉强可行"的松上界。

第三个坑是旋转数组里a[0]的语义。在 153 里，我先写成check(i) = a[i] < a[n-1]（拿末尾元素做参照），结果在完全有序的数组上返回了0，而正确答案应该是a[0]。后来换成a[0]做参照，语义清楚多了。这里的经验是：参照元素要选在分界线的一侧，选错了参照，整个单调性就崩了。

6. 调试与固化：让这个模板变成肌肉记忆

模板写得再漂亮，实战里还是会有check写错、方向搞反的时候。这一节讲几个我常用的调试手段和长期固化的方法。

6.1 三行打印定位分界线

二分的调试最忌讳盯着代码空想。我的做法是在循环外面加三行打印，直接把整个染色过程可视化：

int firstTrue(int n, F check) { int left = -1, right = n; while (left + 1 < right) { int mid = left + (right - left) / 2; bool c = check(mid); printf("mid=%d check=%d -> left=%d right=%d\n", mid, (int)c, left, right); if (c) right = mid; else left = mid; } printf("final: left=%d right=%d\n", left, right); return right; }

这段输出的每一行告诉你：这一轮探了哪个位置、结果是什么、区间怎么收缩。跑一组小数据（n = 10左右），把输出念一遍，你立刻就能看出"为什么最终返回的是这个位置"。这个方法我用过很多次，基本上打印一次就能定位 90% 的边界问题。

更进一步，我会在小数据上写一个暴力对拍：

int bruteFirstTrue(const std::vector<int>& a, int x) { for (int i = 0; i < (int)a.size(); i++) if (a[i] >= x) return i; return a.size(); }

然后随机生成n <= 8的升序数组和随机x，跑 1000 组，比较两个函数的结果。对拍是唯一能让你真正相信模板正确的方法，比看十遍题解都管用。写对拍的成本大概五分钟，收益是以后所有二分题都不再需要纠结边界。

6.2 边界自查清单

我在写二分的题时，会过一遍下面这张清单，你现在就可以拿去用：

这张表里的前五项是模板本身的，后三项是使用习惯。我建议你把它抄在便签上，贴在屏幕边，刷够二三十道二分题之后再撕掉。

6.3 一个容易被忽略的验证技巧

如果你的环境支持标准库，写完手写版本之后可以顺手跟std::lower_bound对比一下：

assert(std::lower_bound(a.begin(), a.end(), x) - a.begin() == firstTrue(n, [&](int i) { return a[i] >= x; }));

标准库的lower_bound语义是"第一个不小于 x 的位置"，和我们的firstTrue(n, check = a[i] >= x)完全一致，两者结果必须相等。这个断言是你给模板上的最后一道保险。我在写新题的check时，经常先用标准库算一遍答案，再用手写模板算一遍，两边一致才提交。

6.4 关于"背模板"这件事我的看法

很多人排斥背模板，觉得背了不理解。但这套开区间模板恰恰相反——它短到可以背，同时它的每一行都能被不变量解释。背下来是让你在赛场上不用现推边界，理解不变量是让你在需要变形（比如二分答案、反向单调）的时候知道该动哪里。两者不冲突，反而是互补的。

我自己现在写二分的流程大概是这样的：先想清楚答案是什么、范围是多少，再写check并在纸上画一条数轴标出真值段朝向，然后套模板。整个过程平均不到三分钟，而且极少出错。这个效率不是我聪明，纯粹是因为把"边界处理"这件事从每次都要重新推的东西，变成了一个固定动作。

如果你之前也在 mid+1、mid-1 上反复栽跟头，我建议你今晚就找三道题——一道普通查找（比如 704）、一道第一个位置的查找（比如 34）、一道二分答案（比如 875）——用这篇里的模板重新写一遍，然后写个暴力对拍跑几百组随机数据。跑通之后你会发现，二分查找可能是你学过的所有算法里，性价比最高的一个。练完这三道，再去看那些以前觉得绕的边界题，多半会有点"就这？"的感觉。