二分查找可能是算法题里最“看着容易、写起来拉胯”的经典了。数组越长它越显得无所不能数组越短它反而容易让你怀疑自己是不是连幼儿园算术都不会。面试笔试、PTA函数题、LeetCode周赛几乎没有哪个环节能躲开它。但每次看到有同学在while循环里调半天边界或者把mid left (right - left) / 2写错成(left right) / 2我都觉得这真不是智商问题而是这套东西有太多“坑”藏在细节里没人给你讲透罢了。这篇我想聊的是我对二分查找的完整认知——不是只给你一个模板背下来而是把它拆开看为什么它能做到对数复杂度、为什么不同写法结果不一样、为什么会有死循环以及它怎么从“查数组”升级成“二分答案”这个大杀器。顺便结合 PTA 上那道经典的二分查找函数题讲一讲评分点都藏在哪里。适合刚入门算法、正在准备笔试面试、或者被各种边界问题折磨到崩溃的同学。1. 二分查找到底在做什么——原理拆解1.1 从一个猜数字游戏讲起先想一个特别朴素的问题让你从 1 到 100 里猜一个数字对方只告诉你“大了”或者“小了”你会怎么猜正常人不会从 1 开始一个一个问。最稳的策略是直接猜 50。如果对方说“小了”范围马上缩到 51 到 100如果“大了”范围缩到 1 到 49。每猜一次范围大约缩小一半。最多猜 7 次你总能锁定答案。这就是二分查找最朴素的生活原型。这个例子里有个非常关键的事实你之所以敢猜 50是因为你默认了“数字大小是有顺序的”。如果不排序、随机乱序猜 50 完全不给任何信息。所以二分查找的第一个前提就是数据必须存在某种可以比较大小的顺序也就是通常说的“有序数组”。1.2 有序性为什么重要——核心是“排除方向”很多人能背二分查找的代码但被问到“为什么数组必须有序”时只能答“因为教材这么说的”。其实本质就一句话有序性让数组具备了“方向”。假设数组从小到大排列你拿arr[mid]和target比较如果arr[mid] target直接命中不用继续如果arr[mid] target说明target比中间值大又因为数组从左到右递增所以target一定在mid右侧左侧整个半区可以直接扔了如果arr[mid] target同理target一定在mid左侧。所以每次比较不是“猜一次少一个候选”而是“猜一次杀掉一半候选”。这就是它和线性扫瞄的本质差别线性查找每次排除一个二分查找每次排除一半。对应的复杂度对数元素从 1024 涨到 100 万二分查找的步数其实也就从 10 涨到 20 而已。1.3 二分查找的本质可行性判定函数我喜欢把二分查找看成一件更高级的工具。它的本质不是“在有序数组里找一个数”而是在一段连续的区间上找一个“分界点”——左边满足某个性质右边不满足或者反过来。举个例子arr [1, 3, 5, 7, 9]要找 5。你其实可以把数组看成每个位置上的“这个数是否小于 5”1 5为真3 5为真5 5为假7 5为假9 5为假这个真假序列是真、真、假、假、假中间有一个清晰的“分界点”二分查找就是在找这个分界点。一旦你把问题转换成“判断某个位置左边全部为真、右边全部为假”理解各种变种题就顺了包括后面要讲的lower_bound、upper_bound以及二分答案全都能统一到这同一个框架下。2. 手写二分查找——三种区间模板和它们的爱恨情仇2.1 模板一闭区间[left, right]最常见、也最好理解的写法int binary_search(int nums[], int n, int target) { int left 0, right n - 1; // 闭区间 [left, right] 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; }这里while (left right)对应的意思是当区间里至少还有一个元素时继续循环。所以循环结束后left right 1区间彻底空了此时返回-1表示没找到。这种写法最直观新手最容易接受。唯一要注意的坑是mid的计算。写成(left right) / 2在left和right都很大的时候可能整型溢出。虽然刷题时数组长度很少到 10 亿级别但面试官喜欢问所以还是养成写left (right - left) / 2的习惯更稳。这个损失不了几个字节纯赚的。2.2 模板二左闭右开[left, right)C 的 STL 容器几乎全用“左闭右开”的区间约定所以刷题时你也会经常看到这种写法int binary_search(int nums[], int n, int target) { int left 0, right n; // 左闭右开 [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; // 注意这里返回的是“第一个 target 的位置” }这里的变化比较微妙right指向的是最后一个元素的下一个位置所以初始化为n而不是n - 1循环条件变成left right因为当left right时区间是空的当nums[mid] target时说明mid及左侧都不可能是目标所以left mid 1否则也就是nums[mid] target时mid可能是目标保留它所以right mid不是mid - 1。这个写法其实直接实现了lower_bound——返回第一个不小于target的位置在后文会细讲。如果你要找target本身是否存在拿这个位置再判断一下值即可。2.3 模板三开区间(left, right)还有一种写法让区间两端都不包含int binary_search(int nums[], int n, int target) { int left -1, right n; // 开区间 (left, right) while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; } else { right mid; } } return right; // 第一个 target 的位置 }这个写法的好处是mid 永远不会和 left 或 right 相等因为 left 初始为 -1、right 初始为 n而left 1 right保证了 mid 至少比 left 大 1、比 right 小 1。这意味着不管怎么更新left mid或right mid都不会造成死循环。等你想清楚了各种奇奇怪怪的边界再回到这个模板会感叹它是真的优雅。但平时我还是建议新手从闭区间模板入手因为最符合直觉。当闭区间写熟了再把“区间开闭”的变换当作一种思维体操去理解收益会更大。2.4 中位数陷阱左中位还是右中位写二分查找时mid (left right) / 2默认取的是左中位向下取整。大部分情况没问题但一旦你的更新逻辑里含有left mid这种左中位就会导致mid永远等于left从而死循环。来一个具体场景。查找“最后一个等于 target 的位置”int search_last(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) { left mid; // 这里埋着死循环 } else { right mid - 1; } } return left; }假设nums[mid] target恒成立那么 right 不动、left 每次变成 mid而 mid 一直是 left循环永远出不来。解决办法是取右中位int mid left (right - left 1) / 2; // 右中位向上取整右中位会在两元素时偏向右边左中位偏向左边。口诀就是用左中位就配left mid 1用右中位就配right mid - 1一旦需要left mid得用右中位一旦需要right mid得用左中位。这是我见过最容易踩、也最防不胜防的坑。3. 二分查找的变种与真实应用场景3.1 lower_bound 和 upper_bound 到底是什么实际工程和算法题里查“等于某个值”其实没那么多需求更多时候是要查位置边界。比如lower_bound返回第一个 target的位置upper_bound返回第一个 target的位置。这两个函数加一起就能轻松计算一个有序数组中某个值的出现区间。C 的std::lower_bound和std::upper_bound帮你实现了但面试时经常被要求手写。用刚才左闭右开模板就是现成的// 手动实现 lower_bound int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }它的本质在前面也提到了火花nums[mid] target时说明 mid 左侧全不行排除左侧否则 mid 可能是答案保留之。把自己训练成“判定函数”思维这种题目根本不需要背推一遍就能写出来。3.2 二分答案把最优化问题变成判定问题这个扩展我认为是整个二分查找里最有价值的升华比单纯查数字有用得多。场景有n段木头长度分别存进数组里要切割成k段长度相等的小段。问每段最长能切多长直接算“最长”很难但如果你给定一个长度len去判定“能不能切出 k 段”这就非常简单了——把每根木头整除一下累加段数看是否够k。于是真正的最长变成了一个“最大可行值”的搜索问题可行就继续往长了试不可行就往短了缩。这完全可以二分查找。写出判定函数bool can_cut(int len, vectorint wood, int k) { int count 0; for (int w : wood) { count w / len; } return count k; }然后对答案二分int max_len(vectorint wood, int k) { int left 1, right *max_element(wood.begin(), wood.end()); while (left right) { int mid left (right - left 1) / 2; // 右中位避免死循环 if (can_cut(mid, wood, k)) { left mid; // 可以继续往长试 } else { right mid - 1; // 不行缩短 } } return left; }用到的思想恰恰是 1.3 节说的“可行性函数分界”短的可行长的不可行注意方向要根据题意变找那个分界点。这种“二分答案”技巧在算法竞赛里太常见了典型模型有求最小化最大值比如把数组拆成m个子数组让每个子数组和的最大值最小求最大化最小值比如给牛棚位置让相邻牛之间最短距离最大在浮点域上二分求方程的根或最优近似解。遇到这类题第一反应不要想怎么贪心或动态规划先想能不能把“求最优值”改写成“判定某个值可行不可行”如果能那就二分答案。判定函数越简单这个思路越划算。3.3 浮点数二分精度控制有讲究整数的二分可以盯着边界浮点数就没这么讲究了一般用误差阈值控制终止double sqrt_binary(double x) { if (x 0) return -1; double left 0, right x; // 处理 x 小于 1 的情况右边界至少是 1 if (x 1) right 1; while (right - left 1e-7) { // 精度给到 1e-7 double mid left (right - left) / 2; if (mid * mid x) { left mid; } else { right mid; } } return left; }浮点数二分不需要担心死循环因为mid永远在 left 和 right 之间且区间长度不断减半。你唯一要决定的是误差阈值。阈值太小会多跑几十次循环但每次循环开销也不大一般建议比题目要求精度高 2 个数量级比如要求保留 6 位小数就用到1e-8这种量级。3.4 PTA 函数题实战评分卡在哪里再来专门说说 PTA拼题A上那道经典的二分查找函数题。题目一般是这样Position BinarySearch(List L, ElementType X);给定一个递增的线性表L和元素X要求返回X在表中的位置找不到就返回NotFound。很多同学的代码能跑通本地样例但提交就是错或者有超时原因往往在几个细节上第一下标从 1 开始。PTA 的List结构通常这么定义typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; // 线性表最后一个元素的位置 };而Position一般约定为 1 到Last之间的值Data[1]存第一个元素Data[0]通常空着或者不用。所以你的left 1, right L-Last而不是从 0 开始。第二中间值写成(left right) / 2又把left right塞进固定 int。在评测环境里Position有可能是 int、long当表特别大时溢出风险就来了。用left (right - left) / 2或者位运算右移才能避免。第三循环退出条件。如果你写成while (left right)再配合right mid - 1可能漏掉left right时那一次检查。更稳的做法是用while (left right)闭区间直接把最终命中节点也查了。对比一下常见的错误写法Position BinarySearch(List L, ElementType X) { Position left 1, right L-Last; while (left right) { // 错会漏查 left right 的情况 Position mid (left right) / 2; if (L-Data[mid] X) left mid 1; else if (L-Data[mid] X) right mid - 1; else return mid; } if (L-Data[left] X) return left; else return NotFound; }这个其实也能过但容易出问题的地方在于如果Last 0也就是空表left 1已经越界访问了。真正稳的写法就要先判空再进入二分最后再决定返回值。很多同学 PT A 上卡在三分、两分不是算法不懂全是这些细枝末节的文件。4. 高频 bug 与排查技巧4.1 死循环的内幕死循环是二分查找最大的杀手。前面简单提过现在系统梳理一下它的产生条件。一、更新分支里出现了left mid或right mid同时 mid 取位方向不合适导致 mid 永远等于边界。比如left mid却取了左中位两元素时 mid 就是 leftleft 不前进永远循环。同理right mid却取了右中位也会卡死。二、循环条件是left right但你的边界更新逻辑有时left或right根本不移动。最典型的错误是把left mid - 1写成left mid或者right mid 1写成right mid。闭区间时每次排除的是mid ± 1如果漏掉 ±1就可能在两个值之间来回横跳。三、对区间开闭理解混乱。比如左闭右开区间[left, right)却用right mid - 1这会导致区间越来越离谱循环次数失控。死循环在我看来几乎都是“取中位方向”和“边界更新方向”不匹配造成的。记住 2.4 节的口诀这种问题基本上能绕开一条命。4.2 边界错位与返回值混乱另一类高发问题不是死循环而是返回的位置差了一位。写lower_bound时到底是返回第一个大于等于 target 的位置还是最后一个小于 target 的位置很多人写完心里没底一跑样例好像对换一组边界就错。这种问题最好的解法就是拿最小规模的边界案例手工验证。比如数组[2, 3]分别试 target 1、2、3、4手工推一遍你的代码看返回结果是否符合预期。target 1应当返回 0第一个 1 的是第 0 个target 2应当返回 0target 3应当返回 1target 4应当返回 2越界位置不算错工程上常用这个哨兵位置表示“不存在”如果这四个点都过了你的 lower_bound 逻辑基本稳了。4.3 三个调试技巧我自己的实战经验里有三个特别管用的调试技巧分享给大家技巧一打印左右边界。在 while 循环里加一行printf(left%d right%d mid%d\n, left, right, mid);配合小样例跑一遍看区间缩小轨迹是否符合直觉。死循环一眼就能看出来某行输出里 left 和 right 半天不变化。技巧二断言区间收缩性。每次循环里可以加一个断言assert(mid ! left || mid ! right)保证 mid 不会等于两个边界之一。如果left mid而 mid 又等于 left断言立刻炸出来省得你干瞪眼。技巧三把目标值换成边界值。如果你不确定返回结果对不对直接拿数组第一个元素、最后一个元素、甚至比第一个还小的值、比最后一个还大的值去测试。大多数边界 bug 藏在这四个点上。我把常见错误整理成一个速查表症状常见原因建议解法死循环left mid但取了左中位改取右中位(left right 1) / 2死循环闭区间下left mid没排除 mid改成left mid 1返回位置差 1lower_bound / upper_bound 混淆明确目标函数用 2.2 模板空表越界没判Last 0进入二分前先判空溢出(left right) / 2改left (right - left) / 2精度不够浮点阈值太大比要求精度高 2 个数量级4.4 一个综合例子查找旋转排序数组中的最小值把前面所有知识串起来的经典题nums本质是有序数组经过一次旋转比如[4, 5, 6, 7, 0, 1, 2]要找最小值。虽然数组不是全局有序的但它可以分为两个递增段且分界点就是最小值。思路还是要找“第一个小于或等于末尾元素的位置”。假设末尾元素是nums[n-1]那么数组中nums[x] nums[n-1]这个性质在分界点右侧恒成立左侧恒不成立。用二分找这个分界点即可int find_min(vectorint nums) { int n nums.size(); int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[n - 1]) { left mid 1; // 说明 mid 在左侧递增段最小值在右边 } else { right mid; // mid 在右侧继续往左找更小的分界 } } return nums[left]; }这个题没有直接“找 target”而是用“判定函数”扫描区间但它依然是二分查找。写到这里我特别想说一句别把二分局限在“有序数组里查值”要把思维升级成“找单调性质的分界线”。一旦想通你在刷题档次上会有肉眼可见的跨越。5. 学习路径与工程应用感悟5.1 怎么练习最有效如果想系统地把二分查找彻底吃透我的建议是别急着刷一堆题先把基础模型题练熟再上变种第一梯队手写基础数组里查找 target以及 lower_bound/upper_bound 的手写实现练到闭眼能写不卡壳第二梯队经典变种查找第一个等于 target/最后一个等于 target 的位置、查找插入位置、旋转排序数组最小值第三梯队二分答案拆数组最大最小值、分木头、分配饼干这类最优化题目练到能熟练把最优化问题改写成判定 function。做题时有个习惯很强推每次写二分把区间写法和 mid 的取法定下来了再动循环体。不要临场“灵机一动”模板定式很重要。等代码跑通了再尝试把闭区间改成左闭右开或者开区间体会一下不同写法对边界的影响这一步对面试时临场解释非常有用。5.2 工程里的二分不止在数组里很多人以为二分查找只在刷题时用得到工程里没什么存在感。这是个很大的误解。举几个真实的例子程序 bug 排查版本管理系统里类似 “git bisect” 的功能本质就是二分定位。你有几百个提交其中某一个引入了 bug每次都取中间那次提交来测试能快速定位出具体是哪一次引入的问题。数据库索引与文件系统在有序索引结构上做查找绕不开二分。B 树的节点内部通常会用二分查找定位 key不是线性扫。机器学习与调参在某个单峰区间上搜索最优超参或学习率时如果满足条件可以先用二分/三分快速逼近比网格搜索效率高得多。数值计算求方程的根、查找临界点二分法是最简单最稳的逼近方法之一。所以我说二分查找不像那些花哨的动态规划惊世骇俗但它是真正的“朴素而强大”。不是每个题目都能动态规划但每个有序场景下你都能想到二分。写到这里我最大感觉是二分查找的难度根本没在算法思想上全在表达细节上。理解它本质上是在找“性质分界点”之后代码怎么写都不容易飘。如果你手头有 PTA 或者 LeetCode 刷题任务别急着背模板先拿出一张纸把 left、right、mid 之间的关系画出来把闭区间和左闭右开的差异试出来后面真的会舒服很多。我自己当年就是在“左闭右开”这个怪圈里绕了整整一周才彻底想明白现在回头看才是真正值回票价的那一周。