企业官网建设流程全解析

从算法题到真实需求，二分查找的应用面比你以为的宽得多。初中级程序员对二分的印象往往是“有序数组里找一个数”，但等你在题库、算法竞赛、工程代码里反复撞见它，会发现这个模板背后挂着一整套可以迁移的思维。这篇内容我会从最基础的边界写法讲起，重点放在“二分答案”这类高频但容易讲不清楚的应用模式，然后结合 PTA 函数题和浮点精度控制，聊聊实际落地时那些不会写进教科书的坑。

1. 二分查找的应用本质：从有序数组进入单调值域

1.1 为什么很多人只会“在数组里找数”

我见过不少朋友是这样理解二分的：数组先排序，然后维护左右指针，每次取中间值比较，大了去左边，小了去右边。这套理解没有错，但它太窄了。把二分当成“排序数组专用查找工具”，会直接限制你判断一个题目能不能用二分。实际上，LeetCode、PTA 这类平台上大量二分题，数据本身根本不是一个普通数组。

这里的关键认知是：二分不需要“数组有序”这个表面条件，它真正依赖的是“单调性”三个字。数组只是承载有序性最常见的容器，但有序性还可以来自别的地方——布尔值序列、答案的取值范围、甚至一段历史提交记录。

举个例子，First Bad Version（第一个错误版本）这道经典题。假设你有 n 个版本，从某个版本开始全部是坏的，前面全正常。这个序列放在数组里是 [正常, 正常, ..., 错误, 错误, ...]，里面没有相等的“目标值”可以比，因为你要找的是“第一个错误”，而不是“某个等于 target 的元素”。但序列的性质满足：前半段“正常”到后半段“错误”存在一个明确且唯一的切换点，也就是说，状态随版本号单调变化。于是二分仍然成立。

用生活化的方式理解：想象一条温度逐渐升高的曲线，你不需要在一堆具体号码里找某个目标，而是要问“从第几天开始超过 30 度”。这里查询的不是点，而是切换点，但它和二分查找的求解过程完全同构。

1.2 单调性才是二分真正依赖的条件

要判断一道题能否用二分，我的习惯是问自己三件事：

• 有没有一个单调的判定函数 check(x)，并且对任意输入 x，它只有 true / false 或 0 / 1 两种结果？
• 整个搜索空间是否可以用数值区间表示，并且答案就在区间内？
• 目标到底是“第一个满足条件的值”还是“最后一个满足条件的值”？

第一件事最重要。一旦 check(x) 满足单调性——例如“当 x 大时必然满足，x 小时必然不满足”——那么整段值域就能切成左右两半，二分的每一轮相当于砍掉一半永远不可能成为答案的区间。这恰恰是二分查找能在 O(log n) 时间内结束的根本原因。

从这一章往后，每遇到一个应用场景，你都应该先问：这里的单调性是什么？能不能把问题抽象成一个布尔判定？我见过很多人代码写得飞快，却连续判错方向，根子就在于没做这一步抽象。与其说是二分应用，不如说是“寻找单调判定条件”的应用。

2. 区间写法之争：left<right 还是 left<=right

2.1 两种模板的语义区别

二分最难的部分往往不是算法思想，而是边界条件。网上关于 left<right 和 left<=right 的讨论层出不穷，但其实它们只是两种不同区间的表达方式，分别服务于不同的查找目标。

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

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

这个循环结束时 l > r，它找到的往往是某个边界位置。比如找 target 的插入位置，结束时 l 正好是第一个大于等于 target 的下标。很多人不理解为什么最后返回 l 而不返回 mid，其实是因为 mid 在最后一次循环后已经不存在于合法区间了，而 l 恰好收敛到了目标位置。

再看左闭右开写法：

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

区别在于 r 初始化为 n 而不是 n-1，循环条件是 l < r，并且右边界只收缩到 mid。它的语义是：查找区间是 [l, r)，结束时 l == r，正好是目标边界的下标。下面用一个表格总结两者的行为差异：

我的建议是，在实现“求第一个满足某条件的下标”这类需求时，优先使用左闭右开写法。它更接近 C++ 标准库 lower_bound 的语义，也更容易记忆。

2.2 死循环从哪来

死循环是二分应用里所有人都可能遇到的事故。最常见的原因，是对 mid 取整方向与边界收缩方向不匹配。

比如写成 l = mid，而且 mid = (l + r) / 2 是向下取整，那么当区间缩小到 [0, 1] 时，mid = 0，如果此时判定条件要求 l 移动到 mid，那么 l 仍然是 0，永远困住。

