二分查找的本质与边界技巧：从有序数组到二分答案与浮点逼近

聊到二分查找，很多人的第一反应是“不就是在一个有序数组里找一个数嘛，写个 while (l <= r) 就行”。但我在带新人、改算法的过程中发现，真正能把二分查找的应用玩明白的人真不多。它远远不止“查找”这么简单，更是一套“不断排除一半答案”的思维框架，能解决边界定位、最优值猜测、浮点逼近、旋转数组、峰值查找等各种看似不相关的问题。PTA上的“二分查找函数题”每年都能挂掉一批人，尤其是重复元素要区分“第一个”和“最后一个”的时候；算法题里二分的变体更是常客。这篇文章我就从实际做题和改题的角度，把二分查找的实现细节、边界变体、二分答案、浮点二分以及常见坑完整讲一遍，适合正在刷PTA、准备期末考试或算法面试的读者。

1. 二分查找的本质与应用版图

1.1 从“有序数组找数”到“单调性判定”

最基础的二分查找大家都清楚：数组有序，每次取中点，和目标值比大小，然后扔掉一半。可你有没有认真想过，为什么数组有序就能二分？本质上是因为数组元素相对 target 具有单调性——在某个分界点之前都小于 target，分界点之后都大于等于 target。每次比较本质是一次“判定”，这次判定的结果能明确排除掉一半候选位置。

这个思想一旦抽象出来，二分查找的应用范围就远不止“有序数组”这一个场景。比如你想在一个很大的值域 [L, R] 中找一个“最小的可行解”，只要你能快速写一个 check(mid) 判断“mid 是否可行”，并且可行性与 mid 的关系是单调的，那就能对值域二分。再比如浮点数方程求根、旋转数组中的查找、无序数组中找峰值，背后都是同一套“通过比较，排除掉不可能的一半”的逻辑。所以我经常跟人说，二分的本质是“单调性”，而不是“数组有序”。

1.2 二分查找的主要应用场景分类

把二分查找的应用场景梳理一下，大致有下面几类：

• 精确查找：在有序数组里找给定值，返回任意一个下标。
• 边界查找：找第一个等于 target 的位置、最后一个等于 target 的位置、第一个大于等于 target 的位置等。
• 二分答案：答案落在一个整数或实数区间内，直接求解困难，但给定一个候选值能快速判断可行性。典型如“最大值最小化”“最小值最大化”。
• 浮点二分：用浮点数逼近方程根或极值，常见于几何计算、数值计算。
• 特殊数组二分：旋转有序数组、峰值查找、二维递增矩阵查找等。
• 结构性二分：在树状数组上二分找第 k 个前缀和、在有序集合中按位置拆分等。

这篇文章会重点讲最容易踩坑的边界二分和二分答案，再带一下旋转数组和浮点二分，最后用 PTA 函数题串一遍实战流程。对于刚从基础入门的读者，先把前两类吃透，后面的内容会帮你打开新世界。

2. 边界查找：PTA函数题里最容易被扣分的细节

2.1 为什么需要区分“第一个”和“最后一个”

拿最常见的需求来说：统计一个有序数组里某个数出现的次数。很多人第一反应是二分找出任意一个 target，然后往左右两边线性扫描。这个思路不能说错，但如果数组里恰好全是同一个数，线性扫描会直接退化到 O(n)，二分就白写了。正确做法是分别二分出“第一个等于 target 的下标”和“最后一个等于 target 的下标”，两个下标相减再加 1 就是出现次数。

这也是 PTA 函数题里特别爱考的变化。有些同学第一次写“找第一个等于 target”的二分时，总是喜欢在中点找到 target 后立刻 return。数组没有重复元素时没问题，但一旦有重复元素，这个 return 返回的可能是最后一个，也可能不是第一个。题目要求“返回最小下标”，你就 WA 了。这时候需要的不是“找到任意一个”，而是不断压缩右边界，直到确定最左边的命中位置。

