二分查找与二分答案：C语言实现、边界处理与竞赛实战

P8088，『JROI-5』Autumn，难度普及+，标签里简简单单四个字：二分查找。第一次看到这道题的人，多半觉得这就是一道套模板的水题。但带过几年算法竞赛我就明白，凡是在“普及+”这个档位被反复讨论的二分题，真正考的都不仅仅是模板本身——它考的是你什么时候能意识到“答案本身可以被二分”。

这篇文章就以这道题为主线，把二分查找从经典模板讲到二分答案，从C语言实现讲到PTA函数题里那些容易挂分的细节。无论你在准备CSP-J/S、蓝桥杯，还是被学校PTA作业折磨，这套思路都通用。我会把边界处理、mid取值、check函数设计、死循环排查这些我实际踩过的坑全部摊开讲，最后再给一个可以直接抄作业的完整代码。

1. 题目与背景：一道普及+的二分题为什么值得反复做

1.1 从标题信息里能读出什么

先拆一下标题。“P8088”说明这是洛谷题库的题号，“JROI-5”指向某个社区赛事的第五场比赛，“Autumn”是题目名，末尾的“普及+”是难度评级，搜索关键词“二分查找”直接点明了正解方向。社区赛的题有一个共同特点：题面通常不短，但正解往往很朴素，不会上来就甩你一棵线段树。这种题最考察的就是“把生活化的场景翻译成算法模型”的能力，而Autumn这种名字，基本暗示了题目里会有一个随时间或者随位置变化的过程，比如日照时间、气温曲线、叶子飘落的位置，然后让你在某个变量上求最大值或最小值。

难度定在“普及+”，意味着它比纯普及组的模拟题多了一点思维量，但还不到提高组那种需要数据结构加持的程度。这种题最舒服的解法就是二分答案加check函数。你不需要维护复杂的数据结构，只需要回答“如果某个值是这个数，行不行”，然后用二分把最优值找出来。这也是我特别喜欢拿这类题给刚学完排序和枚举的选手练手的原因。

1.2 二分查找在竞赛技能树里的位置

二分查找是算法竞赛里性价比极高的一项技能。学会它只需要半小时，真正掌握它可能需要几十道题，但它能撬动的题目范围非常大：从有序数组里找数字、从旋转数组里找最小值、求最大值最小化、最小值最大化、实数域上的精度逼近，甚至是对着单调函数求零点，全部是二分的地盘。

在C语言的支持下，二分查找的代码量并不大，但它对思维习惯的要求很独特。你需要习惯“通过不断缩小答案的可能范围来逼近真实答案”，而不是“一步一步枚举出答案”。很多新手第一次写二分，总忍不住在循环里打印一坨调试信息，然后发现死循环了，这就是因为脑子里还残留着枚举的思维惯性。等你真正把“区间收缩”这个思想焊死在脑子里，再看P8088这种题，一眼就能分辨出它是不是二分答案：题目要你求一个最值，而且这个最值的可行性随答案单调变化，那就二分。

2. 二分查找的根：从有序数组定位到“猜答案”

2.1 经典二分查找的写法与不变量

不管是什么花样的二分，底层都是那个最经典的问题：在一个有序数组里找一个数。C语言实现通常长这样：

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

这段代码的关键不是那三行if，而是理解循环里始终维持的不变量：答案如果存在，一定在区间[l, r]里。所以每次比较a[mid]和x之后，我们可以放心地丢掉一半区间，因为丢掉的这一半里绝对没有答案。这个不变量是二分的灵魂，后面所有边界处理都是为了保证它不失效。

很多人问为什么不用mid = (l + r) / 2，而要用l + (r - l) / 2。在纯竞赛环境里可能无所谓，但在工程或PTA的测试数据里，l + r可能溢出int，这是真实存在的问题。养成用减法计算mid的习惯，能省掉一次崩溃。这个细节我不会再强调了，反正后面每一段代码都按这个习惯写。

2.2 三种区间写法与边界翻车点

二分查找的写法不止一种，关键是选一种你永远能记住的，然后每次都用它。我把三种常见的区间写法整理成了一张对照表：

闭区间写法最容易理解，但处理“找第一个大于等于x的数”这种问题时，左闭右开写法更不容易出错。原因在于r = mid这个操作不会跳过答案，而r = mid - 1一旦在mid等于答案时执行，答案就被丢出区间了。

举个实际翻车例子。有人用闭区间写lower_bound，写成下面这样：

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

这段代码在a[mid]恰好等于x时把r收缩到mid - 1，最终返回的l确实可能是第一个等于x的位置，但处理大量重复元素时极其容易绕晕。我用左闭右开模板很多年，很少在这种细节上翻车。所以在下面的内容里，除非明确说要精确查找某个值，不然统一用左闭右开。

