二分查找这个算法说真的是那种“看起来简单到爆写起来错到哭”的典型代表。我刚工作那几年每次在代码里写二分心里都得默念三遍“左闭右开、左闭右开”生怕一个边界条件搞错就死循环或者漏元素。后来带团队面试发现十个候选人里能有七个在二分查找的边界处理上翻车这还是在大家觉得自己“准备过算法题”的情况下。所以今天想把这几年在C里写二分查找的实战经验好好捋一捋。这篇文章不打算讲那种教科书上的“存在性查找”就完事了而是会把二分查找在C里的各种形态、各种坑、各种工程上的玩法都拆开聊一聊保证你看完之后不管是应付面试手撕代码还是在实际项目里处理数据查找、边界定位都能心里有底。1. 二分查找的内核不是“找数字”而是“找边界”很多人学二分查找第一反应就是哦在一个有序数组里找一个目标值。这个理解没错但是太浅了。如果你只把二分当做一个“高级一点的顺序查找”那你永远写不对它也永远用不好它。1.1 单调性才是二分的灵魂二分查找能成立的唯一前提是“单调性”。你手里的数据必须有一个单调的性质才能通过比较中间值排除掉一半的搜索空间。举个例子你有一排从小到大排列的数字你想找7。你看了一眼中间的数字是5那你就知道7一定在5的右边左边那一半全都不用看了。这个过程能成立靠的就是“右边都比中间值大”这个单调性。但注意这个单调性不一定要是数值上的有序。它可以是任何形式比如“从某个位置开始后面的元素都满足某个条件”。我经常跟朋友说二分查找本质上是在单调区间上寻找一个“分界点”而你要找的目标值只是分界点的一种特例。1.2 写成循环比写成递归重要一万倍我见过不少同学特别执着于用递归写二分查找int binarySearch(vectorint nums, int left, int right, int target) { if (left right) return -1; int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) return binarySearch(nums, mid 1, right, target); else return binarySearch(nums, left, mid - 1, target); }说实话面试的时候你这么写面试官不会说你错。但对工程实现来讲递归版有两个问题很要命第一函数调用有栈开销虽然二分查找的深度是O(log n)不会爆栈但性能上确实白扔了一部分第二递归的参数多了边界状态更容易搞乱。真正好用的是迭代版本三个变量走天下int left 0, right nums.size() - 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; }这版本里有个我特别想展开说的细节mid的计算用left (right - left) / 2而不是(left right) / 2。为什么因为left和right如果都是很大的int加起来会溢出。这是个非常经典的坑LeetCode上第一版二分查找的题解评论区年年都有人踩。写二分查找就是要养成“任何可能溢出mid都用left (right - left) / 2”这个肌肉记忆。这行代码写对了能替你挡掉很多隐蔽的bug。2. C实现里的那些边界“鬼打墙”边界条件是二分查找的重灾区。别看你平时刷题可能侥幸AC了真要让你讲讲为什么while条件是left right而不是left right很多人支支吾吾说不清楚。这里我把我自己的理解方式分享出来保证你再也不会把区间搞混。2.1 区间不变式写着写着就不乱的密钥写二分最核心的思维是“维护一个区间不变式”。你要在一开始就定义清楚你的搜索区间[left, right]代表的是一个闭区间还是开区间然后这个区间里永远包含你还没检查的元素。我默认用的是“闭区间”也就是left指向第一个还没检查的元素right指向最后一个还没检查的元素。当left right时说明这个区间空了没得找了循环结束。所以你看循环条件是left right这正是区间不空的条件。一旦left rightmid就是区间里最后一个元素检查完它之后无论走哪个分支left一定大于right循环终止。这逻辑听着很顺吧但很多时候大家写着写着就乱了是因为贪图少写一遍比较。比如有些人会写成while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid; }这种写法里面的right mid是因为它把right定义成了开区间的右边界即right指向的元素不参与区间。最后退出循环时left right指向的正是我们要找的位置。这个是C标准库lower_bound的做法。你看两种写法其实都对怕就怕你自己都没想清楚用的是哪种区间定义然后一会儿写left mid 1一会儿又写right mid - 1最后换来换去永远死循环。2.2 死循环是怎么炼成的很多刚学二分的朋友一定有过这种体验明明逻辑看起来没问题丢进去跑程序就是卡住不动了。一debug发现left一直等于某个值mid也一直是那个值。问题基本都出在mid的取整方向和区间收缩方式不匹配上。举个反面教材假如你的代码长这样while (left right) { int mid left (right - left) / 2; // 向下取整 if (nums[mid] target) left mid; // 左边界不前进 else right mid; }当left 2right 3时mid 2如果这时nums[2]小于target你让left midleft还是2mid算出来还是2循环就在这无限转圈了。这个问题的本质是mid向下取整时mid有可能等于left。所以你的更新逻辑里如果让left mid就可能导致left永远不动。记住一个口诀mid向下取整时更新要left mid 1mid向上取整时更新要right mid - 1。宁肯多写一步不要在这上面赌运气。3. C的STL里藏着二分查找的“完全体”聊完手写的版子我得说点更实用的C标准库其实已经把二分查找封装得很全面了。很多讲二分查找的文章讲完手写就直接收工完全不提STL这我觉得挺误导人的——工作中真正需要二分查找的地方能用STL就绝不要自己写为什么因为你手写的远不如标准库稳定、高效、泛化。3.1 std::binary_search最基础的存在性判断最简单的场景给你一个有序数组你只想判断某个数存不存在。#include algorithm #include vector std::vectorint nums {1, 3, 5, 7, 9}; bool found std::binary_search(nums.begin(), nums.end(), 5);这个函数返回bool内部就是二分查找时间复杂度O(log n)。但这个函数有个小限制它要求你的容器必须是有序的。你要是传进去一个乱序的结果就是未定义的而且多半是错的。3.2 std::lower_bound和std::upper_bound真正的边界利器实际工程里十次二分查找里八次不是为了判断存在性而是为了找到“第一个大于等于value的位置”或“第一个大于value的位置”对应标准库就是lower_bound和upper_bound。std::vectorint nums {1, 3, 3, 3, 5, 7}; auto it1 std::lower_bound(nums.begin(), nums.end(), 3); auto it2 std::upper_bound(nums.begin(), nums.end(), 3); // it1指向第一个3it2指向5区间[it1, it2)里全是等于3的元素这俩函数配合起来可以在O(log n)时间内求出一个值在有序数组中出现的次数int count std::upper_bound(nums.begin(), nums.end(), 3) - std::lower_bound(nums.begin(), nums.end(), 3);这个“区间长度法”是我在写那种“统计频次”的需求时最常用的实现一个需求只用一行而且绝对不出错。3.3 std::partition_point二分查找的进阶形态如果说lower_bound是“找值”的利器那partition_point就是“找条件分界点”的利器。它的原理很有意思它假设某个区间存在一个分界点分界点之前的元素满足某个谓词之后的元素都不满足然后通过二分查找快速定位这个分界点。std::vectorint nums {1, 3, 5, 7, 9, 2, 4, 6, 8}; // 前5个数都小于6后面的都不小于6 auto it std::partition_point(nums.begin(), nums.end(), [](int x) { return x 6; }); // it指向第一个不小于6的元素也就是2这其实就是“二分答案”的底层逻辑在单调的布尔序列上找分界点。理解了它你在LeetCode上遇到“山峰数组”求峰值、“旋转数组”求最小值这类题时思路会开阔很多。4. 二分的应用场景远比你想的广讲完语法和基础实现我特别想聊的是二分的应用场景。如果只把二分局限在“在一个排序好的vector里搜一个数”那太浪费了。这算法的真正威力体现在各种你想不到的抽象场景里。4.1 二分答案当“值域”代替“下标”时有一类经典题比如“在给定速度下能不能在指定时间内吃完香蕉”“给定运力能不能按时送完包裹”本质上都是“给定一个参数判断是否满足条件”而且这个判断结果随着参数的变化是单调的——参数小了不满足参数大了满足。这种场景就可以二分参数。比如“在一条直线上第k个元素是谁”、“木材切割成k段每段最大能多长”这类问题都对值域做二分。// 判断在速度speed下能否按时吃完所有香蕉 bool canFinish(vectorint piles, int speed, int h) { int need 0; for (int p : piles) { need (p speed - 1) / speed; if (need h) return false; } return true; } int minEatingSpeed(vectorint piles, int h) { int left 1, right *max_element(piles.begin(), piles.end()); while (left right) { int mid left (right - left) / 2; if (canFinish(piles, mid, h)) { right mid; } else { left mid 1; } } return left; }这就是“二分答案法”的模板先确定答案的最小可能值和最大可能值然后通过二分不断验证某值是否可行最终逼近最优解。这个套路非常万能比单纯的在数组上二分查找要高级一个层次。4.2 浮点数二分的精度控制有些时候搜索空间是连续的比如“求平方根”“求一个方程的根”需要对浮点数二分。这部分有个跟整数二分完全不同的点你没法用left right来判断终止因为浮点数理论上可以无限细分永远不等。我自己的习惯是用固定迭代次数来控制精度而不是用精度阈值。比如循环100次每次把区间缩小一半2^100约等于10^30这个精度远超float甚至double的有效位数了一定够用。double sqrt(double x) { double left 0, right x; for (int i 0; i 100; i) { double mid left (right - left) / 2; if (mid * mid x) left mid; else right mid; } return left; }这样写的好处是不会陷入死循环也不用担心精度阈值设的不合适。机器上面跑起来非常稳定。4.3 在旋转有序数组中查找LeetCode上那道经典的“搜索旋转排序数组”是理解二分查找“单调性”精髓的很好的练习题。数组本身不完全有序但分段有序可以通过比较mid和left的关系来判断左半段还是右半段是有序的从而决定搜索方向。这种题面试出现频率极高我建议每个想啃算法的人至少自己手写个两三遍。重点不是记答案而是理解它的判断逻辑最终你会形成一种“二分是手段单调是关键”的本能。5. C里碰过的二分练习题和错误反思既然说到刷题不妨分享几个我实际做过的、对理解二分很有代表性的题目和踩坑记录。这些题自己把代码写一遍比看十篇博文都有效。5.1 求“山峰数组”的峰顶索引这个题很像“二分答案”和“partition_point”的结合体。给你一个数组先升后降要求峰顶位置。这题的关键是发现峰值元素大于右侧元素和左侧元素而数组在某一点前后单调性发生了变化。用二分对比mid和mid1的值如果mid mid 1说明峰顶还在右边left左移否则在左边right收缩。逻辑非常顺是一道很好的“边界单调性”综合训练题。5.2 平方根的笔试题惨案有一次笔试题目是求一个整数的平方根整数部分比如8的平方根返回2。我当时手一抖写了个int mid (left right) / 2导致在处理很大的整数时溢出left变负数瞬间炸裂。后来笔试完复盘才意识到自己已经忘了那个“经典溢出坑”。从那以后我就给自己立了一条规矩任何时候写二分一律left (right - left) / 2从来不写(left right) / 2。这是一种“防呆设计”不用考虑你当时脑子清不清楚只要写成这样就一定不会出溢出问题。5.3 向量里的lower_bound误用有一次在项目里优化一个高并发读取模块我先拿到一个有序数组然后想用它加速查询直接lazy地用std::find线性扫。后来性能报告出来发现这个模块成了热点。换成lower_bound之后单次查询从O(n)变成O(log n)整个接口的中位延迟降了一个数量级。这件事给我的教训是算法优化的第一课是识别出你的代码里那些看起来不起眼、实际上调用次数极高的线性查找。工程优化从来不是花哨地把代码重构成花而是把复杂度给降下来。6. 实际工程里的二分参数、注意事项与性能观察前面讲的都是算法和语法层面现在落到工程现场。实际项目里的二分查找永远伴随着数据量、缓存、内存布局这些“糙事”。这也是很多刷题党转工程时最大的落差你在LeetCode上把二分背得滚瓜烂熟结果到了真正开发发现瓶颈根本不在这里。6.1 分支预测与性能误区一个常见的误解是“二分查找比线性查找永远快”。这话只说对了一半。二分查找是O(log n)线性是O(n)在数据量大且要多次查找时二分肯定是王者。但如果你只查找一次而且数据量小到几十个元素以内线性查找并不一定慢——因为线性访问是顺序的CPU缓存命中率高而二分跳来跳去缓存命中率低。我做过的实测在百万元素的有序数组里二分查找的耗时大约是几十纳秒级别但前提是数组是连续内存vector。如果数据结构是链表虽然逻辑上也是有序的二分根本没法O(log n)地随机访问那时候强行二分反而没法发挥优势。6.2 当数组大到缓存装不下时当你的有序数组大到一定规模比如上亿个64位整数那二分查找每轮跳转访问的内存位置大概率不在缓存里需要去内存里取。每一轮虽然只有O(1)次访问但内存访问的延迟是缓存的几十倍所以实际耗时也不低。这时候有些高级优化方案比如“插值查找”或者“分块索引二分”通常在工程中值得考虑。不过这些属于进阶话题了这里提一句主要是想告诉你算法复杂度只是理论下界工程性能永远是“算法复杂度数据存放位置硬件特性”三者共同作用的结果。6.3 自定义比较器时的一个大坑STL的lower_bound和binary_search都支持自定义比较器。注意所有二分相关的STL函数对“有序区域”的判断用的比较逻辑必须和排序时的比较逻辑完全一致否则语义就乱了。最常见的问题是sort的时候用了自定义结构体的字段排序查找的时候也传了同样的比较器但字段的“等于”逻辑没处理好结果明明存在的数据却查不到。我自己就在一个地理坐标相关的项目里踩过类似的坑。结构体按经纬度排序查找时用“经度相同”做比较器判断相等但两个点在浮点数上永远不可能真正相等导致lower_bound永远返回end。后来改成先按“浮点精度对齐”再比较问题才解决。浮点数比较是个永恒的话题。凡是涉及浮点的二分查找强烈建议先做一层量化或者使用epsilon容差不要拿去判定相等。7. 二分查找的“周边知识”C里的一整套二分姿势写到这里可能有人会问所以二分查找到底有没有一个“终极完美模版”我的答案是没有。但如果你理解得够深所有二分都长得差不多。7.1 手写代码时的最小化模板这里给出我调试过无数遍之后日常最常用的一套模板适用于绝大多数整数二分求第一个满足条件的最大/最小索引。核心思路是维护开区间[left, right)把问题转化为“在布尔数组上找第一个true”。// 求第一个使check(mid)为true的下标 int l 0, r n; // [l, r) 左闭右开 while (l r) { int m l (r - l) / 2; if (check(m)) { r m; } else { l m 1; } } return l;这套的优雅之处在于left始终指向“答案左边第一个不满足的位置”right始终指向“答案右边第一个满足的位置”。最终left和right重合就是第一个满足条件的位置。你不用关心什么mid 1还是mid只要记好“满足就往回收右边界不满足就往前进左边界”就行。7.2 三个面试必问的变化有了这套理解之后面试官只要稍微变形你都能立刻反应过来找最后一个小于等于target的下标求第一个大于target的下标再减1。找第一个大于等于target的下标就是lower_bound。找第一个等于target的下标先求lower_bound再检查它指向的元素是否等于target。这三件事本质都是一件事给有序数组找一个“分界点”。你从“找边界”再回到“找数”就会特别轻松。7.3 二分和STL函数的协作习惯再补充一个工程习惯。但凡你的数据是动态变化的比如要频繁插入、删除、查找我不建议你用一个vector来维护那份有序数据然后反复二分——插入和删除是O(n)的二分的O(log n)完全被插入的O(n)吞掉了。这种情况下更合适的数据结构是std::set或std::map它们本身就是红黑树提供了O(log n)的查找和插入。但注意set/map不支持随机访问下标如果你还需要“第几个元素”这种操作就得考虑平衡树或者跳表了。另外如果你的查询是多维度的比如二维平面上查最近点裸的二分需要先用“线段树套平衡树”之类的数据结构改造复杂度会指数级上升。这种场景找专业库比硬写二分靠谱。8. 常见问题速查表把过去遇到的各种二分疑难杂症整理成一个速查表你遇到直接对着查就行。症状可能原因解决办法死循环不退出mid向下取整时left mid确保mid正确更新要么left mid 1查找结果总是差1区间开闭定义混乱统一用左闭右开或者全闭区间别混用mid计算溢出用了(left right)/2换用left (right - left)/2找不到目标但元素存在比较器逻辑不一致检查lower_bound用的比较器和排序比较器是否一致浮点二分精度不足用判断左右边界改固定迭代次数或使用epsilon容差结果正确但性能差每轮访问频繁跳出缓存考虑块索引、插值查找、或更改数据结构传入无序数组排序被覆盖或漏排使用前先确认序列有序这个表我几乎每次做二分相关分享都会放出来。不是因为它有多高深而是因为它凝练了常见的坑能让后来的人迅速定位问题。9. 对初学者的学习路径建议很多跑来找我问算法的人最焦虑的问题就是“我要不要背模板”。我的回答非常明确刚开始可以背但千万别停在背上。背模板只能让你写出能跑的代码但不能让你在边界条件变形的面试题里生存下来。我给的建议路径是这样的先搞清楚“区间不变式”用笔在纸上画几个例子每次mid在哪、更新之后left和right变成多少、区间是怎么缩小的。这一步花上半小时比你刷5道二分题都管用。然后用上面那套左闭右开的模板把LeetCode上几个经典的二分题刷一遍从最基础的搜索旋转排序数组、找到峰值到稍微难一点的数组中的第K个最大元素、分割数组的最大值逐步体会“单调性从哪来”。最后回到工程里看看自己项目里哪些地方还在用线性扫描处理有序数据试着用std::lower_bound替换掉感受一下性能差异。这一步会强烈激发你对算法学习的真实兴趣。10. 一个二分的“高级感”小技巧用二分求最长递增子序列的长度既然聊到这了我再分享一个我自己觉得非常巧妙的应用——用二分求最长递增子序列LIS长度。你没看错LIS的经典O(n log n)解法底层就是二分。思路是维护一个“当前最小递增尾部数组”遍历原序列对每个元素用lower_bound找它在尾部数组中能替换的位置。如果找不到就往后加。这个过程的正确性靠的正是二分查找的单调性。int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }这段代码很短但信息量很大。我第一次看懂这个解法时有一种“原来二分真的能长成这样”的震撼感。理解它之后你对二分的认知就不会再停留在“有序数组找数”上了。11. 最后的实战提醒最后分享一点个人化体会。每次写二分之前建议先花10秒钟想清楚**你要找的到底是什么是数值相等的位置还是第一个满足条件的位置你的搜索区间用的是开还是闭**这三个问题想明白了代码几乎不会出错。我这些年写的二分绝大多数bug都出在这三个问题没想清楚的时候而不是出在语法不熟练上。另外一个习惯是写完二分之后一定要补上边界测试空数组、只有一个元素、目标在开头、目标在结尾、目标不存在但在范围内、目标小于所有值、目标大于所有值。这几个用例一跑代码的健壮性立刻就清楚了。很多看起来天衣无缝的实现都是在这几个用例上破功的。二分查找不是什么高深莫测的算法它只是“充分利用单调性缩小搜索范围”这个朴素思想的严谨表达。但恰恰是这份严谨逼着你把每一个边界都抠清楚。能在C里把这小几十行代码写对、写稳、写通用你算法功底的扎实程度其实已经超过很多自称“熟悉算法”的人了。