2.2 标准实现与循环不变式

先看“找第一个等于 target”的写法。我这里统一用左闭右闭区间 [l, r]，因为它跟数组下标的直觉最贴近。

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

核心思路是：当 a[mid] >= target 时，第一个等于 target 的位置要么是 mid，要么在 mid 左边，所以先记录 ans = mid（当然要满足 a[mid] == target），然后 r = mid - 1 继续往左找；当 a[mid] < target 时，target 肯定在右边，所以 l = mid + 1。循环结束时，ans 保存的就是最左边的命中下标；如果整个数组里没有 target，ans 一直是 -1。

再看“找最后一个等于 target”，逻辑刚好反过来，判断条件用 <=，没命中时往右收缩。

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

很多初学者会把“找最后一个”写成 if (a[mid] < target) 再单独处理相等，这样不是不行，但分支一多容易乱。上面这种把等于情况合并进 <= 分支，然后通过 ans 记录候选位置，思路很干净。这里的循环不变式是：每一轮循环开始时，你都相信“如果 target 存在，那么第一个等于它的位置一定还在 [l, r] 中，并且 ans 记录的是当前已经找到的最左候选”。只要这个不变式不被破坏，循环结束答案就是对的了。

还有一个细节要强调：mid 计算为什么用 l + (r - l) / 2 而不是 (l + r) / 2？因为当 l 和 r 都接近 INT_MAX 时，l + r 可能溢出。虽然普通的 OJ 题不一定能碰到，但养成这个习惯，换到更极端的场景不会翻车。

2.3 PTA函数题的实用写法

PTA 上有一道很常见的函数题，原型类似这样：在长度为 n 的升序数组 a 中查找 key，找到返回下标，找不到返回 -1。如果题目没有额外要求“返回第一个等于 key 的下标”，那么用最普通的精确查找模板就够了。

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

需要特别提醒：PTA 函数题只要求提交函数实现，不要自己写 main，也不要在函数里打印调试信息。我见过不止一个同学把 printf 调试语句留在提交代码里，OJ 输出多了自然判错。另外，PTA 有时会把数组下标定义成 1-based，比如题目说“下标 1 到 n 存放数据，0 号位不用”，那 l 初始化就应该是 1，r 初始化是 n，返回的下标也是 1-based。审题时先确认这件事，不然同样的模板要么越界，要么答案整体偏移。

3. 二分答案：把“求最优解”变成“判定可行性”

3.1 什么时候该用二分答案

判断标准其实很直接：题目让你求一个最值，而你发现“给定一个猜测值 x，能在 O(n) 或更短时间判断这个 x 是否可以达到”，那就可以二分答案。直接算很难，但判可行性容易，这种题天然适合二分。

比如要把 n 根木材切成统一长度，问最长能切到多少。这个问题直接列方程几乎没法解，但如果你告诉我“每段长度 x”，我可以很快算一遍每根木材能切出几段，累加起来看是否达到目标。这就是典型的“答案可二分”。单调性也很直观：x 增大时，能切出的总段数只可能减少或不变；x 减小时，总段数只可能增多或不变。如果 check(x) 不满足单调性，二分就不是“排除一半”，而是赌博，所以看到没有单调性的题目，不要硬套二分答案。

3.2 整数二分的模板与方向控制

整数二分答案最容易出错的是方向：求的是“最小可行解”还是“最大可行解”？模板其实就差两行。以“最小可行解”为例，mid 可行时记录 ans，并把右边界压到 mid - 1，因为更小的值可能也可行；mid 不可行时把左边界推到 mid + 1。

