二分查找这个算法很多人觉得自己早就掌握了不就是“对一个有序数组每次取中间值比较一下缩小一半范围”嘛。可实际上我在带学生和帮朋友排查面试题的几年里发现二分查找反而是翻车率最高的题目之一。尤其是经常能在各种平台上看到“二分查找pta函数”这种搜索词说明大批同学正在PTA上被这道经典函数题折磨。今天这篇就以“二分查找-I”为切入点把核心思想、边界处理、PTA函数题实现和常见坑一次讲透希望能让你真正吃透这五分钟就能学会、却要花很久才能写对的算法。1. 二分查找的核心思路从猜数字到区间收缩1.1 猜数字游戏的本质假设有人让你猜一个1到100之间的整数你每猜一次对方只告诉你“大了”还是“小了”。你会怎么猜正常人都会先猜50如果大了范围直接缩到1到49如果小了范围变成51到100。无论答案是什么一次猜测都能排除一半可能性这就是二分查找最朴素的思想。这个游戏背后隐藏的数学规律很值得咀嚼初始有n个可能值每猜一次剩余可能值减半减到只剩下1个的时候你就锁定了答案。猜的次数k满足 n / 2^k ≤ 1也就是 k ≥ log₂(n)。n100时log₂(100)约等于6.64所以7次以内必定猜中。一千万个数呢log₂(10000000)约等于23.2524次就够。这种增长速度肉眼可见地慢是二分查找效率高的根本原因。理解到这个层面你就会明白二分查找不是“背模板的算法”而是一种信息论层面的策略每次都利用有序性获取“目标在左还是在右”这一比特的信息逐步收敛解空间。写代码时所有细节包括边界怎么改、循环条件怎么写本质上都是为了保证“区间收缩”这个过程不出错。1.2 二分查找能工作的三个前提很多人拿着二分模板到处套结果在无序数组上跑出错误答案回头怀疑自己代码写错了其实是前提没满足。二分查找成立需要三个条件缺一不可。第一数据必须有序。这个“有序”可以是单调递增也可以是单调递减甚至可以是非严格增减有重复值但必须保证你能够通过一次比较确定目标在哪一侧。日常理解就是你要在电话簿里找“张”姓朋友就必须按拼音排好序不然只能从头翻到尾。第二必须支持随机访问。二分查找每次要直接跳到中间位置所以底层必须是数组这种可以用下标O(1)定位的数据结构。链表不行因为找中间节点要O(n)遍历整体复杂度就退化成了O(n log n)不如直接遍历。第三元素之间可比。任何一次if判断都依赖“大于”“小于”“等于”这三种关系如果你处理的数据不能比较大小比如自定义结构体没有定义排序规则那就先给它定好序再说。这三点里初学者最容易忽略的是“数组有序”这个前提。刷题时题目通常会明说但在真实项目中你要自己保证调用二分查找前数据确实有序。我见过不止一个同事往一个动态增长的数组里不停插入新数据却不重新排序然后二分查找返回了诡异的结果排查了半天才发现是数据新鲜度的问题。2. 手写二分三种典型写法与边界处理2.1 先看懂区间定义左闭右闭还是左闭右开代码怎么写是表象区间怎么定义才是根源。写二分之前你必须先回答一个问题当前搜索范围[left, right]里的left和right到底是“数组下标”还是“下标1”是“包含right指向的元素”还是“不包含”最常见的是左闭右闭区间也就是[left, right]表示搜索范围包含right位置的元素。此时初始化是left0, rightn-1循环条件是while (left right)因为当leftright时区间里还有一个元素需要检查不能直接退出。另一种是左闭右开区间写作[left, right)搜索范围包含left但不包含right。初始化变成left0, rightn循环条件是while (left right)当leftright时区间为空已经不需要再查。这种情况下right可以等于n因为n这个下标本来就不在合法范围内。这两个定义没有谁绝对更好但你必须全程保持一致。我见过最多的错误就是初始化用了左闭右开更新right时却用了右闭的写法rightmid-1导致跳过了一个元素或者初始化用了左闭右闭循环条件却写成了left right导致最后一个元素永远查不到。区间定义不明是边界错误的总根源。2.2 左闭右闭模板逐行拆解我推荐初学者先掌握左闭右闭的写法因为它的三个分支最直观相等返回、小于走左边、大于走右边。下面是最基本的实现int binarySearch(int nums[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }为什么nums[mid] target时是left mid 1而不是left mid因为mid这个位置已经检查过了它不可能是目标所以搜索区间应该从mid的下一个位置开始。同理nums[mid] target时mid也不可能是目标right要缩到mid-1。这种“排除已检查位置”的思路能帮你避免很多死循环。mid的写法也有讲究。我故意写成了left (right - left) / 2而不是(left right) / 2。原因很简单当数组规模很大时left right可能超出int的表示范围产生溢出导致mid变成负数。这在面试和竞赛中是一个经典考点用减法替代加法既安全又效果相同。如果你用Python这类大整数语言写第一种也不会错但好习惯还是早点养成为妙。2.3 左闭右开模板与对比左闭右开在C标准库里很常见比如STL里的lower_bound、upper_bound都基于这个区间定义。它的代码长这样int binarySearch(int nums[], int n, int target) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid; } } return -1; }注意这个模板里的两个区别初始化时right n因为n不在搜索范围内当nums[mid] target时right mid而不是mid-1因为right本身就不包含在区间内所以mid可以直接作为新的右边界。这个模板不会死循环原因值得单独说一下。在left right的前提下mid left (right - left) / 2由于整数除法向下取整mid一定小于right当区间长度为1时比如left3, right4mid3更新leftmid1后变成left4循环结束。所以永远不需要担心left和right卡住不动。对比项左闭右闭 [left, right]左闭右开 [left, right)初始化left0, rightn-1left0, rightn循环条件left rightleft rightmid偏小时向右left mid 1left mid 1mid偏大时向左right mid - 1right mid区间为空标志left rightleft right我个人建议日常刷题或面试时固定用左闭右闭模板因为它和人类的自然直觉更接近判断也少一个弯而读源码或做边界变种题时要能看懂左闭右开写法的逻辑。两种都要练到但不必强求混用。3. PTA函数题从接口定义到完整实现3.1 读题先读接口List结构暗藏玄机很多人在PTA上做“二分查找”这道函数题时代码逻辑明明没问题却一直Wrong Answer问题往往出在没读懂题目给的接口。PTA这类题通常不会让你自己写main函数而是要求你补全一个特定的函数实现所以先搞清楚参数含义比急着写代码重要得多。以经典的PTA二分查找题目为例接口通常会定义成下面这样typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; Position BinarySearch(List L, ElementType X);这道题有几个非常容易踩的点。第一Data从下标1开始存有效数据Data[0]通常闲置不用Last保存的是最后一个有效元素的下标而不是元素个数。第二Position是一种typedef本质上是int返回的应该是找到元素的下标找不到则返回NotFound这个宏通常是0。第三ElementType不一定就是int具体是什么需要看题目说明有些版本里ElementType是int的别名有些则可能是其他类型。你要养成一个习惯拿到任何编程题先花两分钟把所有typedef、结构体定义、宏定义读一遍再把“返回什么”“找不到怎么办”在注释里写出来再去动键盘。我教过的学生里凡是反复WA的十有八九是没搞清楚Last是“位置”不是“长度”或者把下标从1开始当成了从0开始。3.2 完整实现下标从1开始的二分查找针对上一节说的接口一个能直接提交的完整实现如下Position BinarySearch(List L, ElementType X) { if (L NULL) { return NotFound; } Position left 1, right L-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 NULL的判断PTA的测试用例里可能传入空指针不判空可能会导致运行时错误比如段错误。不要觉得“题目一定不会给空表”严谨的函数是任何状态下都该安全返回的。第二个是初始化left1, rightL-Last。因为Data的下标从1开始有效Last是最后元素的下标所以这正好对应一个左闭右闭区间[1, Last]。循环条件while (left right)当left right时区间里还有那一个元素必须查。如果漏了等号最后一个元素永远找不到。第三个是返回值的语义。当找到时返回mid也就是元素在数组中的下标当找不到时返回NotFound通常是0。请务必对照题目确认NotFound的具体值有的习题可能定义为-1直接用题目给的宏名就好不要自己写魔法数字。3.3 提交前的自测用例写完PTA函数题不要急着直接点提交。先在本地或者记事本里手推两个小用例能省下至少三次无效提交。假设Data数组是[_, 1, 3, 5, 7, 9]_表示下标0处闲置Last5。查找目标是5。初始left1, right5mid3Data[3]正好是5返回3正确。查找目标是1。第一次mid3Data[3]是5比1大所以rightmid-12第二次mid1Data[1]是1返回1。查找目标是9。第一次mid3Data[3]是5比9小leftmid14第二次mid4Data[4]是7还是比9小left5第三次mid5Data[5]是9返回5。查找目标是4。经历类似最后一次mid3后Data[3]5比4大right变成2此时left3left right循环结束返回NotFound。这四个用例分别覆盖了“正中间命中”“最左侧命中”“最右侧命中”和“完全不存在”四种情况手推一遍就能确认边界逻辑没有问题。时间复杂度是O(log n)因为每次循环范围减半空间复杂度是O(1)因为只用了常数个变量。如果面试官追问一定要回答出这两点。4. 常见坑与排查技巧实录4.1 死循环肉眼最难看出来的问题我见过太多人写二分一提交就超时一看代码问题基本都出在left更新上。最常见的死循环写法是这样的if (nums[mid] target) { left mid; // 错误 }为什么错假设当前left3, right4mid3整数除法向下取整nums[3]确实小于target于是leftmid还是3。下一次循环left3, right4mid还是3就永远跳不出去。这就是“left没有前进”的经典死循环。排查死循环最快的方法不是盯着代码看而是找一组“区间长度只有2”的数据手动走一遍。因为一切死循环最终都表现为某个边界上不断重复。你在自己机器上调时可以打印每次的left、right、mid三个值一旦发现连续两轮完全相同立刻就能锁定是哪一行赋值出了问题。4.2 mid计算溢出面试官爱挖的坑写成(left right) / 2在绝大多数小数组上没有任何毛病因为根本溢不出来。但如果你处理的是一个非常大的数组比如长度接近2^31-1那么left right就可能超过int上限变成一个负数mid自然也就错了。正确写法是left (right - left) / 2。理解它也很简单先求出[left, right]这一段的一半长度再把它加到left上这样每一步操作都不会超过right的范围自然也不会溢出。Python、Java的有些场景也记得用这个习惯好习惯能让你少一个潜在的bug。4.3 找不到目标时的返回值别自己想当然普通数组版本的返回-1已经是行业习惯但PTA和许多C语言题目不这么玩。PTA里的NotFound宏经常被定义为0因为下标从1开始0本身就是一个不存在的“无效下标”用它做“没找到”的标记非常自然。所以写任何二分查找之前先确认三件事数组下标从0开始还是从1开始没找到时返回-1、0还是某个特殊值如果有重复元素返回的是任意一个还是最左最右。这三点只要题目里有一句“详见函数接口定义”你都要一字不差地看清楚。不然你写了一个看起来完美的二分却在返回值上栽跟头那可比算法不会写更可惜。4.4 PTA提交常见的编译与逻辑问题PTA的函数题只让你补全函数但不代表你提交的代码只有那一段。很多同学写完了函数编译却报错通常都是下面的问题。第一没有把题目给出的结构体定义包含进自己的代码。PTA会提供一个“裁判实现”其中包含List、Position、NotFound等定义你要原样使用它不要自己另起炉灶再typedef一遍。第二如果ElementType不是int比如是float或自定义结构体直接用小于号比较可能编译都过不了或者语义不对。此时要按题目要求使用相应的比较方式。第三不要为了调试方便在函数里写printf打印语句交上去会影响输出格式轻则格式错误重则直接判错。我的习惯是在本地IDE里临时把完整可运行的骨架拼出来包括main函数、结构体定义和测试数据先调试到逻辑正确再把多余代码删掉只保留题目要求的函数体去提交。这样可以避免反复在在线评测平台上试错省时间也省耐心。4.5 变种二分再往下走一步如果你还想继续深入二分查找不只是“查一个等于target的数”这么简单。面试里更常出现的变种是查找左边界和右边界在一个有重复元素的数组里找到第一个等于target的位置或者最后一个等于target的位置。思路也不难核心变化是即使nums[mid] target也不急着返回而是继续向左收缩找左边界或向右收缩找右边界。找左边界时等于的情况统一走right mid - 1找右边界时等于的情况统一走left mid 1。循环结束后再做一次位置判断。这块内容比较适合放在“二分查找-II”里展开今天先把最基础的“二分查找-I”吃透后面才有底气解锁更大的题海。我个人在实际操作中的体会是二分查找这类算法最难的不是理解而是每次动手前有没有把“搜索区间是什么”写清楚。我自己的习惯是先写一行注释比如“当前处理左闭右闭区间[left,right]”然后才开始写代码。这个方法听起来笨但真的帮我躲过了无数次边界错误。最后再分享一个很实用的小技巧如果你实在不确定自己写的二分对不对就先用长度为1、长度为2、长度为3的三个小数组把目标分别设成最左边、中间、最右边、根本不存在的值逐个手推一遍。这套组合测试法在我刷题和带人的过程中屡试不爽希望它也能让你的二分查找少走弯路。