1. 二分查找的核心思路与整体设计拆解1.1 从一个猜数字的场景说起如果你玩过“猜一个1到100之间的数对方只告诉你猜大了还是猜小了”的游戏那你其实已经用过二分查找的原始直觉每次都往中间猜一次能砍掉一半的候选范围。这个游戏背后的算法就是二分查找Binary Search也是我在实际工程和刷题中最常用、最容易被细节绊倒的基础算法之一。二分查找解决的核心问题非常明确在一个有序的序列中快速定位某个值的位置或者找到满足某种条件的最左/最右位置。它把线性查找的时间复杂度从 O(n) 降到了 O(log n)。别小看这个log当数据量从一万变成一百万时线性查找可能需要跑几十万次而二分查找只需要大约20次比较。这种差距在大规模数据处理、数据库索引思想、各类竞赛题目里都是决定性的。这篇文章适合这样几类读者刚学完数组和循环、想真正掌握二分边界写法的初学者在PTA、力扣等平台做题时经常因为死循环或越界扣分的同学以及工作中需要在有序数据上做快速检索、但总记不住边界规则的开发工程师。我会从底层原理、边界细节、代码实现、PTA实战到变体扩展把二分查找这件事讲透。1.2 为什么必须有序——单调性与“砍半”的数学基础二分查找之所以能工作前提是序列具备单调性。所谓单调性就是随着下标增大数组中的值要么一直不减升序、要么一直不增降序。在这个前提下当你比较中间位置的值与目标值时结果会告诉你一个关键信息目标值只会落在左边或者右边而中间及其另一侧的所有元素都可以被安全丢弃。这一点特别像在电话簿里翻名字因为首字母是按字母顺序排列的你知道“Li”在“Ku”后面那“Li”就一定不在“Ku”之前的所有页里。电话簿不是靠一页页翻的是靠一次次“往中间翻、再判断方向”完成的。从数学角度看每次比较至少把搜索区间缩小一半因此最多经过log2(n)次比较就能收敛。这个结论是所有二分变体的基石也是我们在面试中能自信说出“时间复杂度为 O(log n)”的依据。但它有一个隐性前提序列必须支持随机访问也就是能通过下标在 O(1) 时间内拿到任意位置的值。所以二分查找通常用于数组而非链表——链表也可以二分但每次取中点都需要遍历时间复杂度退化得很严重。1.3 二分的本质不是“找值”而是“划分边界”很多教材把二分讲成“在有序数组里找一个数”这其实窄化了二分的用途。二分的真正本质是在一个满足“前部分为假、后部分为真”或相反的判定序列上找到真假分界的那个位置。举个具体的例子假设存在一个数组[1, 3, 3, 3, 5, 7, 9]你想找“第一个大于等于4的位置”。那么对于每个下标你可以定义一个判定函数check(mid) (a[mid] 4)。这个判定函数的返回值序列是[False, False, False, False, True, True, True]。我们要找的就是第一个True的位置。这个过程完全可以用二分完成而且它不要求你真正去“比较相等”只需要一个可判定的布尔条件。这个视角非常关键因为它把二分从一个“搜索算法”提升为一种“通用优化套路”。后面我会专门讲怎么把这种“答案二分”的思想用到实际题目中。2. 边界到底是左闭右闭还是左闭右开——细节决定成败2.1 两种最常见的区间写法写二分查找第一件事不是写代码而是先定区间表示。初学者最容易混乱的就是这里一会儿while (left right)一会儿while (left right)一会儿right mid一会儿right mid - 1。这些写法没有绝对的对错但如果你混着用就会出现死循环或漏判。我习惯以区间是否包含右端点来区分两种写法左闭右闭[left, right]初始化left 0, right n - 1。循环条件是while (left right)。因为区间里包含right所以当left越过right时才说明区间为空。左闭右开[left, right)初始化left 0, right n。循环条件是while (left right)。因为right本身不参与检查当left right时区间已经为空。这两种写法各自配套的更新方式也不一样。左闭右闭时如果a[mid] target那么mid位置已经不可能是答案了所以要写成right mid - 1如果是左闭右开right是个取不到的位置所以直接right mid就可以了因为mid已经被排除在下一轮区间之外。我在实际教学中发现一个规律写左闭右开时循环条件用、更新时right mid或left mid 1逻辑比较顺也不容易死循环。而左闭右闭的写法更直观但mid - 1和mid 1容易在边界处出错。我的建议是个人练习时固定用一种但必须能读懂另一种因为不同教材、不同题解用的风格不一样。2.2 mid 的计算一个坑了无数人的整数溢出mid的写法是二分查找里最经典的“隐形 bug”。很多人一开始写的是int mid (left right) / 2;这在left和right都较小时没有问是可一旦数组长度接近INT_MAX约21亿left right就可能超过int的表示范围变成负数导致mid计算错误。这在内置了二分查找库函数的语言里影响不大但手写时非常危险。正确的写法是int mid left (right - left) / 2;或者用位运算版本int mid left ((right - left) 1);这样right - left永远不会超过right本身的量级从根本上避免了溢出。同理在Java、C里也建议用left (right - left) / 2。另外用右移 1来替代/ 2是可以的但要注意运算优先级left ((right - left) 1)必须加括号否则left right - left 1会先算加法得到完全不同的结果。这种低级错误我见过不止一次千万别踩。2.3 死循环到底是怎么产生的死循环是二分查找初学者最痛苦的报错类型。它不报越界也不报答案错误就是卡住不动让你盯着屏幕怀疑人生。死循环的本质是某个区间状态下新的区间和旧的区间完全相同。最常见的死循环场景是在左闭右闭写法中如果mid已经等于left例如区间长度为2时而你执行了left mid而不是left mid 1那么新区间和旧区间完全一样循环永远跳不出去。另一个常见场景是左闭右开写法中mid的计算偏左且你又写了right mid - 1导致新的右边界反而小于等于旧的左边界区间逻辑直接混乱。为了避免死循环你只需要记住一个铁律每一次循环区间必须严格缩小。无论是left前进还是right后退都必须确保新的搜索范围比旧的小。如果发现某次迭代后区间长度没有变化那一定就是死循环的信号。调试时可以打印每次的left、right、mid三个值很快就能定位到是哪一行把区间“冻结”了。3. 二分查找的标准实现与PTA实战3.1 一套可以直接用的标准模板这里给出一套我反复使用的标准二分模板基于左闭右开区间适合在绝大多数场景下直接套用。以C语言为例// 在递增有序数组 a 中查找 target返回其下标若不存在返回 -1 int binarySearch(int a[], int n, int target) { int left 0, right n; // 左闭右开[left, right) while (left right) { int mid left (right - left) / 2; if (a[mid] target) { return mid; // 找到直接返回 } else if (a[mid] target) { left mid 1; // target 在右半区间 } else { right mid; // target 在左半区间 } } return -1; // 区间为空仍未找到 }这段代码里left和right的语义非常清楚left是当前可能解的最小下标right是最大下标加一。因为right本身是不包含的所以当a[mid] target时把right设为mid即可不用减一。这样做的好处是你不需要纠结“mid 有没有可能等于 right”因为right本来就不是合法下标。Python版本也很简单def binary_search(arr, target): left, right 0, len(arr) while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid return -13.2 PTA“二分查找”函数题怎么破解在PTA平台上二分查找经常以“函数题”的形式出现给你一个递增数组和一个待查找的值你要实现一个函数返回目标值的下标有些题目要求返回第一个匹配的位置有些直接返回任意匹配位置。这类题目的特点是输入输出已经由题目框架定义好你只需要补全函数体而函数体内部到底怎么写完全看你对边界的把握。我在PTA上见过的最典型函数题是题目给了一个结构体数组或数组函数原型类似于int Search(int a[], int n, int target)要求在数组a中查找target找到则返回其下标否则返回-1。这种题目用上面的模板直接就能过。但有几个容易被扣分的细节返回值的约定有些题目返回的是下标有些返回的是逻辑序号从1开始还有些要求返回“是否存在”的布尔值。写之前先看清题目描述别把0当成“不存在”的信号因为下标0在C语言里是合法的。数组可能为空如果n 0直接返回-1不要进入循环。重复元素如果题目要求“返回第一个等于target的位置”上面的模板返回到的可能是任意匹配位置。这时你需要用变体模板详见第4章而不能直接返回。配合PTA常见的判断题和编程题我建议你在本地自己搭建一个测试函数把所有极端情况写成一个数组列表跑一遍而不是只提交上去等判题结果。比如测试n1、target小于最小元素、target大于最大元素、所有元素都相同、元素个数为偶数/奇数等场景。这些边界往往就是PTA测试点里专门埋的坑。3.3 完整示例从输入到输出下面是我在调试PTA题目时经常用的一套完整C程序框架你可以直接复制下来在本地验证#include stdio.h int binarySearch(int a[], int n, int target) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if (a[mid] target) { return mid; } else if (a[mid] target) { left mid 1; } else { right mid; } } return -1; } int main() { int a[] {1, 3, 5, 7, 9}; int n sizeof(a) / sizeof(a[0]); int target 7; int pos binarySearch(a, n, target); if (pos ! -1) { printf(found at index %d\n, pos); } else { printf(not found\n); } return 0; }这里有一个细节当数组元素个数为奇数时mid正好落在正中当数组元素个数为偶数时mid偏左例如长度为4时mid(04)/22也就是第二个元素。这个“偏左”的特性在标准查找里没有影响但在变体问题里要注意——我们后面会提到它可能导致找左边界时需要特别处理。4. 从“找一个数”到“找边界”——二分查找的三大变体4.1 查找第一个等于target的位置现实中的问题往往不是“找一个数”而是“找第一个满足条件的位置”。例如统计一个班级成绩单中第一个及格60分的人是谁或者在一个日志列表中找第一条出现某个状态码的记录。这类问题的特点是数组中有重复元素而我们需要的是最左侧的那个。变体模板如下左闭右开int lowerBound(int a[], int n, int target) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if (a[mid] target) { right mid; // 当前位置可能是答案但不能排除左侧还有 } else { left mid 1; } } return left; // 如果 left n说明不存在 }这套逻辑的关键在于当a[mid] target时我们不急着返回mid而是把右边界压缩到mid继续在左侧寻找。循环结束后left指向的位置就是第一个大于等于target的元素下标。如果你要的是“第一个等于”还要再加一句判断a[left] target否则返回 -1。上面这个函数其实在C标准库里就是lower_boundPython里对应bisect_left。理解它的实现原理比直接调库更能在面试和竞赛中拿分。4.2 查找最后一个小于等于target的位置另一个高频变体是“查找最后一个不大于 target 的元素”。比如在商品价格列表里找出最后一个不超过预算的商品在日程表中找最后一个早于某个时间点的事件。模板可以这样写int upperBound(int a[], int n, int target) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if (a[mid] target) { left mid 1; // mid 可能是答案但右侧可能还有 } else { right mid; // 排除大于target的部分 } } return left - 1; // left 是第一个大于target的位置 }注意看这里和lower_bound的差异非常细微一个是时压缩右侧一个是时推进左侧。很多初学者把这两个模板混着用结果找出来的位置要么偏左一位要么偏右一位。我的记忆口诀是找左下界大于等于压缩右侧找右上界小于等于推进左侧。把这两句话刻在脑子里比死记代码管用。4.3 浮点数二分和“答案二分”二分查找不仅适用于整数数组也能作用于实数域。比如求平方根给定一个非负数x求它的平方根精度要求1e-6。这时你不能用整数下标而是要在实数区间[0, x]上不断缩小区间长度。因为实数连续循环条件不能像整数那样用而要用精度控制double sqrtBinary(double x) { double left 0, right x; if (x 1) right 1; // 小于1时平方根比x大需要扩大上界 for (int i 0; i 100; i) { // 迭代100次精度足够 double mid (left right) / 2; if (mid * mid x) { left mid; } else { right mid; } } return left; }这里我用固定迭代次数100次来代替while (right - left eps)因为浮点数比较在极端情况下可能因为精度不够而陷入死循环。100次迭代可以把区间长度缩小到原来的2^100分之一对于任何实际场景都绰绰有余。所谓“答案二分”是二分思想的一种高级应用问题本身不是“在数组里搜索”而是“求一个最优解”而这个最优解具有单调性。例如给定一个正整数数组你要判断“是否存在一种划分方式使每个子数组的和都不超过limit”。如果limit太小一定不行如果limit足够大一定可以。那么“可行”这个性质关于limit就是单调的——我们可以二分limit对每个猜测值运行一次判定函数。这种套路在算法竞赛里非常常见很多看似复杂的“最大值最小化”问题本质就是一个“答案二分”加贪心判定。我的建议是遇到题目时先问自己三个问题——答案是否在一个可枚举的范围内这个范围的答案是否满足单调性给定一个答案我能否高效地判定它是否可行如果三个问题的答案都是“是”那这题八成就是二分答案。5. 避坑手册我在PTA和实际开发中踩过的二分坑5.1 常见的五类错误与排查方案二分查找的坑非常集中我把它们整理成了一张速查表方便你在调试时对照错误现象可能原因排查与修复死循环区间更新后长度不变通常是left mid却没有给mid1打印每次的left/right/mid确认每次区间都在缩小返回下标偏左/右与用混或left/right更新方向错误对照第4章的模板逐行确认条件分支越界访问right初始化为n-1但在左闭右开模板中用了a[right]统一区间语义要么全用闭区间要么全用开区间找不到边界值循环结束后忘了检查left是否越界返回前加上if (left n a[left] target)判断整数溢出使用(left right) / 2计算mid改为left (right - left) / 2浮点死循环用right-left eps作为循环条件但eps过小改用固定迭代次数如100次5.2 一个真实调试案例PTA函数题里的“差一错误”有一次我在PTA上写一道查找题题目要求返回“第一个等于target的下标”。我一开始用的是标准二分查找模板也就是找到就return mid。自信满满提交结果有一个测试点过不去。我本地打印数组和查找全过程发现数组是[2, 2, 2, 3, 3]target是3。标准模板返回的下标是3但题目期望的是3吗看起来没错。可如果数组是[2, 2, 3, 3, 3]target是3标准模板返回的是中间那个3的下标2而“第一个等于3”的位置应该是2。嗯这里恰好一样。真正暴露问题的是这个数组[1, 2, 2, 2, 3, 3]target是2。标准二分第一次mid (06)/2 3a[3]2直接返回3。但“第一个等于2”的位置应该是1。题目要求返回1我的代码返回了3自然就WA了。把模板换成第4.1节的lowerBound变体后问题立即解决。这个案例特别能说明搞清楚题目在问什么比会写二分重要一百倍。哪怕你二分写得很熟练如果题意理解偏差照样白费功夫。5.3 “看着对但就是错”的代码长什么样我总结了一下这类代码通常有以下几个特征它混合了左闭右闭和左闭右开的写法。比如初始化用的是左闭右闭right n-1循环条件用的是左闭右开while (left right)更新时又采用了左闭右闭的right mid - 1。这三种风格混在一起逻辑上是不自洽的在特殊测试点下就会暴露问题。另一种典型错误是在左闭右开模板中mid被用来索引数组但因为循环条件是left right当left和right挨在一起时mid始终等于left随即又执行left mid 1这本身没错可如果错误地写成right mid在同一分支里还使用了mid - 1更新那么新的右边界可能跑到左边界左边直接导致访问负下标。我见过太多这种混合风格代码最后的建议只有一条统一区间定义写下来贴在显示器旁边。每次写完函数心里从头到尾过一遍初始化、循环条件、左更新、右更新、最终返回值这五处都必须严格匹配同一个区间语义。6. 二分查找在现实场景中的扩展应用6.1 从数组到函数二分不再依赖“下标”数组只是二分的一种载体。只要你能回答“某个值是否可行”并且这个“可行”随参数单调变化你就能用二分。比如判断一台服务器在给定负载下是否超时判断一批货物能否在给定车辆数内完成运输判断一个调度方案能否在给定时间内完成全部任务。这类问题在OOP、系统设计、运维脚本里到处都是。这种应用方式我做项目时经常遇到。比如一个批处理任务需要估算“每分钟最多能处理多少条日志”而每条日志的处理耗时会随着总输入量变化。我可以写一个check(rate)函数返回“在该速率下是否能在限定时长内处理完所有日志”。因为处理能力越大越容易完成check是单调的于是我可以二分这个速率找到最大值。这种方法比直接构造数学公式要简单得多尤其是在性能参数不明确、只能靠实验测定的场景里。6.2 与排序配合的经典套路二分双指针在数组相关的算法题里二分经常和排序、双指针一起出现。例如“给定一个有序数组和一个目标值找出数组中两个数之和等于目标值的所有组合”。你可以固定第一个数然后对剩余部分做二分查找目标差值。虽然双指针O(n)更优但在一些变体题里比如“三个数之和最接近目标”先排序再固定一个数、对剩余区间二分或双指针是标准解法。这个套路在生产环境也有价值。比如在订单列表按金额排序中找出所有满足“两笔订单合计金额恰好等于某额度”的组合用于风控规则排查。用二分能把双重循环 O(n^2) 降到 O(n log n)在数据量稍大的场景下体验差异非常明显。6.3 面试中如何展示二分水平面试官让你写二分查找其实不只是检查你会不会背模板。他们更想看的是你会不会先确认输入是否有序、是否包含重复元素、目标搜索的边界语义是什么你会不会主动处理整数溢出和空数组你能不能解释当前模板为什么不会死循环。这几件事比代码本身更能体现扎实的工程素养。我建议面试时先口述一遍你的区间定义“我习惯用左闭右开区间left指向候选起点right指向终点加一循环不变式是 target 始终落在[left, right)内。”面试官听到这句话基本就知道你理解到位了。另外别一上来就写最优变体。先写一个朴素的binarySearch然后根据面试官的要求“如果数组里有重复元素呢”再演进到lowerBound反而显得思路清晰、沟通顺畅。一上来就背一个模板的输出效果远不如“现场把它推出来”来得有说服力。7. 我的实操心得与最后一个小技巧二分查找这个算法看起来只有十几行代码但我在PTA和实际项目中反复踩坑之后最大的体会是难的不是“找到答案”而是“定义答案是什么”。每次拿到一道二分题先去搞清楚答案在哪个范围内判定条件是什么返回的是下标、位置、还是布尔值搞清楚了这三件事再套模板基本一遍过。最后再分享一个我多年来一直在用的小技巧写完二分函数后不要只测试正常用例一定要手动模拟一次“区间长度为1”的情况。在纸上或者脑子里演算一遍left0, right1, mid0看你的分支会不会把区间正确更新再演算一次leftn-1, rightn, midn-1的情况看访问a[mid]时下标有没有越界。这两次心理演练能干掉80%的二分边界bug。这比任何调试工具都来得快也是我每道二分题都能一次提交通过的秘密。