聊到二分查找很多人的第一反应是“不就是在一个有序数组里找一个数嘛写个 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 保存的就是最左边的命中下标如果整个数组里没有 targetans 一直是 -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 初始化就应该是 1r 初始化是 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 起步用 ans0 兜底。吃透这一道题就能迁移到分巧克力、装船问题、机器人搬砖等一大类二分答案题。它们共同点都是不直接求最优值而是判断某个猜测值是否可行然后反复二分直到逼近答案。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[mid1]说明 mid 左侧一定存在峰值反之说明右侧一定存在峰值因为至少 mid1 有可能是峰值。于是每次都能排除一半。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[mid1] 时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 二分题的主要错误类型。典型症状常见原因修复方式程序卡死不输出mid 更新导致区间不缩小检查是否出现 lmid 或 rmid 且 mid 不变统一用 l(r-l)/2返回下标差 1下标起点理解错误确认 0-based/1-based以及 r 初始值是 n-1 还是 n答案错误但样例全过没有处理重复元素的“第一个/最后一个”用 ans 记录候选值别着急 return运行错误/内存越界mid 用 (lr)/2 导致整型溢出改用 l(r-l)/2必要时用 long long 参与计算输出多余内容函数题里写了 printf 调试提交时只留函数体删掉调试输出死循环问题是重灾区。如果使用左闭右闭 [l,r]循环条件是 l r每次进入循环后 mid 至少会让 l 或 r 发生移动理论上不会死循环。但如果你用 l r又把 mid (lr)/2更新时写成 l mid 或 r mid那么当区间缩到两个相邻元素时mid 可能永远等于 l区间就不再缩小。比如 l2, r3 时 mid2如果更新到 lmid区间就永远停在 [2,3]。解决办法是左闭右闭时用 lmid1 或 rmid-1左闭右开时用 lmid1 和 rmid。绝对不能 l 和 r 都保持不变。6. 我把二分写对的私有方法论6.1 三个问题定下循环不变式我自己现在写二分动手前固定问三个问题。第一答案可能存在的区间是什么第二这个区间用左闭右闭还是左闭右开第三当中间值不满足条件时下一次搜索区间应该排除哪一半把这三个问题答完代码基本就出来了。举个例子找“第一个大于等于 target 的位置”。答案区间是 [0, n]其中 n 是数组长度因为可能不存在这样的元素。我选左闭右开 [l, r)l 初始化为 0r 初始化为 n。循环 while (l r)mid l (r-l)/2。如果 a[mid] target说明 mid 可能就是要找的第一个位置而且答案不会在 mid 右边于是 r mid否则 a[mid] targetmid 不可能是答案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 (lr) 的循环里写 rmid-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), kn)) 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不要依赖循环结束后对 lr 复杂判断。第三把 check 函数单独抽出来写不要和二分主逻辑混在同一行出问题方便调试。第四提交前删掉所有调试输出。第五题目里出现“非递减”而不是“递增”时默认可能有重复元素该用边界二分就用边界二分别心存侥幸。写了这么多我个人其实还是在“左闭右闭 ans 记录”这个风格上最顺手因为它跟普通查找模板最接近不容易出错。但你完全可以选左闭右开只要保持前后一致就没问题。二分查找的代码可以很短但短代码越容易在边界上翻车。有了不变式意识加上对拍验证再复杂的变体也能稳稳拿下来。希望这篇实战总结能少让你受一点 WA 的折磨。