2.3 lower_bound与upper_bound的C语言实现

竞赛里的二分查找，更多是配合排序解决“某个值出现几次”这类问题。C语言标准库虽然提供了bsearch，但它返回的是任意一个匹配位置，没法直接满足“统计重复次数”的需求。所以手写lower_bound和upper_bound是必备技能：

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

于是数字x在有序数组里的出现次数就是upper_bound(a, n, x) - lower_bound(a, n, x)。这里有个非常容易忽略的坑：lower_bound的返回值可能等于n，表示x比整个数组都大；upper_bound也可能返回n，表示所有数都小于等于x。如果你拿这个返回值直接去当数组下标，必越界。我早年写统计词频的程序时，就因为没判断返回n的情况，在PTA上反复爆运行时错误，后来养成了拿到返回值先看是否合法的习惯。

3. 二分答案：把最优问题转化为判定问题

3.1 什么时候能二分答案

P8088这种题，真正的核心不是二分查找数字，而是二分答案。二分答案解决的是一类看起来和“查找”无关的问题：题目要你求一个最优值，比如最小花费、最大距离、最短时间，而且这个最优值的可行性随着答案的变化是单调的——答案越大，越有可能满足条件，或者反过来，答案越小，越有可能满足条件。

用生活例子理解：你女朋友让你在预算内买礼物，预算越高，买得到满意礼物的可能性越大。如果我想知道“花多少钱才能让她满意”，我不用从一块钱开始慢慢试，我可以直接猜一个中位数，她说不够我就往高价猜，她说太多我就往低价猜。这个“往哪边猜”的依据，就是单调性。

放到算法题里，单调性通常表现为：设f(x)为“当答案限制为x时，能否完成目标”，那么f(x)必须是一个单调函数。如果x增大f(x)从false变成true，说明答案越小越难，这叫最小值最大化问题；反过来，如果x增大f(x)从true变成false，说明答案越大越难，这叫最大值最小化问题。看到题目里的“使最大值最小”或“使最小值最大”，直接往二分答案上想，基本不会错。

3.2 check函数的设计套路

二分答案最关键的部分是check(x)函数，它决定整个算法能不能跑对。check的任务是回答一个问题：在答案限制为x的情况下，方案是否存在。这个函数通常用贪心或模拟实现，复杂度最好是O(n)或O(n log n)，因为二分答案会在外层做log V次（V是答案值域），check每慢一点，总时间都会被放大几十倍。

设计check的核心技巧是“往前看”：从左到右扫描，能安排就安排，不能安排就换新的一段。比如经典题“把n个数分成m段，每段和不超过x”，check就直接累加，超了就开新段，最后看段数是否小于等于m。这种做法能保证在x的限制下，段数是最少的，所以如果最少的段数都超出m，x一定不可行。

很多新手写check时总想把方案也求出来，比如不仅判断能不能，还想知道具体怎么分。这个思路在二分答案里是多余的，你只需要回答“能不能”，具体方案留给原题需要的时候再说。把check写成一个干脆利落、只说“行还是不行”的函数，是二分答案题拿高分的秘诀。

3.3 最大值最小化与最小值最大化的代码模板

我把两个方向的二分答案模板都整理出来。第一个是“最大值最小化”，比如把一些工作分配出去，求最大耗时最小能到多少：

