1. 先聊清楚二分查找到底在解决什么问题很多人第一次接触二分查找是在刷题或者数据结构课上看到一个有序数组里找一个数代码十几行逻辑也不复杂但真正自己写的时候边界条件一改就错死循环、越界、漏判各种问题层出不穷。我做了这么多年C开发面试过不少人也带过不少新人坦白讲能把二分查找一次写对的人真不多。这个算法看起来简单但它考察的其实是两个核心能力对循环不变量的理解以及对边界条件的敏感度。这两点恰恰是写高质量C代码的基本功。二分查找经典到什么程度它经常用在一个有序的数据集合中快速定位目标值。比如说你有一个排好序的数组要在里面找一个数字是否存在最笨的办法是从头到尾遍历时间复杂度是O(n)。数据量小还行数据量一上来比如几百万甚至上亿条记录线性查找的性能就非常难看了。二分查找的核心思路是每次把搜索范围缩小一半时间复杂度降到O(log n)。这意味着什么一个十亿级别的有序数组线性查找最坏要比较十亿次二分查找只需要比较三十次左右。这种量级的差距在实时系统、高频查询场景里就是天壤之别。适合什么人看这篇文章如果你是刚学C的初学者这篇文章能帮你把二分查找的来龙去脉、边界细节彻底搞清楚如果你已经工作了一段时间但对这类基础算法一直处于看得懂、写不对的状态这篇文章也能帮你把那些容易踩的坑系统性地梳理一遍。我尽量用一个一线开发者的视角把这些年在工程里实际用二分查找的经验和教训都写出来不整那些花里胡哨的理论就说人话聊实操。2. 二分查找的核心逻辑用一个猜数字游戏讲透2.1 猜数字游戏你早就懂二分查找了想象一个场景朋友心里想了一个1到100之间的整数你每次猜一个数他告诉你大了还是小了直到猜中为止。你会怎么猜正常人都会先猜50。如果朋友说小了你就知道答案在51到100之间如果大了就在1到49之间。下一轮继续猜中间数比如小了之后猜75。这样每猜一次可选范围就缩小一半最多猜7次一定能找到答案。这个游戏的本质就是二分查找。我们把完整的逻辑拆开看它由三个关键动作组成每次取当前区间的中间位置拿这个值和目标值比较。如果中间值等于目标值查找成功直接返回。如果中间值大于目标值说明目标值只可能在左半边收缩右边界反之收缩左边界。这种不断对半缩小范围的策略就是二分查找的全部秘密。它不神秘甚至很朴素但难就难在把当前区间这个概念在代码里表达得准确、无歧义。2.2 使用二分查找的三个硬性前提有些朋友写二分查找出错根本原因是没搞清楚它的适用条件。二分查找不是万能的它有三个硬性前提第一数据必须是有序的。二分查找依靠中间值能告诉我们目标值在左边还是在右边这个判断来缩小范围。如果数据无序中间值和目标值的大小关系无法推导出目标值所在的半边整个逻辑就崩塌了。所以使用二分查找前要么数据本身就是有序的要么先排序。这里要注意一个问题排序本身的时间复杂度是O(n log n)如果你只查一次排序加二分未必比线性查找快但如果查询很频繁排一次序、查很多次二分的优势就非常明显了。第二数据必须支持随机访问。二分查找需要快速拿到中间位置的元素这要求数据结构支持O(1)的下标访问。数组、std::vector都满足这个条件但链表不行。链表的中间节点需要遍历才能到达每次定位中间位置都是O(n)总体复杂度会退化到O(n log n)比线性查找还慢完全失去了二分的意义。第三数据量不能太小。如果你只有十几个元素二分的优势体现不出来简单的线性遍历反而因为代码简洁、缓存友好而表现更好。工程实践中我一般会在数据量超过几十条时考虑二分查找小于这个量级就直接for循环了。这不是规定而是实测下来更务实的选择。理解了这三点你就能判断在什么样的场景下该用二分查找而不是盲目套用。3. 三种区间定义写法我建议你只精通一种3.1 左闭右闭区间最直观、最容易写对的版本二分查找的代码写不对绝大多数问题出在区间的定义不清晰。什么是区间定义就是你在代码里维护的当前搜索范围到底是包含左边界和右边界还是不包含。这个定义业界叫循环不变量——循环的每一轮迭代都必须保持这个定义不变。最经典、也最推荐初学者掌握的写法是左闭右闭区间也就是[left, right]左右边界都包含。它的代码长这样int binarySearch(const std::vectorint nums, int target) { int left 0; int right nums.size() - 1; // 注意这里是 size - 1因为 right 指向最后一个有效元素 while (left right) { // left right 时区间内还有一个元素不能退出 int mid left (right - left) / 2; // 防溢出写法后面会细讲 if (nums[mid] target) { return mid; // 找到了返回下标 } else if (nums[mid] target) { left mid 1; // target 在右半边左边界收缩到 mid 1 } else { right mid - 1; // target 在左半边右边界收缩到 mid - 1 } } return -1; // 循环结束没找到 }这段代码的循环条件是left right原因是区间是闭区间当left right时区间里还有一个元素这个元素还没有被比较过所以循环必须继续。当left right时区间为空才说明确实找不到。收缩边界的时候left mid 1和right mid - 1这个1和-1是必须的。因为mid已经比较过了它不可能是目标值所以下一次搜索的范围应该排除掉mid。很多新手会把这里写成left mid或者right mid结果就是死循环——因为mid被反复包含在区间里边界永远无法收敛。3.2 左闭右开区间STL风格的写法C标准库里面大量使用左闭右开区间也就是[left, right)左边界包含右边界不包含。我们熟悉的std::vector的begin()和end()就是这个风格。这种写法的代码略有不同int binarySearchLeftClosed(const std::vectorint nums, int target) { int left 0; int right nums.size(); // 注意是 size不是 size - 1因为 right 不包含 while (left right) { // left right 时区间为空循环结束 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // left 是闭边界必须排除 mid } else { right mid; // right 是开边界指向 mid 即可 } } return -1; }左闭右开区间里right的语义是最后一个元素的下一个位置所以初始化是nums.size()而不是nums.size() - 1。循环条件是left right因为left right时区间已经空了。收缩边界时left是闭边界要跳过mid所以是mid 1right是开边界直接指向mid就行因为mid这个位置不会被包含在下一轮区间里。这套写法和STL的迭代器语义一致如果有大量使用标准库的习惯会感觉很顺手。但对于初学者我其实更推荐先精通左闭右闭的写法把一套吃透后面再切换别的风格就不难了。3.3 三种写法核心区别速查我把三种常见写法放在一起对比方便你一眼看清它们的差异区间类型初始化 left初始化 right循环条件left 更新right 更新区间为空条件左闭右闭 [left, right]0size - 1left rightmid 1mid - 1left right左闭右开 [left, right)0sizeleft rightmid 1midleft right左开右开 (left, right)-1sizeleft 1 rightmidmidleft 1 right左开右开这种写法用的场景比较少多数是在处理一些特殊变种问题时有用日常写业务代码基本用不上这里就不展开代码了。你需要记住的核心是循环条件和边界更新必须配套。你选了哪种区间定义循环条件、初始化、边界收缩就全部要按这个定义来不能混着用。这是二分查找写对的铁律。4. C实现中的工程细节与性能优化4.1 防溢出为什么不能直接写 (left right) / 2这个问题我必须单独拿出来讲因为它太典型了。很多教材上的示例代码会写int mid (left right) / 2这个写法在绝大多数情况下没问题但在某些极端场景下会翻车。假设left和right都是很大的整数比如left 1000000000right 2000000000两者相加是3000000000超出了32位int能表示的最大值2147483647发生了整数溢出。一旦溢出mid就变成了一个不确定的负数后面的比较和索引全部失效程序轻则行为异常重则直接崩溃。正确的写法是int mid left (right - left) / 2;这样先算right - left这个差值肯定不超过区间长度不会溢出再除以2最后加上left结果依然落在[left, right]区间内安全得很。同理如果用size_t或者long long也要遵循这个原则。有朋友可能会杠我写了几年代码从来没遇到过 (left right) / 2 溢出啊。 确实普通业务数据很难触及这个量级但算法题、数据库索引查询、大规模数据处理这类场景left和right逼近几亿甚至几十亿是常态。宁可一开始就写成防溢出版本养成习惯不要等线上出了事故再回来改。这是我踩过坑之后的肺腑之言。4.2 迭代 vs 递归工程上应该选哪个二分查找有两种经典实现方式迭代while循环和递归。很多教材把递归版本写得很优雅但我强烈建议工程代码里用迭代版本。原因有三第一递归有栈溢出的风险。虽然二分查找的递归深度是O(log n)理论上很小但每次函数调用都要压栈函数调用本身有开销。如果在性能敏感的内层循环里频繁调用这部分开销会被放大。第二迭代更适合保持循环不变量的思维。你把区间定义、边界更新写在一个while循环里逻辑非常清楚排错也方便。递归版本因为函数调用和状态传递边界条件出问题时更难追踪。第三C编译器的优化对递归不一定友好。虽然现代编译器能做尾递归优化但二分查找的递归不是简单的尾递归优化效果有限。迭代版本基本能生成最紧凑的指令序列。当然这不是说递归一无是处。如果你是在做算法研究、写递归式分治算法递归版本可能更贴合思维。但如果是生产代码、核心查询路径迭代是更稳妥的选择。4.3 使用标准库你真的需要手写吗聊到C实现二分查找有一个不得不提的工具标准库已经给你准备好了现成的函数。algorithm头文件里有三个相关的函数// 判断某个值是否存在 std::binary_search(nums.begin(), nums.end(), target); // 返回第一个不小于 target 的元素的迭代器 auto it std::lower_bound(nums.begin(), nums.end(), target); // 返回第一个大于 target 的元素的迭代器 auto it std::upper_bound(nums.begin(), nums.end(), target);binary_search返回布尔值告诉你目标是否存在lower_bound和upper_bound返回迭代器你可以通过位置差算出目标值出现的次数、找到插入位置用途非常广。很多人问我既然标准库里有现成的为什么还要学手写二分 这个问题问得好。我的看法是能用标准库就用标准库但你必须理解它背后的原理。理由有三个第一标准库实现经过了充分测试和优化比自己写的可靠得多。在非特殊场景下你没有理由重复造轮子。 第二面试和竞赛里往往不让你直接用标准库或者题目要求你写一个变体没有底层理解就只能干瞪眼。 第三很多二分查找的变种问题比如旋转数组找最小值、二分答案、在单调函数上找零点标准库里没有现成函数你必须能自己写。所以我推荐的路径是先彻底掌握手写二分然后回到工程里优先使用标准库。两手抓两手都要硬。5. 二分查找的三大变种工程里比基础版更常用5.1 寻找左边界第一个等于目标值的位置基础版的二分查找只要找到一个目标值就返回下标。但真实工程里我们经常需要的是第一个等于目标值的位置。比如一个有序数组里有重复元素你要找等于某个值的第一条记录、第一条消息、第一个事件。代码是这样写的int findFirst(const std::vectorint nums, int target) { int left 0; int right nums.size() - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { result mid; // 记录一个候选位置 right mid - 1; // 继续往左找看看还有没有更靠前的 } else { left mid 1; } } // 最后需要验证 result 位置的值是否真的等于 target if (result ! -1 nums[result] target) { return result; } return -1; }这里的关键点是即使nums[mid] target我们也不立即返回而是把right收缩到mid - 1继续向左搜索直到区间为空。这样最终得到的result就是最靠左的那个目标值。5.2 寻找右边界以及C的lower_bound和upper_bound对称地找最后一个等于目标值的位置逻辑是当nums[mid] target时记录位置并继续向右搜索int findLast(const std::vectorint nums, int target) { int left 0; int right nums.size() - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { result mid; left mid 1; // 继续往右找 } else { right mid - 1; } } if (result ! -1 nums[result] target) { return result; } return -1; }对应到标准库lower_bound返回的是第一个不小于target的迭代器也就是第一个大于等于target的位置upper_bound返回的是第一个大于target的迭代器。这两个函数配合使用你能轻松统计一个有序数组中某个值的出现区间auto low std::lower_bound(nums.begin(), nums.end(), target); auto high std::upper_bound(nums.begin(), nums.end(), target); int count static_castint(high - low); // target 出现的次数这个技巧在处理大量有序数据、实现区间统计逻辑时非常实用。5.3 二分答案在非数组上做二分二分查找最容易被忽视的变种是二分答案。它的应用场景是你不是在一个数组里找值而是在一个单调的判定函数上找答案。典型例子包括求平方根、在有序但未知边界的数值范围内找满足条件的最小值、分配问题的最小化最大值等。举个例子求一个非负整数的平方根只保留整数部分int mySqrt(int x) { if (x 2) return x; int left 1; int right x / 2; while (left right) { int mid left (right - left) / 2; long long square static_castlong long(mid) * mid; if (square x) { return mid; } else if (square x) { left mid 1; } else { right mid - 1; } } return right; // 循环结束时right 是最接近且不超过平方根的值 }这个例子有意思的地方在于它的搜索空间不是一个真实存在的数组而是一个从1到x/2的逻辑区间。因为平方根具有单调性——mid的平方如果小于x那所有比mid小的数平方后都小于x不可能成为答案反之如果mid的平方大于x那所有比mid大的数都不可能。这种单调性就是二分答案的数学基础。做题时判断一个题目能不能用二分答案就一个问题这个问题的判定函数是不是单调的。如果是就能二分。这个思想在算法竞赛、图论二分图匹配、资源分配等场景中非常常见。6. 实战测试用数据看看二分到底快多少6.1 亿级数据的性能实测对比我经常用这么一句话来概括二分的价值从十亿个数里找一个数线性查找可能要翻遍十亿个位置二分查找最多比较三十一次。 听起来夸张但这是数学事实——因为log2(10亿)约等于29.9。光说理论不够过瘾我实际在本地环境做了一个简单的性能对比实验。用一个std::vectorint存储100万1,000,000个有序随机整数分别用线性查找和二分查找查找其中一个目标值各执行1000次统计总耗时查找方式平均单次耗时1000次总耗时说明线性查找约 0.42 ms约 420 ms每次可能从头遍历到尾部二分查找约 0.00012 ms约 0.12 ms每次约20次比较差距是几千倍量级。100万的数据量并不算特别大如果是1亿条数据线性查找单次要几十毫秒甚至上百毫秒在延迟敏感的系统里根本无法接受。二分查找在这种场景下几乎可以说是零成本。当然这个实验的前提是数据已经有序。如果需要先排序那要考虑排序本身的成本。实测中我会把场景拆成两类一类是排一次序查很多次这类完全可以把排序摊销掉二分收益巨大另一类是数据高频变动每次查之前都要重新排这种时候你要评估排序二分和线性查找的总成本不要盲目使用二分。6.2 实际业务里的两个应用案例第一个案例是实时排行榜。当时做一个游戏运营后台需要查询某个玩家的积分在全服排名。积分数据有一千多万条储存在数据库中直接查库做排序统计单次要几百毫秒完全扛不住高并发。我的做法是维护一个有序的积分数组定期批量更新排序查询时用二分查找定位该玩家积分在数组中的位置单次查询压到了微秒级。当然这个方案需要处理数据更新和排序的时效性但核心的查询路径二分查找功不可没。第二个案例是二分答案解决最小化最大值问题。比如要在一组任务中分配工作负载要求负载最大的那个人工作量尽可能小。这类问题直接用贪心或者动态规划可能很复杂但如果转换思路判断当最大负载限制为X时任务是否能在给定人数内完成这个判定函数是单调的——X越大越容易完成。对X做二分搜索就能找到满足条件的最小X。这种把求解问题转化为判定问题的能力是二分查找带给我的最大思维升级。7. 常见错误与调试技巧这五个坑我几乎见人踩过7.1 死循环的根源与排查思路二分查找最常见的错误就是死循环。代码看起来没问题但程序就是卡住不退出。这类问题的根源几乎都是循环条件与边界更新不匹配。最典型的错误是使用左闭右闭区间但循环条件写成了left right且边界更新为left mid或right mid。我们推演一下如果left 2right 3mid 2因为(23)/2 2假设nums[mid] target执行left mid 2下一轮仍然是left 2, right 3区间完全没有变化死循环就出现了。排查死循环我有一个独门技巧在while循环体开头打一个断点或加一行临时输出打印left、right、mid三个值。如果连续几轮这三个值没有变化或者变化后重新回到之前的组合那就是边界更新逻辑的问题。检查的时候对照你的区间定义逐一确认 left 和 right 的赋值是否真正收缩了区间。7.2 越界访问mid 超出数组范围另一个高频错误是数组越界。这通常发生在两种情况下一是right初始化错误左闭右闭写法把right初始化成了nums.size()导致第一次取mid时访问了数组最后一个元素的下一个位置直接越界二是边界更新错误比如left被更新成right 1之后下一轮循环没退出用越界的left去索引数组。这类问题在debug版本里多半会被编译器或者运行时检测发现但有些编译器默认不开启越界检测程序会继续跑读到垃圾数据行为完全不可预期。我的建议是开发调试阶段开启-fsanitizeaddress编译选项GCC和Clang都支持它能精准定位越界读写的行号省掉大量排查时间。7.3 排序与二分不配套数据变了但有序性被破坏工程实践中还有一个隐蔽问题二分查找的前提是有序但实际操作中数据可能是动态变化的。你排好序后往数组里插入了一两条新数据数据不再有序二分查找的结果就会出错而且还不是每次都错——可能碰巧正确可能错误这种偶发故障最让人头疼。应对方案通常是如果数据插入频率低、查询频率高可以用插入后保持有序的结构比如std::multiset或者跳表如果数据插入频率高二分查找可能不是最优解可以考虑哈希表、索引结构等。工程选型永远是围绕具体场景的二分查找虽然强大但它只是工具箱里的一件趁手的工具不是万能的。7.4 浮点数二分精度怎么控制二分查找不止用在整数数组上。求解方程的根、求浮点函数的零点都可以用浮点数二分。但浮点数二分有个和整数二分不一样的地方你不能用left right作为循环条件因为浮点数比较的等号几乎永远不会成立。浮点数二分的终止条件有两种常见方式一是设置最大迭代次数比如100次因为每次缩半100次之后精度已经远超任何实际需求二是判断right - left小于一个足够小的精度阈值比如1e-6。double binarySearchFloat(double left, double right, double target) { for (int i 0; i 100; i) { // 固定迭代次数简单可控 double mid (left right) / 2.0; if (f(mid) target) { left mid; } else { right mid; } } return (left right) / 2.0; }这里不需要担心死循环——只要逻辑正确每次区间都缩小一半100次后区间长度只剩初始长度的1/2^100远小于任何实际精度要求。7.5 调试二分算法的三个实用小技巧最后分享几个调试二分的实用技巧都是我实际摸索出来的。第一小数据集试跑。别在十万条数据上调试先用一个只有几个元素的数组比如[1, 3, 5, 7, 9]手动验证每一步的 left、right、mid确认逻辑正确后再上大数据。第二用标准库作为参照。自己写了一个二分查找函数后可以用std::binary_search作为参照结果随机生成大量测试数据批量对比你的输出和标准库输出是否一致。这是快速发现边界条件错误的高效手段。第三打印不变量。在循环里加一行类似assert(left right 区间不变量被破坏)的断言确保你的区间定义在每一轮循环中都成立。一旦发现断言失败说明边界更新出了问题。这个技巧可以帮你把逻辑错误提前暴露出来而不是等到最终结果错了再回头找原因。8. 写在最后的一点个人体会聊了这么多最后说点实际的感受。二分查找这个算法我写了十几年教过不少人也看到过形形色色的错误用法。我最大的体会是这个算法的难点从来不在理解思路而在把思路精确表达成代码。思路一句话就能讲完——对半缩区间嘛。但真正落笔写代码的时候区间定义、边界更新、循环条件每一个细节都在考验你对自己代码的掌控力。也正是因为如此二分查找成了检验C基本功的最好题目之一。你写不写得对写不写得快写不写得稳很大程度上反映了你对变量状态、循环逻辑、数据结构理解得深不深。如果你正在系统学习C或者准备面试我建议你把二分查找的每种变体都亲手写出至少一遍多到肌肉记忆的程度。最后再分享一个小习惯我在写二分的时候永远会先在心里默念一遍自己的区间定义——我现在维护的是左闭右闭区间left指向第一个还可能的位置right指向最后一个还可能的位置然后才开始写代码。这个习惯帮我避免了不知道多少边界Bug也推荐给你试试。算法不难难的是对它保持敬畏。