企业官网建设流程全解析

二分查找这个算法，很多人觉得自己早就掌握了：不就是“对一个有序数组，每次取中间值比较一下，缩小一半范围”嘛。可实际上，我在带学生和帮朋友排查面试题的几年里，发现二分查找反而是翻车率最高的题目之一。尤其是经常能在各种平台上看到“二分查找pta函数”这种搜索词，说明大批同学正在PTA上被这道经典函数题折磨。今天这篇就以“二分查找-I”为切入点，把核心思想、边界处理、PTA函数题实现和常见坑一次讲透，希望能让你真正吃透这五分钟就能学会、却要花很久才能写对的算法。

1. 二分查找的核心思路：从猜数字到区间收缩

1.1 猜数字游戏的本质

假设有人让你猜一个1到100之间的整数，你每猜一次，对方只告诉你“大了”还是“小了”。你会怎么猜？正常人都会先猜50：如果大了，范围直接缩到1到49；如果小了，范围变成51到100。无论答案是什么，一次猜测都能排除一半可能性，这就是二分查找最朴素的思想。

这个游戏背后隐藏的数学规律很值得咀嚼：初始有n个可能值，每猜一次剩余可能值减半，减到只剩下1个的时候，你就锁定了答案。猜的次数k满足 n / 2^k ≤ 1，也就是 k ≥ log₂(n)。n=100时，log₂(100)约等于6.64，所以7次以内必定猜中。一千万个数呢？log₂(10000000)约等于23.25，24次就够。这种增长速度肉眼可见地慢，是二分查找效率高的根本原因。

理解到这个层面，你就会明白二分查找不是“背模板的算法”，而是一种信息论层面的策略：每次都利用有序性获取“目标在左还是在右”这一比特的信息，逐步收敛解空间。写代码时所有细节，包括边界怎么改、循环条件怎么写，本质上都是为了保证“区间收缩”这个过程不出错。

1.2 二分查找能工作的三个前提

很多人拿着二分模板到处套，结果在无序数组上跑出错误答案，回头怀疑自己代码写错了，其实是前提没满足。二分查找成立需要三个条件，缺一不可。

第一，数据必须有序。这个“有序”可以是单调递增，也可以是单调递减，甚至可以是非严格增减（有重复值），但必须保证你能够通过一次比较确定目标在哪一侧。日常理解就是：你要在电话簿里找“张”姓朋友，就必须按拼音排好序，不然只能从头翻到尾。

第二，必须支持随机访问。二分查找每次要直接跳到中间位置，所以底层必须是数组这种可以用下标O(1)定位的数据结构。链表不行，因为找中间节点要O(n)遍历，整体复杂度就退化成了O(n log n)，不如直接遍历。

第三，元素之间可比。任何一次if判断都依赖“大于”“小于”“等于”这三种关系，如果你处理的数据不能比较大小（比如自定义结构体没有定义排序规则），那就先给它定好序再说。

这三点里，初学者最容易忽略的是“数组有序”这个前提。刷题时题目通常会明说，但在真实项目中，你要自己保证调用二分查找前数据确实有序。我见过不止一个同事，往一个动态增长的数组里不停插入新数据，却不重新排序，然后二分查找返回了诡异的结果，排查了半天才发现是数据新鲜度的问题。

2. 手写二分：三种典型写法与边界处理

2.1 先看懂区间定义：左闭右闭还是左闭右开

代码怎么写是表象，区间怎么定义才是根源。写二分之前，你必须先回答一个问题：当前搜索范围[left, right]里的left和right，到底是“数组下标”还是“下标+1”？是“包含right指向的元素”还是“不包含”？

最常见的是左闭右闭区间，也就是[left, right]表示搜索范围包含right位置的元素。此时初始化是left=0, right=n-1，循环条件是while (left <= right)，因为当left==right时，区间里还有一个元素需要检查，不能直接退出。

另一种是左闭右开区间，写作[left, right)，搜索范围包含left但不包含right。初始化变成left=0, right=n，循环条件是while (left < right)，当left==right时区间为空，已经不需要再查。这种情况下，right可以等于n，因为n这个下标本来就不在合法范围内。

这两个定义没有谁绝对更好，但你必须全程保持一致。我见过最多的错误就是：初始化用了左闭右开，更新right时却用了右闭的写法（right=mid-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时，比如left=3, right=4，mid=3，更新left=mid+1后变成left=4，循环结束。所以永远不需要担心left和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的测试用例里可能传入空指针，不判空可能会导致运行时错误（比如段错误）。不要觉得“题目一定不会给空表”，严谨的函数是任何状态下都该安全返回的。

第二个是初始化left=1, right=L->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处闲置，Last=5。

查找目标是5。初始left=1, right=5，mid=3，Data[3]正好是5，返回3，正确。查找目标是1。第一次mid=3，Data[3]是5，比1大，所以right=mid-1=2；第二次mid=1，Data[1]是1，返回1。查找目标是9。第一次mid=3，Data[3]是5，比9小，left=mid+1=4；第二次mid=4，Data[4]是7，还是比9小，left=5；第三次mid=5，Data[5]是9，返回5。查找目标是4。经历类似，最后一次mid=3后，Data[3]=5比4大，right变成2，此时left=3，left > right循环结束，返回NotFound。

这四个用例分别覆盖了“正中间命中”“最左侧命中”“最右侧命中”和“完全不存在”四种情况，手推一遍就能确认边界逻辑没有问题。时间复杂度是O(log n)，因为每次循环范围减半；空间复杂度是O(1)，因为只用了常数个变量。如果面试官追问，一定要回答出这两点。

4. 常见坑与排查技巧实录

4.1 死循环：肉眼最难看出来的问题

我见过太多人写二分，一提交就超时，一看代码，问题基本都出在left更新上。最常见的死循环写法是这样的：

if (nums[mid] < target) { left = mid; // 错误 }

为什么错？假设当前left=3, right=4，mid=3（整数除法向下取整），nums[3]确实小于target，于是left=mid，还是3。下一次循环left=3, right=4，mid还是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的三个小数组，把目标分别设成最左边、中间、最右边、根本不存在的值，逐个手推一遍。这套组合测试法在我刷题和带人的过程中屡试不爽，希望它也能让你的二分查找少走弯路。