int l = 0, r = 1e9, ans = 0; while (l <= r) { int mid = l + (r - l) / 2; if (check(mid)) { ans = mid; r = mid - 1; // 当前可行，继续尝试更小的值 } else { l = mid + 1; // 不行，只能增大限制 } }

第二个是“最小值最大化”，比如在坐标轴上选k个点，让点与点之间最小距离尽量大：

int l = 0, r = 1e9, ans = 0; while (l <= r) { int mid = l + (r - l) / 2; if (check(mid)) { ans = mid; l = mid + 1; // 当前可行，尝试更大的值 } else { r = mid - 1; } }

这两个模板唯一的差别就是可行时往哪个方向收缩。很多人在考场上背混，然后对着数据发呆。我的办法是每次都在注释里写清楚“ans记录的是最后一个可行的值”，然后只记住一句话：能让答案继续变优的方向，一定是可行时移动的方向。

4. P8088题解思路推演与实战演示

4.1 没有完整题面时，怎么用标签反推套路

实话说，具体到P8088的原始题面，我不保证每一个细节都能一字不差复述出来。但这类社区赛题目有一个共性：题面给你一个具体场景，然后让你求一个最值，标签里的“二分查找”几乎在明示你应该用二分答案。拿到题先别急着看数据范围，先问自己三个问题：题目要求的最优值是什么？这个最优值变大时，条件会更容易还是更难满足？check函数能不能用一遍扫描判断？

把这三个问题想清楚，就算原题描述再花哨，骨架也已经出来了。Autumn这个主题，在算法题里最常见的包装是：一个序列上的值随时间递增或递减，然后让你找一个分界点，左边满足某个性质，右边不满足。这个分界点本身就是二分的对象。

4.2 一个Autumn风格的典型模型：落叶清扫问题

为了把二分答案讲透，我现场构造一个与Autumn气质相符的模型题。剧情是：一条长度为L的路上飘落了n片叶子，第i片叶子落在坐标a[i]处。清洁工从0出发，每趟可以清扫一段长度不超过x的连续区间，扫完一趟必须回0倒掉叶子。现在规定最多只能扫k趟，问清扫长度x至少要设置为多少。

这个问题要你求最小可行的x，属于最大值最小化，因为x越小越难完成，x越大越容易。单调性很明显：x增大，每趟能覆盖的范围变大，总趟数不会变多。check(x)的思路是：把叶子坐标排序后，从第一片没扫的叶子开始，每次从它所在位置往右覆盖长度x，这一趟就能扫掉区间内所有叶子，统计趟数，最后判断趟数是否小于等于k。

这里有个小细节：叶子坐标必须先排序，因为清扫区间天然要求坐标有序，题目给出的a[i]可能是乱序的。排序之后贪心覆盖才能保证趟数最少。如果直接拿原序扫描，check出来的趟数可能是错的，甚至可能导致合法的x被误判成非法。

4.3 完整C语言实现与手算演示

下面给出这个落叶清扫模型的完整实现，代码可以直接改改用于P8088这类二分答案题：

#include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } int n, k; int a[100005]; // 判断当每趟清扫长度为x时，能否在k趟之内扫完 int check(int x) { int cnt = 0; int i = 0; while (i < n) { cnt++; int cover_end = a[i] + x; while (i < n && a[i] <= cover_end) i++; if (cnt > k) return 0; } return 1; } int main() { int L; scanf("%d%d%d", &n, &k, &L); for (int i = 0; i < n; i++) scanf("%d", &a[i]); qsort(a, n, sizeof(int), cmp); int l = 1, r = L, ans = L; 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; }

我用手算模拟一遍加深理解。假设叶子坐标是1、4、7、12、20，n=5，k=3。先看mid可能取到9：从1开始清，覆盖到10，所以前三个叶子1、4、7一趟清掉；下一趟从12开始，覆盖到21，把12和20都清掉。总共2趟，小于等于3，可行。于是收缩r，尝试更小的x。再看x=6：第一趟1覆盖到7，清掉1、4、7；第二趟从12覆盖到18，清掉12；第三趟从20覆盖到26，清掉20。正好3趟，可行。继续缩小。x=5时：第一趟1覆盖到6，清掉1、4；第二趟从7覆盖到12，清掉7、12；第三趟从20覆盖到25，清掉20。正好3趟，也可行。那x=4呢？第一趟清1、4，第二趟清7，第三趟清12，第四趟清20，4趟超了，不可行。所以最小x就是5。

通过这个手算过程你能直观看到，二分答案并不是什么高深技巧，它就是把这个“从4不行到5可行”的分界点找出来。P8088无论场景换成温度还是距离，底层逻辑都是这一套：排序、贪心check、二分边界。

5. 从竞赛到平台：PTA函数题与工程化写法

5.1 PTA二分查找函数题的经典模板

很多读者搜“二分查找pta函数”，是因为学校布置了PTA上的函数题。这类题的经典形式是给你一个有序链表结构体或者数组结构体，让你实现一个BinarySearch函数，接口看起来像这样：

Position BinarySearch(List L, ElementType X)

其中List是一个结构体指针，结构体里存着Data数组和Last变量，Last表示数组最后一个元素的下标。这道题的本质和一个裸数组二分没有区别，但有两个坑：第一，题目为了统一接口，Data数组下标从1开始，Last存的是最后一个元素的位置，所以右边界是L->Last而不是L->Last - 1；第二，查找失败时需要返回一个约定的NotFound宏，通常定义为0。

一个适配这种接口的标准写法如下：

Position BinarySearch(List L, ElementType X) { int l = 1, r = L->Last; while (l <= r) { int mid = l + (r - l) / 2; if (L->Data[mid] == X) return mid; else if (L->Data[mid] < X) l = mid + 1; else r = mid - 1; } return NotFound; }

很多人在这个函数题上挂分，不是因为二分不会写，而是没看明白接口约定：到底下标从0还是从1开始。我的建议是写函数前先确认Last的含义，如果题目说“Last表示最后一个元素的位置”，大概率下标从1开始。PTA的判题比较死板，错了不会告诉你具体数据，所以这种边界细节必须靠自己抠清楚。

5.2 手写二分与标准库的取舍

工程实践中，C语言标准库提供了bsearch函数，配合qsort使用，可以做二分查找。但bsearch有两个问题：它只返回任意一个匹配位置，无法直接处理“统计重复元素个数”的需求；其次，bsearch的比较函数签名比较繁琐，对新手不友好。所以手写lower_bound和upper_bound在面试和竞赛中依然是硬技能。

C++选手可以直接用STL里的binary_search、lower_bound、upper_bound，但在C语言环境下，手写是唯一选择。我建议你把第2小节的三个函数背到肌肉记忆：binary_search、lower_bound、upper_bound。这仨在打比赛时就是你的左膀右臂，连键盘都不用看就能敲出来。

5.3 二分查找的复杂度分析与实际耗时

二分查找单次的时间复杂度是O(log n)。之所以快，是因为每次比较都能排除一半的候选区间。从4096个数里找一个数，最坏也只需要12次比较，这个效率是线性查找完全没法比的。

二分答案的复杂度要乘以check的复杂度：O(log V)次二分乘上每次O(n)的check，就是O(n log V)，其中V是答案的值域。如果题目给的坐标范围是10^9，log V大约是30，再乘n等于100000的话，大概300万次运算，在1秒时限内非常轻松。这也是为什么普及+难度的二分答案题不需要优化check到O(log n)，O(n)的check已经足够快了。

6. 常见问题与排查实录

6.1 死循环：mid的取整方向惹的祸

二分题死循环是新手最常遇到的现象，典型症状是程序卡在那里不结束。最常见的病根是左边界的更新方式写成了l = mid，配合mid = (l + r) / 2向下取整时，如果l和r只差1，mid就会等于l，更新后l还是原来那个值，区间不收缩，循环永远跑不完。

解决死循环的办法有几个。第一个办法是在纸上模拟区间只有两个元素时的情况，比如l=5, r=6，看看这一轮操作后区间能不能缩小。第二个办法是把循环条件改成l < r而不是l <= r，配合左闭右开区间，记忆负担会小很多。第三个办法是在循环里加一个计数器，超过100次直接终止，调试阶段用这个办法能快速定位问题。

6.2 边界错误：mid - 1和mid + 1谁该用

边界更新错误是二分题另一大类bug。很多人不敢在收缩区间时加减1，怕把答案漏掉，结果写成了l = mid或者r = mid，导致死循环或者答案不对。其实只要你维护好了“答案永远在[l, r]区间内”这个不变量，该加1就加1，该减1就减1，完全不用担心漏答案。

我排列一个速查表：

这个表配合ans变量，能解决绝大多数边界问题。核心原则是：mid已经判断过了，它不可能再是下一步的候选答案，所以更新时一定要让mid退出区间。

6.3 check函数不单调，二分直接失效

如果check函数本身不满足单调性，二分答案就是空中楼阁。比如某些题的条件是“x必须恰好等于某个数”，这时候check(mid)的结果可能是true、false、true交替出现，二分完全没法收敛。遇到这种情况，要警惕题目其实不是二分答案，而是别的算法，比如前缀和加哈希，或者数学推导。

一个小技巧是：写check之前，先用小数据把x从小到大都测一遍，打印出check(x)的true/false变化序列。如果这个序列是连续的true之后接连续的false，或者反过来，二分才能成立。这一步只要花一分钟，能省掉改半天代码的时间。

6.4 调试技巧：对拍、打印区间、极限数据

调试二分题，我最常用的三招。第一招是打印区间：在循环开头打印l、r、mid，看一眼区间收缩的方向对不对，几个数就能看出问题。第二招是对拍：写一个纯暴力的枚举解法，然后在n很小的时候跟二分做法对比结果。第三招是极限数据：把答案推到题目允许的极小值和极大值，确认check在边界情况下不会越界、不会除零、不会溢出。

这三个方法看起来土，但比冥想管用一百倍。我平时给学生讲题，一律要求他们先打暴力再写正解，两道代码对上了才提交。二分题尤其适合这种流程，因为它的逻辑容易在细节上出错，而对拍能自动暴露这些错误。

我个人的体会是，二分查找本身不是难点，难点永远是“敢不敢把最优问题交给一个不直接求答案的算法”。很多选手第一次接触二分答案，会有一种“我都没算出方案，这答案怎么就出来了”的别扭感。这种别扭是正常的，多刷几道题就顺了。如果你正卡在P8088这种普及+的二分题上，照着这篇文章的步骤走：找单调变量、写check、套模板、对拍验证。做完这四步，你收获的不只是一道题的AC，而是一整套处理“求最值”问题的方法论。