要说算法学习里最像“玄学”的二分查找绝对排得上号。代码就那么几行教科书也讲得清清楚楚可一到PTA的“二分查找-I”这种函数题或者面试手写环节还是有大批人栽在边界条件上——死循环、答案错一位、变体不会写什么幺蛾子都有。我当年刷这道题时反反复复改了七八版才真正把区间、循环条件和返回值三件事搞明白。这篇就把我踩过的坑和最终沉淀下来的套路一次说清楚。不管你是在校生刷PTA还是准备算法面试按这个思路走二分查找基本不会再出错。1. 二分查找到底在查什么1.1 一次比较砍掉一半二分的思想二分查找的原理用一个猜数字游戏就能讲透。我在1到100里想一个数你每猜一次我会告诉你“大了”还是“小了”那么你最多猜几次答案是7次。因为每次猜测都把候选范围砍掉一半100变成50再变成25一路缩到1。这个数学过程写出来就是 log₂(100)≈7。把游戏搬到有序数组里就是标准二分取中间位置mid把a[mid]和target比较。相等就返回a[mid]小于target说明target只可能出现在右半段a[mid]大于target说明只可能在左半段。每比较一次问题规模减半。这比从头到尾一个个找的线性查找快得多尤其是数据量大的时候差距是压倒性的。100万个有序元素里找某个值线性查找平均要走50万次二分最多20次。很多人到这一步都明白但真写代码就翻车。原因在于二分查找的核心不是“取中间”而是“每次比较之后能不能确定性地抛弃掉一半搜索空间”。这个前提极其重要它决定了你能不能在某个问题上用二分也决定了边界怎么写才不会乱。1.2 有序只是表象单调可判定才是前提教科书喜欢说“二分查找要求数组有序”这句话对但容易让人产生思维定势。我在竞赛里见过不少人把“数组有序”当成唯一条件结果碰到“在函数值域上二分答案”“找旋转数组最小值”这类题目就不知道该怎么套了。实际上二分能用需要满足三个条件顺序存储、随机访问、单调可判定。数组占前两条链表虽然也有顺序但访问第k个元素要O(k)时间二分在链表上每跳一次都这么贵整体复杂度退化成O(n)还不如顺序遍历。第三条是灵魂你要能写出一个判定函数check(mid)而且这个check的结果必须是单调变化的比如一堆false之后全是true或者一堆true之后全是false。只要满足这个模式不管查的是数组元素、日期还是浮点数都能用二分。PTA的“二分查找-I”只是最基础的数组形态但你把“有序数组”抽象成“单调可判定序列”之后后面遇到二分答案、浮点数二分、找左右边界都顺理成章。这也是为什么我一直建议新手别看一堆花哨模板先把“判定函数”这个思维立起来。后面第三部分我会把这种思想落地成代码模板。2. 边界写法所有二分错误的根源2.1 左闭右闭和左闭右开两种区间两种写法二分查找的代码网上能搜出十几种看着一样细节全在区间定义。我观察了很久90%的人写错都是因为在动手前没明确“我现在维护的区间是闭区间还是半开区间”。这个问题的答案决定了循环条件、边界更新和循环结束时的状态。第一种写法左闭右闭区间是[l, r]int binarySearch(int a[], int n, int target) { int l 0, r n - 1; // 闭区间 [l, r] while (l r) { int mid l (r - l) / 2; if (a[mid] target) return mid; if (a[mid] target) { l mid 1; } else { r mid - 1; } } return -1; }这个写法最符合日常数组下标习惯l和r都是有效下标所以循环条件是l r意思是“只要区间里还有元素就继续”。当l r退出循环区间已经空了target不存在。第二种写法左闭右开区间是[l, r)int binarySearch(int a[], int n, int target) { int l 0, r n; // 半开区间 [l, r) while (l r) { int mid l (r - l) / 2; if (a[mid] target) return mid; if (a[mid] target) { l mid 1; } else { r mid; } } return -1; }这里r不包含在区间里所以初始r n循环条件是l r退出时l r区间收缩成一个空位。注意当a[mid] target时r可以直接收成mid因为mid已经检查过了而且右区间是开区间r mid就不会把mid重复包含进去。我自己的习惯是竞赛里优先用左闭右开因为后续写lower_bound语义几乎无缝衔接。但PTA“二分查找-I”这道函数题我反而推荐左闭右闭根本原因是题目给了Last这个“最后一个元素下标”天然就是个闭区间端点。记住先定区间再写代码所有分支就都有依据了。2.2 mid 计算的溢出陷阱和向上取整场景mid (l r) / 2 是另一个经典隐藏坑。l和r都是int如果数组很大l r可能超过int上限变成负数mid就错了。虽然平时练习数据规模小不容易触发但面试官考你的时候这个问题几乎必问。正确写法是 mid l (r - l) / 2把加法换成减法规避溢出。再补充一个优先级坑mid l (r - l) 1 在C/C里的等价写法是 (l (r - l)) 1不是你心里想的 l ((r - l) 1)。位移运算的优先级比加减法低所以要把右移部分用括号包起来mid l ((r - l) 1)。还有一个更隐蔽的点关于mid向上取整。当你写循环更新时出现“l mid”这种分支mid必须向上取整否则可能死循环。举个例子区间收缩到[2, 3]l2r3向下取整mid (23)/2 2。如果某个分支写的是l mid那l还是2区间永远不变程序卡死。解决办法是用 mid l (r - l 1) / 2 让mid取上中位数变成3。我在找右边界的时候踩过这个坑以后只要看到l mid就条件反射地检查mid是不是向上取整。3. 一个模板收敛所有二分变体3.1 把查找改成找第一个满足条件的位置二分不只是“找等于target的下标”它真正擅长的是各种边界查找第一个大于target的位置、最后一个小于等于target的位置、第一个大于等于target的位置。很多新手一遇到“第一个”“最后一个”就重新写一套逻辑结果一写就乱。我推荐把所有二分收敛成一个模板。先理解一个事实任何一个有序数组上的二分问题都能改写成“找第一个满足check(mid)的位置”。比如精确查找X等价于找第一个Data[i] X的位置然后验证这个位置上的值是不是X。// check(mid) 必须是单调的false, false, ..., false, true, true, ... // 查找区间 [l, r)返回第一个 check 为 true 的下标 int firstTrue(int a[], int l, int r, int target) { while (l r) { int mid l ((r - l) 1); if (a[mid] target) { // 这里就是 check r mid; } else { l mid 1; } } return l; }check(mid)成立时mid可能是答案也可能是答案右侧的某个点所以把右边界收成r mid保留mid不成立时mid不可能是答案直接l mid 1排除。退出时l就是答案。为什么用左闭右开因为“保留mid”用r mid表达很自然而“排除mid”用l mid 1表达也很自然两种操作不对称半开区间正好把这两种不对称性都消化掉了。3.2 精确查找、左边界、右边界的统一实现有了firstTrue所有变体都能映射到不同的check上。需求check(mid)返回位置的含义精确查找targeta[mid] targetl还要验证a[l] target第一个 targeta[mid] targetl第一个 targeta[mid] targetl最后一个 target先找第一个 target结果减1l - 1最后一个 target先找第一个 target结果减1并验证l - 1举个例子数组是[1, 3, 5, 7, 7, 9]要找第一个7。check用a[mid] 7。第一次mid 2a[2] 55 7不成立l 3。第二次mid 4a[4] 7成立r 4。第三次mid 3a[3] 7成立r 3。退出时l r 3这正是第一个7的下标。整个过程没有单独处理“等于”的分支等于的情况被“”这个check自动包含了干净利落。找最后一个7也简单先找第一个大于7的位置也就是check用a[mid] 7得到下标5然后减1得到4就是最后一个7的下标。这个技巧比单独写一套“找最后一个等于”的二分稳得多。精确查找同样可以这样组合先找第一个X的位置pos然后判断pos是否越界且a[pos] X。如果X不存在firstTrue返回的是第一个大于X的位置验证失败返回-1。我后来写二分全是这个套路再也没有因为“等于”分支写错过。3.3 和 STL lower_bound/upper_bound 的对照C里的lower_bound和upper_bound其实就是上表的两个核心变体很多新手搞不清这两个函数用我前面这套区间概念去记忆会非常顺lower_bound返回的是第一个 target的元素upper_bound返回的是第一个 target的元素。两者之间的范围就是序列中所有等于target的元素。我平时面试手写二分时都会顺口说一句“这就是手写版lower_bound”面试官马上就知道你理解了本质。这也是我强烈建议你吃透统一模板的原因它把复杂的边界问题收敛成一个单调判定问题工作量全在写check上。后面遇到二分答案题check甚至可以不是数组比较而是模拟一次贪心或者检查一个可行性条件但外层框架还是这个firstTrue换汤不换药。4. PTA“二分查找-I”函数题实战拆解4.1 题目结构里最容易误读的 LastPTA数据结构课程的经典函数题“二分查找-I”题面大概是给定一个已经按非降序排好的线性表实现二分查找函数返回X在表中的下标找不到则返回NotFound。线性表结构一般是这个模样#define MAXSIZE 10 typedef int ElementType; typedef int Position; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data[MAXSIZE]; Position Last; // 线性表的最后一个元素的下标 }; typedef PtrToLNode List;很多初学者第一眼看到的数据结构题最大的坑就在Last这个成员上。它存的是“最后一个元素的下标”不是元素个数。如果Last等于9说明表里有10个元素下标范围是[0, 9]。一旦你把Last当成数量n来用初始化写成right Last而实际期望“元素数量是Last个”整个查找范围直接错位返回的下标全是错的。还有一点有些同学为了省事自己定义结构体结果和judge程序的定义冲突。函数题里你只需要提交函数实现和必要的辅助内容结构体定义、MAXSIZE、NotFound这些通常由裁判程序提供重复typedef会导致编译错误。如果你拿不准优先只提交BinarySearch这一个函数体。4.2 完整代码与本地测试五步法基于上面的结构我推荐用左闭右闭写法因为Last天然是闭区间的右端点。代码很直接Position BinarySearch( List L, ElementType X ) { Position left 0; Position right L-Last; // 关键Last 是最后一个元素的下标 while (left right) { Position mid left (right - left) / 2; if (L-Data[mid] X) { return mid; } else if (L-Data[mid] X) { left mid 1; } else { right mid - 1; } } return NotFound; }注意访问结构体指针成员要用L-Data[mid]而不是L.Data[mid]这个编译错误我见过太多人犯了。Data是结构体里的数组名L是指向结构体的指针直接用点号访问会在编译器阶段就报错。本地测试建议走五步第一步把结构体定义、NotFound常量、函数原型原样复制到本地C文件里再补一个main函数。第二步构造几组测试数据比如有序数组、单元素数组、空表、目标值小于最小值、目标值大于最大值、目标值不存在但落在值域中间。第三步主函数里循环调用BinarySearch并打印返回下标。第四步跑一遍逐个核对预期输出。第五步确认无误后只把BinarySearch函数体复制到PTA提交框。一个本地测试的完整骨架长这样#include stdio.h #define MAXSIZE 10 #define NotFound -1 typedef int ElementType; typedef int Position; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data[MAXSIZE]; Position Last; }; typedef PtrToLNode List; Position BinarySearch( List L, ElementType X ); int main() { struct LNode L; ElementType arr[] {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int n 10; L.Last n - 1; // 最后一个元素的下标 for (int i 0; i n; i) L.Data[i] arr[i]; printf(找 11: %d\n, BinarySearch(L, 11)); // 5 printf(找 10: %d\n, BinarySearch(L, 10)); // -1 printf(找 1: %d\n, BinarySearch(L, 1)); // 0 printf(找 19: %d\n, BinarySearch(L, 19)); // 9 return 0; }这段代码一跑正确返回分别是5、-1、0、9你就知道函数实现没有大方向问题。剩下的边界用例再补一补一个单元素表一个Last0的表一个目标小于所有元素的用例基本就能覆盖最危险的边界。4.3 提交前必须绕开的在线判题坑在线判题系统里最经典的翻车行为是把调试用的printf留在提交代码里。本地测试你打印l、r、mid没关系但提交到OJ你的函数输出会混进答案输出轻则格式错误重则全判错。我见过有人拿着“本地全对OJ零分”的代码来找我最后发现就是残留了一行printf。另外一个容易被忽视的点在PTA函数题里题目给的ElementType不一定是int。有的变体题会用浮点数或者结构体判断大小就不能直接写和。我见过一道题把ElementType定义成结构体里面存学号和成绩让你按成绩二分。这时候L-Data[mid] X这种写法就是灾难必须改成L-Data[mid].score X.score。看起来是小改动但如果你习惯了int数组的写法遇到这种题第一反应往往不是这里出问题。最后一个经验提交之前再读一遍题目要求确认NotFound常量名和返回值类型。有的版本把NotFound定义为-1有的版本直接在题目里写“return -1”你用变量名应该跟题面保持一致。如果题目明确要求直接用整数-1那函数里写return -1比return NotFound更稳妥。这一步花十秒钟能省一次提交机会。5. 常见问题速查与调试实录5.1 死循环、错位返回、越界三个典型症状我把平时被问到最多的三种二分错误整理成一张速查表先判断症状再对症下药。症状可能的原因解决方向程序超时或卡死mid向下取整但某个分支写成l mid区间不缩小检查所有l mid的分支改用mid向上取整返回下标总是差1区间定义混用了闭区间和半开区间边界更新不对称写之前显式注释区间类型统一成一种写法数组越界访问初始r n但没注意mid会不会等于r或错误使用a[r]判断关闭区间时保证mid r不要直接判断a[r]目标存在但返回-1等于分支处理错误或Last含义误用成元素个数用firstTrue模板统一成“”判定再验证本地对、OJ零分残留printf、多余结构体定义、常量名不一致提交前删调试输出只提交函数体死循环是我最常被问的。用两个元素的数组[2, 3]测试最容易复现我在2.2节说的向上取整问题就是典型场景。遇到这种情况先不要改逻辑把l、r、mid打印出来看两个循环内的变化基本一眼就能定位。错位返回通常出在“找第一个/找最后一个”的变体里。新手喜欢把等于单独拿出来处理比如a[mid] target时还要再判断一次左右边界结果逻辑越加越乱。换成我第三部分推荐的check模板等于的情况根本不用专门写全部交给“”或“”两个判定就完了。越界问题相对少出现但一出现就是致命错误。左闭右开写法的初值r n本身是安全的因为循环条件l r保证了mid r nmid永远不会等于越界的下标。真正的风险是你自己手欠写了个“if (a[r] target)”在区间收缩过程中r可能直接等于n于是访问越界。记住数组访问全部通过mid完成不要碰l和r。5.2 我的二分调试三板斧第一板斧是短数组打印。我调试二分时习惯用一个4到6个元素的数组在每次循环里打印l、r、mid和a[mid]的值然后手动验证一遍更新方向。物理学家费曼有个说法每算一步都把数字写下来问题会自己现形。二分也一样靠脑内模拟不如把中间量拿出来看。第二板斧是随机对拍。写一个暴力函数从左往右扫数组找答案再写一个随机数据生成器生成几百组有序数组和随机target把二分结果和暴力结果逐一对比。有任何一个case不一致立刻缩小数据范围复现。这个方法不仅可以验证二分还能反向验证你对题目的理解。我在PTA函数题上遇到“返回值到底是下标还是第几个位置”这种疑惑时都是用对拍把行为测出来的。第三板斧是三种写法互相验证。我练二分时会把同一个需求分别用左闭右闭、左闭右开、统一模板各写一遍然后跑同一组测试数据。三份代码结果一致说明逻辑基本没问题结果不一致对比中间量的差异就能找出是哪个地方的定义没对齐。这个过程看起来很笨但对培养“区间直觉”特别有效。最后分享一个我个人一直在用的小技巧给二分写的check函数单独命名不要直接内联在if条件里。比如写成bool check(int mid)里面return a[mid] target这样代码可读性高了而且未来扩展到二分答案题时你只需要替换check的实现外层循环一行不用动。我从PTA刷到笔试再到面试完全靠着这个习惯二分再也没写崩过。