反过来说，如果想把 l 移动到 mid，mid 就必须向上取整，即写成 mid = l + (r - l + 1) / 2。很多题解里出现 +1 就是这个目的，它不是一个魔法，而是为了配合“l = mid”这种收缩方向。这个细节特别值得记，因为很多报错不是编译错，而是卡在超时或者运行时间超限，你反复检查判定逻辑都找不出问题，最后发现是死循环。

2.3 一套不容易错的组合拳

我个人的总结是：把任务统一翻译成“求第一个满足 condition 的下标”，然后固定用左闭右开 + l = mid + 1 + r = mid 的组合。模板如下：

int binary_bound(vector<int>& a, int target) { int l = 0, r = a.size(); while (l < r) { int mid = l + (r - l) / 2; if (a[mid] < target) { // 不满足条件，排除左半段 l = mid + 1; } else { // 满足条件，保留 mid r = mid; } } return l; // 第一个 >= target 的位置 }

这样写的好处是：l 的移动永远是“跳过不满足的位置”，让 l 成为答案候选；r 的移动永远“收窄满足区域的右边界”，让 r 不会小于答案。最后两者重合，即是答案。使用这套模板后，我基本没再因为边界问题“打死循环”过。如果题目要求“最后一个满足条件的位置”，则反向处理：先求第一个不满足的条件位置，再减一。

3. 二分答案：把“求最值”转化成“猜答案 + 快速判定”

3.1 木材切割：从每根柱子能切几段开始

二分查找最典型的应用升级，是把二分用在“答案范围”上，而不是直接用在原数组上。这种模式竞赛里叫“二分答案”。它适用于一类问题：答案本身是一个整数或实数，且你能判断某个答案是否可行。

以经典的木材切割问题为例：给若干根长度已知的木头，要求切成 K 段等长的木段，求每段最大可能的长度。这个问题直接去推公式很难，但换个角度就很容易：先猜一个长度 len，然后检查这根木头能切几段。所有木头能切出的总段数如果大于等于 K，说明 len 可行。段数随 len 增大而减少，所以 check(len) 关于 len 是单调递减的，可以用二分找最大的可行 len。

上界怎么定？一种简单取法是所有木头总长度除以 K，或者直接取最长木头长度。我习惯直接取“总长度 / K + 1”，这样既不会被卡死，也不会浪费搜索空间。

伪代码如下：

l = 1 r = max_length while l < r: mid = (l + r + 1) / 2 // 注意这里用向上取整 if (可切割段数(mid) >= K): l = mid else: r = mid - 1 answer = l

注意这里 mid 用了向上取整，因为当 l 满足条件而 r 也满足条件时，普通向下取整可能导致 l 一直停滞在同一个位置出不去。这个细节恰好呼应了第 2 章里说的收缩方向问题。

3.2 分割数组：最大子段和的最小化

另一道典型题是 LeetCode 410“分割数组的最大值”：给定一个非负整数数组和一个整数 m，将数组分成 m 个连续的子数组，使得这 m 个子数组各自和的最大值最小。

这题如果直接想动态规划，稍复杂；但用二分答案，整个思维链会很清晰。先猜一个上限 limit，看是否能将数组分成不超过 m 段，使得每段和都不超过 limit。这个判定用贪心就能做：从头往后累加，一旦当前段和加上下一个元素超过 limit，就立即另起一段。如果最终段数大于 m，说明 limit 太小；否则可行。随着 limit 增大，所需段数只减不增，所以 check(limit) 单调，可以二分。

下界取数组最大元素，上界取数组总和。模板：

bool canPartition(vector<int>& nums, int m, int limit) { int cnt = 1; long long cur = 0; for (int x : nums) { if (cur + x > limit) { cnt++; cur = x; } else { cur += x; } } return cnt <= m; } int splitArray(vector<int>& nums, int m) { long long l = 0, r = 0; for (int x : nums) { l = max(l, (long long)x); r += x; } while (l < r) { long long mid = l + (r - l) / 2; if (canPartition(nums, m, mid)) r = mid; else l = mid + 1; } return l; }

这题我第一次写的时候，把上界取成了所有元素和，然后还去硬凑复杂度，后来发现其实没有必要那么紧张，因为二分在 log 级别迭代，每次检查是 O(n)，总体复杂度 O(n log sum)，对常见数据规模完全够用。

3.3 判定函数为什么是二分答案的灵魂

很多人在二分答案时把注意力全放在 while 循环和边界上，但真正决定代码能跑对的，是 check 函数的正确性。二分只是反复调用 check 的框架，check 一旦有偏差，结果就会系统性偏移，而且远看很难发现。

check 函数常见的错误有这么几类：

• 贪心策略选错，导致某种情况下多统计或少统计段数。
• 判定条件方向搞反，比如“可行”写成“不可行”。
• 数据范围没用 long long，中间累加直接溢出，尤其当数组和达到 1e9 级别而你又只开了 int。

一个建议：写 check 前先把思路用一两个小例子手推一遍。比如分割数组，先拿 nums = [7,2,5,10,8], m = 2 手工验证 limit = 10 时分成几段，再验证代码会不会给出同一个结果。这种“人肉走读”本质上是在给 check 函数做单元测试，成本很低，但能避免比赛或提交时大面积返工。

4. 浮点二分：精度控制与连续值域的二分

4.1 浮点二分和整数二分的差别

前面讲的场景，答案基本都是整数。但现实里很多题目要求答案精确到若干位小数，比如求某个多项式的根、计算开方结果、求满足某种几何约束的最大半径。这时二分直接作用于连续实数域，没有“数组下标”和“相邻位置”的概念。

一个典型的例子是用二分实现 sqrt 函数：给定 x，求其平方根。你可以把搜索区间设为 [0, max(1, x)]，然后判断 mid * mid 与 x 的大小关系。因为 f(mid) = mid * mid 是一个单调递增函数，所以二分仍然成立，只不过结束方式从“left < right”变成“right - left < eps 或固定迭代次数”。

4.2 终止策略：eps 还是固定迭代次数

浮点二分最讲究的是终止条件。两种主流做法：

做法一是 while (r - l > eps) 形式。eps 取多少很关键。如果题目要求保留三位小数，eps 通常取 1e-6 就够了；如果要求 1e-9，建议 eps 取 1e-12。一个常见坑是 eps 取得过小，比如 1e-15，而 l 和 r 的差距可能因为浮点误差陷入震荡，或者因为二进制无法精确表示某个小数，导致达不到退出条件。

做法二是固定迭代次数，我个人更推荐这个。比如直接 for 循环 100 次，每次把区间缩小一半。原理是：每轮迭代区间长度减半，2 的 100 次方已经远远超出双精度浮点数 15-17 位有效数字的范围，迭代到后面即使不再真正变化也不会死循环。这种写法的好处是不用纠结 eps 是多少，适应性强。代码示例如下：

double sqrt_binary(double x) { double l = 0, r = max(1.0, x); for (int i = 0; i < 100; i++) { double mid = (l + r) / 2; if (mid * mid < x) l = mid; else r = mid; } return l; }

稳健的原因是：双精度浮点能表示的相对精度大约 2e-16，而每一轮二分把问题规模缩小一半，100 轮后缩小的倍数远超双精度极限，之后循环再跑也不会有什么实际变化，但也不会超时或死循环。

4.3 输出精度处理的隐藏坑

还有一个容易踩的坑是输出。题目要求保留两位小数，常规做法是 printf("%.2lf", ans)，但这个 ans 在某些边界情况下会差 0.01。比如 ANS = 1.999，printf 会输出 2.00，这通常没问题；但有些判题系统对误差校验很严格，会直接比对 ±0.01 内的数值。更好的做法是不要直接输出左边界或右边界，而是输出根据题意计算出的最终函数值，或者在输出前做一次“四舍五入到目标精度”的操作。

一种可用写法：

double result = floor(ans * 100 + 0.5) / 100; printf("%.2lf\n", result);

不过很多题目的判题方式是“误差不超过 eps 即算正确”，那样直接用 printf("%.2lf", l) 其实也行。真正的坑在于：如果你想返回开方后的结果再去参与下一步运算，不要再对这个结果做一次二分，因为二次处理会引入额外误差。一步到位的二分结果，往往就是你该提交的结果。

5. PTA 函数题：如何把二分写成可复用的接口

5.1 函数题的坑：签名、语义与边界

“二分查找 pta 函数”是题库平台里相当常见的题类。这类题不会让你从标准输入读数据，而是要求在限定函数体里实现逻辑。例如给你一个已排序数组和查找目标，要求实现 BinarySearch 函数，返回是否找到，并通过引用参数返回下标。

这类题目考试既有算法部分也有工程习惯部分。你需要按题目给的签名写，不允许自己改接口，比如：

bool BinarySearch(int a[], int n, int k, int &index);

此时你要明确几件事：

• n 是数组长度，a 已经升序排序。
• 找到时返回 true，并把下标存入 index；没找到返回 false，index 可以置为 -1。
• 边界情况是 n <= 0 时，直接返回 false，不要访问 a[0] 或 a[n-1]。
• 数组元素下标从 0 开始，还是从 1 开始？这会影响边界初始化。一定要看题面。

5.2 一份判题友好的参考实现

下面是一个比较稳的写法，兼容“返回是否找到 + 下标引用”的常见要求：

bool BinarySearch(int a[], int n, int k, int &index) { if (n <= 0) { index = -1; return false; } int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (a[mid] == k) { index = mid; return true; } else if (a[mid] < k) { l = mid + 1; } else { r = mid - 1; } } index = -1; return false; }

这段代码没有炫技成分，但可读性和正确率都足够。函数题尤其不适合用递归，因为递归栈深未必有问题，但代码量和出错概率都会提高，判题环境也不给你调试器，一步错就直接提交失败。

5.3 手写二分与库函数的取舍

熟练之后你可能会想，既然 C++ 有 lower_bound 和 upper_bound，为什么还要手写二分？真实项目里我确实优先用库函数，但考试和算法题里手写二分仍然有它的位置。原因是库函数返回的是迭代器/下标，但语义是“第一个不小于某值的位置”，而不是“是否存在某个值”。两者在目标语义上并不完全一致。

比如你想判断 k 是否存在，直接调 lower_bound 后还要额外比较一下 *it == k。而在 PTA 函数题里，你没法改函数返回类型，只能按题目要求手写。这个细节也是工程习惯与算法训练之间的一道分界线：你会用工具固然好，但理解工具内部的判定逻辑，你才知道什么时候该用它、什么时候不能只用它。

6. 走出算法题：二分思想在工程里的三个影子

6.1 git bisect：用二分定位出问题的提交

二分思想离现在开发者日常最近的一个应用，可能不是算法题，而是 git bisect。假设某天你发现代码坏了，但不知道是 50 个提交中的哪一个引入的 bug。逐版本手动测试不现实，二分就可以派上用场。

把历史提交看作一条线，从某个“仍然正常”的旧版本开始，到“已经出错”的最新版本结束。用 git bisect 标记一个坏版本和一个好版本，它就会不断帮你二分这段范围，让你在每一轮只验证一个中间版本，并告诉它“这个版本是好的还是坏的”。由于版本状态从某一提交开始会突然变坏，这个序列是单调的，和 First Bad Version 完全同构。整个定位过程大约 log2(50) ≈ 6 次验证就能完成，而不是 50 次。

6.2 索引与存储结构里的二分

数据库索引的 B+ 树结构里，每个节点通常保存一组有序的 key，页内搜索时用的就是二分查找思路。与之类似的还有跳表，在多层链表上通过概率跨级跳转来模拟二分效果。这些场景的代码你可能用不到，但底层逻辑和咱们前面讨论的“单调序列上的快速定位”是同一个思想。

如果你维护过一个大数组的分页列表或定时任务调度系统，可能也遇到过需要快速定位某个时间点的任务：按时间排序后，你就是在一个有序空间里做范围切割。理解二分边界语义，能帮你避免使用 lower_bound 时把“首个大于等于”误当成“最后一个小于”，这类 bug 在真实业务里很隐蔽，一旦发生就极其难排查。

6.3 什么时候不要用二分

需要提醒的是，二分是一个工具，不是所有问题都可以套。如果 check 不具备单调性，比如一个序列的状态是“好、坏、好、坏”，那就不能用二分，因为砍掉一半区间可能砍掉正确答案。另一个是在数据量极小的情况下，线性查找或哈希查找更合适。二分的时间复杂度是 O(log n)，但常数也很重要——对溢出、乘法误差的处理如果不到位，实现一套二分代码的成本可能还不如直接遍历。

所以，二分应用的真正门槛是把“有序性”和“单调性”分辨清楚。有序是数据属性，单调是函数属性。前者对应的场景是查找，后者的场景是判定。能在这两者之间灵活切换，你才算真正掌握了二分查找的应用。

最后再分享一点个人经验：我学二分很久之后才意识到，最容易出错的从来不是算法本身，而是你心里没有先给出一个明确的边界语义。等到你能画出哪一段是“不满足”、哪一段是“满足”，再去看 while 条件和 l/r 的收缩方向，就会发现所有模板其实都是同一种思想的不同表达。这不是一条能背出来的知识，而是一个想清楚就能一直沿用的思维框架。