bool check(int x) { // 返回 x 是否可行 return true; } int main() { int l = 1, r = 1e9, ans = -1; while (l <= r) { int mid = l + (r - l) / 2; if (check(mid)) { ans = mid; r = mid - 1; // 继续找更小的可行解 } else { l = mid + 1; } } printf("%d\n", ans); return 0; }

如果要求“最大可行解”，就把 check 成功后的处理改成 ans = mid; l = mid + 1。很多人死记一套模板，结果做了两道题全是 WA。我建议每次写二分答案之前，先问自己：check(mid) 为真时，答案还能更小还是更大？想清楚再动笔，比背模板靠谱得多。

还有一个隐藏坑：check 函数里如果 mid 取 0，可能会出现除以 0、数组越界等问题。对于答案最小是 1 的题，l 直接设成 1，再单独处理“找不到可行解输出 0”的情况。

3.3 真题实战：木材切成最大等长段

拿经典的木材加工题当例子，PTA 和洛谷都有类似题目。有 n 根原木，长度分别为 L[i]，现在要把它们切成 k 段长度相同的小段，问单段最大长度是多少。如果单段长度为 x，那么一根原木可以贡献 L[i] / x（取整）段，累加就是总段数。check(x) 返回总段数是否大于等于 k。

#include <cstdio> int n, k; long long L[100005]; bool check(int x) { long long cnt = 0; for (int i = 0; i < n; i++) { cnt += L[i] / x; } return cnt >= k; } int main() { scanf("%d%d", &n, &k); long long maxL = 0; for (int i = 0; i < n; i++) { scanf("%lld", &L[i]); if (L[i] > maxL) maxL = L[i]; } int l = 1, r = maxL, ans = 0; while (l <= r) { int mid = l + (r - l) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } printf("%d\n", ans); return 0; }

这里要求的是“最大可行解”，所以 check(mid) 为真时记录 ans，再往更大的值试探。r 的上界取 maxL，因为单段长度不可能超过最长原木。时间复杂度 O(n log maxL)，n 是 1e5、L 是 1e9 时完全够快。注意 ans 初值是 0，表示一段都切不出来时输出 0。如果 l 从 0 开始，check 里会除以 0，所以这里 l 从 1 起步，用 ans=0 兜底。

吃透这一道题，就能迁移到分巧克力、装船问题、机器人搬砖等一大类二分答案题。它们共同点都是：不直接求最优值，而是判断某个猜测值是否可行，然后反复二分直到逼近答案。

4. 浮点二分与特殊结构上的二分

4.1 浮点二分的精度与终止条件

整数二分需要纠结 l <= r 还是 l < r，浮点二分反而更简单：循环条件直接写成 while (r - l > eps)，eps 根据题目精度要求确定，一般取 1e-6 或 1e-7。由于浮点精度有限，我们不需要也不能通过 l == r 退出循环。

double binarySqrt(double x) { if (x < 1) return x; double l = 0, r = x; double mid; while (r - l > 1e-7) { mid = l + (r - l) / 2; if (mid * mid < x) l = mid; else r = mid; } return (l + r) / 2; }

注意浮点比较不要用 mid*mid == x 这种判断，因为浮点运算有误差。无论 l 还是 r，在终止时都已经非常接近答案，但题目如果要求保留三位小数，eps 设到 1e-4 或更小就够，不要设得比输出精度还要宽松很多。浮点二分在几何题里很常见，例如在时间和速度之间二分，或者找抛物线的交点。套路都是：把 mid 代入几何公式计算，根据结果判断当前 mid 偏大还是偏小。

4.2 旋转有序数组：先判断哪半段有序

一个有序数组经过旋转后，比如 [4,5,6,7,1,2,3]，在这种数组里找 target。暴力扫描是 O(n)，但只要用一点结构信息，就能在 O(log n) 内完成。每次拿到 mid，先判断左半段 [l, mid] 是否有序，再根据 target 是否落在这个有序区间里决定去哪边找。

int searchRotate(int a[], int n, int target) { int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (a[mid] == target) return mid; if (a[l] <= a[mid]) { // 左半段有序 if (a[l] <= target && target < a[mid]) { r = mid - 1; } else { l = mid + 1; } } else { // 右半段有序 if (a[mid] < target && target <= a[r]) { l = mid + 1; } else { r = mid - 1; } } } return -1; }

判断左半段有序用的是 a[l] <= a[mid]。如果数组允许重复元素，这个条件可能不再可靠，最坏会退化成 O(n)。面试时如果被问到“有重复元素的旋转数组查找”，可以主动说一句“有重复时最坏线性，但平均仍然是对数级”。这个例子告诉我们，二分不一定要求整个数组严格有序，只要每次能从局部结构里得到“答案不可能在某一半”的信息就行。

4.3 寻找峰值：无序数组也能二分

再来一个更有冲击力的例子：在无序数组里找任意一个峰值，也就是 nums[i] 大于左右邻居，边界看作负无穷。数组本身无序，但相邻元素不相等。怎么二分？

关键在局部单调性：如果 nums[mid] > nums[mid+1]，说明 mid 左侧一定存在峰值；反之说明右侧一定存在峰值，因为至少 mid+1 有可能是峰值。于是每次都能排除一半。

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

注意这里循环条件是 l < r 而不是 l <= r，并且更新时用的是 l = mid + 1、r = mid。为什么不是 r = mid - 1？因为当 a[mid] > a[mid+1] 时，mid 本身可能就是峰值，不能把它排除掉。这个模板重要的是保证区间始终保留“潜在峰值”，当 l == r 时，区间里只剩一个位置，它一定就是峰值下标。很多人在这里写成 r = mid - 1，结果漏掉峰值，查半天不知道错在哪。

从旋转数组和峰值这两个例子可以看出，二分真正依赖的只有一条：每次比较能确定答案不在某半边。它不需要数组整体有序，只要有一个方向性的判断就够了。

5. PTA题目实战与常见错误实录

5.1 读题时先确认五件事

PTA 的二分题风格比较多，尤其函数题，题面不长，但坑全藏在细节里。写代码前先花 30 秒确认下面五件事，能避开一半的 WA。

• 数组下标起点是 0 还是 1？函数接口给的参数到底是长度还是最大下标？
• 数组是升序还是降序？题目说“非递减”时，意味着可能有重复元素。
• 有重复元素时，题目要求返回任意一个位置，还是第一个/最后一个位置？
• 找不到时函数应该返回 -1，还是返回一个可能让人莫名其妙的值？
• 提交的是完整程序还是只提交函数？后者不能有 main 和任何多余输出。

把这些确认好，再套模板。很多人题没读清就写二分，样例过了，隐藏测试点全挂。我见过最典型的错误是把“返回第一个大于 key 的位置”理解成“返回 key 所在位置”，样例里 key 恰好唯一存在，于是侥幸通过，换个数据就崩。

5.2 一个典型函数题的完整答案

假设 PTA 题目要求你实现 int binarySearch(int a[], int n, int key)，在非递减数组 a 中查找 key，找到返回最小下标，找不到返回 -1。那么直接这样写：

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

判断条件是 a[mid] >= key，而不是 a[mid] == key 后 return，因为要的是最小下标。如果题目改成“返回最大下标”，只需要把 >= 换成 <=，把 r = mid - 1 换成 l = mid + 1，其余不动。如果题目只要求任意一个下标，普通模板里找到就 return 更省事，不要盲目用边界模板。

还要提一点，PTA 的 C 语言函数题有时会用 C++ 编译器编译。如果你在函数里用了 C++ 特有语法可能编译失败。稳妥做法是函数内只用 C 风格数组访问，不依赖 vector、algorithm 等。如果非要用 C++ 的 lower_bound，记得 #include ，并且注意返回的是迭代器，数组名退化为指针后要 handle 一下，反而绕远。

5.3 死循环、溢出、返回错值排查

下面这几条是我帮别人 debug 时遇到的高频问题，几乎涵盖了 PTA 二分题的主要错误类型。

死循环问题是重灾区。如果使用左闭右闭 [l,r]，循环条件是 l <= r，每次进入循环后 mid 至少会让 l 或 r 发生移动，理论上不会死循环。但如果你用 l < r，又把 mid = (l+r)/2，更新时写成 l = mid 或 r = mid，那么当区间缩到两个相邻元素时，mid 可能永远等于 l，区间就不再缩小。比如 l=2, r=3 时 mid=2，如果更新到 l=mid，区间就永远停在 [2,3]。解决办法是：左闭右闭时用 l=mid+1 或 r=mid-1；左闭右开时用 l=mid+1 和 r=mid。绝对不能 l 和 r 都保持不变。

6. 我把二分写对的私有方法论

6.1 三个问题定下循环不变式

我自己现在写二分，动手前固定问三个问题。第一，答案可能存在的区间是什么？第二，这个区间用左闭右闭还是左闭右开？第三，当中间值不满足条件时，下一次搜索区间应该排除哪一半？把这三个问题答完，代码基本就出来了。

举个例子，找“第一个大于等于 target 的位置”。答案区间是 [0, n]，其中 n 是数组长度，因为可能不存在这样的元素。我选左闭右开 [l, r)，l 初始化为 0，r 初始化为 n。循环 while (l < r)，mid = l + (r-l)/2。如果 a[mid] >= target，说明 mid 可能就是要找的第一个位置，而且答案不会在 mid 右边，于是 r = mid；否则 a[mid] < target，mid 不可能是答案，l = mid + 1。循环结束时 l == r，返回 l 就对了。

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

这就是 C++ 标准库 lower_bound 的经典实现。我建议你也把左闭右开这套掌握，因为很多高级二分和树状数组二分都默认用左闭右开；如果只会一套，看别人的代码会吃力。不过要提醒的是，不要在同一段代码里混用两种区间表示。比如 while (l<r) 的循环里写 r=mid-1，常常会把正确答案排除掉。

6.2 对拍测试：让暴力验证二分

二分太容易错，那就不要只靠眼睛看。写一个暴力函数，再写一个二分函数，用随机数据对拍。比如你想验证“找第一个等于”的二分，可以写一个小脚本，随机生成排序数组和 target，然后对比二分结果和线性扫描结果。一万组全部一致，基本就放心了。

import random def binary_first(a, x): l, r, ans = 0, len(a) - 1, -1 while l <= r: mid = (l + r) // 2 if a[mid] >= x: if a[mid] == x: ans = mid r = mid - 1 else: l = mid + 1 return ans def force_first(a, x): for i in range(len(a)): if a[i] == x: return i return -1 for _ in range(10000): n = random.randint(1, 20) a = sorted(random.choices(range(1, 10), k=n)) x = random.randint(1, 10) if binary_first(a, x) != force_first(a, x): print("WA", a, x, binary_first(a, x), force_first(a, x)) break else: print("OK")

这种对拍方式在本地跑一跑，比空想边界要高效得多。实际比赛或作业里遇到任何边界模板，我都建议先用暴力随机测试验证一遍再提交。

6.3 几个避免翻车的小习惯

最后分享一些我这些年总结下来的习惯。第一，凡是二分数组，先确认数组长度，r 是 n-1 还是 n，这决定后面所有边界。第二，凡是需要返回 -1 的情况，优先用 ans 初值 -1，不要依赖循环结束后对 l+r 复杂判断。第三，把 check 函数单独抽出来写，不要和二分主逻辑混在同一行，出问题方便调试。第四，提交前删掉所有调试输出。第五，题目里出现“非递减”而不是“递增”时，默认可能有重复元素，该用边界二分就用边界二分，别心存侥幸。

写了这么多，我个人其实还是在“左闭右闭 + ans 记录”这个风格上最顺手，因为它跟普通查找模板最接近，不容易出错。但你完全可以选左闭右开，只要保持前后一致就没问题。二分查找的代码可以很短，但短代码越容易在边界上翻车。有了不变式意识，加上对拍验证，再复杂的变体也能稳稳拿下来。希望这篇实战总结能少让你受一点 WA 的折磨。