尧图网页设计 
二分查找大概是很多人学算法的“入门第二课”——第一课通常是排序。但老实说能把二分查找写到一次提交就通过的人从来都不算多。那个经典的“循环里到底用 left right 还是 left right”“mid 要不要加 1”“会不会死循环”的纠结几乎每个用 C 写过二分的人都经历过那么几回。这篇文章用我自己踩过的坑把二分查找这件事用 C 完整讲一遍从最基础的模板开始到边界查找、实数域二分、二分答案、STL 里的现成轮子lower_bound、upper_bound最后再拆几个面试高频题轮转数组找最小值、找峰值。不管你是刚学算法的学生还是在准备面试、想查漏补缺的开发者照着这篇文章把代码敲一遍、把边界想明白后面遇到二分的题基本不会再慌。1. 二分查找的本质与适用边界1.1 为什么有序和随机访问是硬前提先说一个最容易被忽略的点二分查找的前提不只是“有序”还需要“可随机访问”。序列有序我们才能根据中间元素和目标值的大小关系一次性排除掉一半的数据支持随机访问我们才能用 O(1) 的时间拿到任意下标对应的元素。这两个条件缺一不可。对比一下就清楚了数组天然支持随机访问所以 vector、array 上直接二分没问题。链表虽然可以有序但你要取中间元素必须从头遍历。每次“二分”都要付出 O(n) 的定位成本整体复杂度退化到 O(n log n)还没线性扫描快。所以如果面试里有人问“链表能不能做二分查找”标准答案不是“能”而是“能做但没必要复杂度反而更差”。C 里你要是想在 list 上二分STL 也不会给你基于随机访问迭代器的 lower_bound而是走线性扫描的通用版本。1.2 复杂度优势到底体现在哪二分查找的时间复杂度是 O(log n)。这个“log”有多强我用具体数字说话数据规模 100 万线性查找最坏要比较 100 万次二分最多比较 20 次。数据规模 10 亿线性查找几十亿次基本不可接受二分最多比较 30 次。增长非常慢。你每多比较一次能排除的数据范围就翻一倍。换句话说二分查找把“规模”问题变成了“深度”问题这是几乎所有高效算法共通的底层逻辑——分治。当然前提是你先得排序。排序的复杂度是 O(n log n)所以“排序 二分”这套组合拳适合“一次排序、多次查找”的场景。如果只查一次直接线性扫反而是最优的。这个场景判断我后面在实战章节再展开。1.3 二分不只是“查数字”本质是“砍半搜索”很多人对二分的理解停在“在一个有序数组里找一个数”其实二分的通用模型是在一个“具有二段性”的序列上通过中间值判断应该往左还是往右走。什么叫二段性就是存在一个分界点分界点的一侧全部满足某个性质另一侧全部不满足。比如有序数组中“元素 target”这个条件在某个下标之后全为 true之前全为 false。一个先降后升的数组“最小值”左边右边的单调性不同。一个单调函数 f(x)“f(x) target”这个条件从某个 x 开始恒成立。只要能定义出这种“一侧全真、一侧全假”的性质就能用二分去找那个分界点。很多人学二分觉得模板背不住其实是没有理解这个统一模型。后面讲边界查找和二分答案时全部围绕这个模型展开。2. C 标准实现与边界处理闭区间和半开区间两种模板2.1 先给一套“背下来不会错”的闭区间模板先说结论我平时写二分默认就是闭区间 [left, right] 这套模板。它最直观也是大部分教材的写法。下面是标准实现// 在升序数组 nums 中查找 target返回下标找不到返回 -1 int binarySearch(const vectorint nums, int target) { int left 0; int right (int)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; } } return -1; }核心规则有三条循环条件是 left right因为闭区间下 left 和 right 都可能指向还未检查的合法位置。mid 用left (right - left) / 2而不是(left right) / 2避免整数溢出。虽然现代 64 位环境下 left right 一般不会溢出但这是好习惯面试官看了也舒服。left 更新为 mid 1right 更新为 mid - 1。因为 mid 已经比较过了下一步必须在它的两侧找。这套代码看似简单真正容易错的地方是“区间收缩后会不会跳过答案”。可以想一下当 nums[mid] target 时答案只可能在 mid 右边所以 left mid 1 是安全的当 nums[mid] target 时答案只可能在 mid 左边right mid - 1 同样安全。while 循环每次都会让区间长度至少减 1所以不会死循环。2.2 半开区间模板理解 STL 的思维起点闭区间模板好写但你要是去看 C STL 的 lower_bound 实现会发现它用的是“左闭右开”区间也就是 [first, last)。这套风格的典型实现长这样// 返回第一个 target 的元素下标类似 lower_bound int lowerBound(const vectorint nums, int target) { int left 0; int right (int)nums.size(); // 注意right 是开区间端点指向最后一个元素的下一个位置 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这套模板为什么 long 是左闭右开因为 STL 的迭代器设计本身就是“左闭右开”begin() 指向第一个元素end() 指向最后一个元素的下一个位置end() 是“哨兵”不指向真实元素。所以[first, last)可以完整表达一个空区间这是 C 标准库风格的底层习惯。半开区间模板的关键区别初始 right nums.size()不是 size() - 1。循环条件是 left right不是 left right。因为当 left right 时区间为空没必要再循环。right 收缩时指向 mid不做加减。因为右端是开区间right 指向的位置可以留给下一轮继续判断。循环结束时 left rightleft 就是第一个不满足nums[mid] target的位置也就是第一个 target 的位置。这套模板天然处理了“找不到精确值”的场景返回的是应该插入的位置而不是 -1。这也是 STL 把 lower_bound 设计成“返回迭代器”而不是“返回 bool”的原因。这里容易困惑的是“right mid 而不是 right mid - 1”。画个图就清楚了假设数组是 [1, 3, 5, 7]target 4mid 一开始是下标 1值为 3因为 nums[mid] target所以 left 变成 2下一轮 mid 是下标 2值为 5因为 nums[mid] target我们把 right 设置成 2。此时 left right 2直接返回 2这个位置就是 5就是第一个大于等于 4 的元素。正因为 5 这一轮还没“被排除掉”right 才能指向它这就是 right mid 的意义。2.3 两种模板怎么选看你要的是“找位置”还是“验存在”闭区间模板适合“查找精确值是否存在”比如搜索某个用户 ID、邮件地址。半开区间模板适合“找边界”比如第一个大于等于某个阈值的位置。实际工程里lower_bound 这类边界查找用得更频繁因为数据库索引、区间统计、二分答案全都依赖它。我的习惯是面试写算法题时如果题目明确是“查找某个值存在返回下标”用闭区间模板。如果题目是“找边界”“找插入位置”“二分答案”用半开区间模板。两种模板别混用。一旦定下来循环条件和收缩规则就要全部配套否则左指针右移规则、右指针收缩规则各用各的很容易出死循环或漏解。3. 二分查找的变体与边界查找不只是“找一个数”3.1 找左边界、右边界最常考的二分变形很多题目不满足于“找到 target 就返回”而是问你 target 第一次出现的位置、最后一次出现的位置或者统计 target 在数组里出现了几次。这种问题在闭区间模板上扩展一下就能解决。找左边界第一个等于 target 的下标int firstEqual(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; int ans -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { ans mid; // 先记录当前候选位置 right mid - 1; // 继续往左搜 } else { left mid 1; } } if (ans ! -1 nums[ans] ! target) return -1; return ans; }找右边界最后一个等于 target 的下标int lastEqual(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; int ans -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { ans mid; // 先记录当前候选位置 left mid 1; // 继续往右搜 } else { right mid - 1; } } if (ans ! -1 nums[ans] ! target) return -1; return ans; }这两种写法的思路是一样的不着急 return而是把“找到 target”变成一个持续逼近的过程。每次命中 target就记下当前下标然后继续向左或向右压缩区间直到区间清空。最后 ans 里存的就是最左最右的那个目标位置。统计出现次数也简单lastEqual - firstEqual 1前提是存在。不过这里我要提个醒——如果只是统计次数STL 里有更优雅的做法equal_range一趟搞定后面第四部分会专门讲。平时练习用上面的代码理解原理工程上直接用 STL两头都顾到。注意一个细节上面的代码里ans初始化成 -1最后还要二次检查 nums[ans] 是否等于 target。这是因为循环结束时 ans 可能是“大于等于 target 的最左位置”或者“小于等于 target 的最右位置”但 target 可能根本不存在。比如数组 [1, 3, 5]target 2左边界算法得到的 ans 是下标 1值为 3必须检查值才能确定 2 是否真的存在。3.2 实数域二分控制迭代次数代替判断相等前面都是整数数组能判断nums[mid] target。但遇到实数二分比如二分浮点答案时相等判断就废了——浮点数没法精确比较也不能用整数区间的 left right因为浮点数永远可以再细分下去。实数二分的标准写法// 求 f(x) x^3 在 [0, 100] 中等于 target 的近似解 double cubicEqual(double target) { double left 0.0, right 100.0; for (int i 0; i 100; i) { // 固定迭代次数 double mid left (right - left) / 2.0; double val mid * mid * mid; if (val target) { left mid; } else { right mid; } } return left; // 或 right两者已经非常接近 }为什么不用while (right - left eps)因为 eps 的设置和使用场景强相关。收敛速度不稳定区间越小同样步数下的精度提升越慢eps 选大了提前退出选小了循环次数不可控。固定 60 ~ 100 次迭代在双精度 double 下几乎能把区间压到极限精度这个技巧在 ACM 比赛里很常用我建议直接记下来。3.3 二分答案把“最优化问题”变成“判定问题”二分查找最大的价值不是找数组里的值而是解决“最优化问题”——典型场景让“最大化最小值”“最小化最大值”。这类题目一旦识别出来解法套路很固定对答案做二分然后写一个判断函数检查某个候选答案是“可行”还是“不可行”。我拿一个非常常见的问题举例有 n 根绳子长度分别是 Li现在要切出 k 段长度相等的绳子每段最长能有多长这个问题你直接算很难但反过来判断“每段长 x 是否可行”就很简单——把每根绳子长度除以 x向下取整后求和如果总段数 k说明 x 可行。于是流程变成答案的范围是 [0, max(Li)]可能的最长段长不会超过最长的那根绳子。在这个区间上二分 x用判断函数验证。因为答案是实数用固定迭代次数控制收敛。伪代码如下bool canCut(const vectordouble ropes, double len, int k) { int cnt 0; for (double r : ropes) { cnt (int)(r / len); if (cnt k) return true; } return false; } double solve(const vectordouble ropes, int k) { double left 0.0, right *max_element(ropes.begin(), ropes.end()); for (int i 0; i 100; i) { double mid left (right - left) / 2.0; if (canCut(ropes, mid, k)) { left mid; // 可行尝试更大 } else { right mid; // 不可行减小 } } return left; }这类题目的核心是你能写出“候选答案是否可行”的判定函数二分本身反而是最简单的部分。而且“二分答案”不限于数值题很多算法竞赛里的经典难题比如“最小化最大距离”“最大化平均值的子段”都能转化过来。做多之后你会发现看到“求最大...的最小值”“求最小...中的最大值”这类措辞基本可以条件反射式地往二分答案方向想。4. C STL 现成实现lower_bound、upper_bound、equal_range、binary_search4.1 四个函数的功能和对应用法很多刷题党和工程党可能没有意识到C STL 的 头文件里已经内置了一套完整、经过大量测试的二分查找函数。日常开发里99% 的场景可以直接用它们不需要自己写二分。函数功能返回值binary_search(first, last, val)判断 [first, last) 中是否存在等于 val 的元素boollower_bound(first, last, val)返回第一个大于等于val 的元素的迭代器迭代器upper_bound(first, last, val)返回第一个大于val 的元素的迭代器迭代器equal_range(first, last, val)返回一个 pairfirst 是 lower_bound 结果second 是 upper_bound 结果pair迭代器, 迭代器配合 vector 使用时最典型的姿势#include algorithm #include vector using namespace std; int main() { vectorint v {1, 2, 2, 2, 3, 5, 8}; auto itL lower_bound(v.begin(), v.end(), 2); // 指向第一个 2 auto itR upper_bound(v.begin(), v.end(), 2); // 指向 3 bool exists binary_search(v.begin(), v.end(), 2); // true auto range equal_range(v.begin(), v.end(), 2); // range.first 指向第一个 2range.second 指向 3区间内全是 2 // 统计 2 的个数 int count itR - itL; // vector 迭代器是随机访问可以直接相减 return 0; }这套东西的简洁程度真的没话说。你不用自己维护 left、right不用担心中间 bug直接用就行。注意这些函数的前提是区间已经有序如果你传进去一个无序区间行为是未定义的编译器不会帮你检查。这是最常见的误用场景。4.2 如何用标准库实现“统计某个值出现了几次”前面手动写的 firstEqual、lastEqual在 STL 里一句话就能替代auto p equal_range(nums.begin(), nums.end(), target); int count p.second - p.first;这个做法比upper_bound - lower_bound更直观而且只遍历一次虽然 lower_bound 和 upper_bound 本身各是 O(log n)合起来也是 O(log n)。要注意的是迭代器相减只对随机访问迭代器有效vector、array、dequelist 的迭代器不支持这个操作。如果你用的是 map 或 set 这类关联容器还有更贴心的成员函数版本setint s; s.lower_bound(x); s.upper_bound(x);mapstring, int m; m.lower_bound(key);成员函数版本利用了红黑树内部结构查找效率是 O(log n) 且不需要随机访问迭代器。而通用版本接受的是双向迭代器在 set/map 上会退化到 O(n)。这是个很容易被忽略的性能坑规则很简单对 vector/deque 用 的版本对 set/map 用成员函数版本。4.3 自定义比较器lower_bound 的进阶用法lower_bound 默认按比较处理升序数组。如果你想降序排列或者按自定义规则找边界可以传入比较器。这里最容易出错的是比较器的语义——lower_bound 找的是“第一个不满足 comp(element, val) 为 true 的位置”。举个例子。数组降序 {8, 5, 3, 2, 1}找第一个小于等于 target 的位置可以这样写vectorint v {8, 5, 3, 2, 1}; int target 4; auto it lower_bound(v.begin(), v.end(), target, [](int a, int b) { return a b; }); // 返回指向 3 的迭代器因为 3 是第一个 4 的元素这里的比较器a b不是“降序排序器”那么简单而是告诉 lower_bound我定义了一个“偏序”在这个偏序下前面元素都“大于”后面元素。lower_bound 会在这样的序列里找第一个不满足element target的位置也就是第一个element target的元素。理解这个语义需要多琢磨但一旦想通了你会发现能用 STL 解决很多自定义规则的边界查找问题。5. 典型场景实战从轮转数组到峰值查找5.1 轮转数组的最小值二段性的经典体现“轮转排序数组”rotated sorted array是二分查找在面试里的王牌题目几乎没有大厂不考。题目形态大概是一个原本升序的数组被从某个位置切开并交换前后两段比如 [1,2,3,4,5] - [3,4,5,1,2]让你找最小值。这个数组不是全局有序的但单调性在“断开点”两侧各自保持所以仍然有二段性。有个思路非常直接——用闭区间模板比较 mid 和 right// 无重复元素版本 int findMin(const vectorint nums) { int left 0, right (int)nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; // 最小值在右半段 } else { right mid; // 最小值是 mid 或 mid 左边 } } return nums[left]; }为什么和 nums[right] 比较因为轮转数组的右半段一定是从小到大的如果 nums[mid] nums[right]说明 mid 不在这段递增区里最小值一定在 mid 右边如果 nums[mid] nums[right]nums[mid] 本身及左边可能存在更小值所以把 right 收过来。这个判断非常优雅把二段性的边界一步步逼近到最小值。如果数组里有重复元素比如 [2,2,2,0,2]直接比较 nums[mid] nums[right] 就不够了。因为当 nums[mid] nums[right] 时无法确定最小值的区间方向。应对办法是把右边界往左挪一位int findMinWithDup(const vectorint nums) { int left 0, right (int)nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; } else if (nums[mid] nums[right]) { right mid; } else { right--; // 无法判断退一步缩小范围 } } return nums[left]; }这个退让看起来很“笨”但最坏情况下确实需要 O(n) 时间比如数组里全是相同元素时右边界只能一格一格挪。面试时能讲清楚“重复元素导致无法二分最坏退化到线性”这个结论是加分项。5.2 轮转数组中查找目标值两段单调性怎么合并处理进阶版问题在轮转数组里找一个具体 target存在返回下标不存在返回 -1。最经典的做法还是闭区间模板但多了“判断 mid 落在哪一段有序区间”的步骤int searchRotated(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; // 左半段有序 if (nums[left] nums[mid]) { // 如果 target 在左半段区间内 if (target nums[left] target nums[mid]) { right mid - 1; } else { left mid 1; } } // 右半段有序 else { if (target nums[mid] target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }核心判断就一个先确认 mid 左边有序还是右边有序通过 nums[left] nums[mid] 判断然后看 target 是否落在那段有序区间的范围内决定收缩方向。每次循环依然排除一半数据整体复杂度 O(log n)。5.3 对应题目的工程启发id 范围统计与日志时间戳定位聊完算法题说点实际的。二分查找在工程里的典型应用场景我遇到过两类特别值得讲第一类是 ID 范围统计。系统里有海量用户 ID按升序排序需要快速统计落在某个区间 [minId, maxId] 的用户数量。这时候直接lower_bound(begin, end, minId)和upper_bound(begin, end, maxId)拿到两个迭代器相减就得到数量。即使数据量几千万这个查询也是毫秒级。第二类是日志时间戳定位。日志按时间排序要找出某个时间段内的所有日志。做法一样对时间戳数组做二分找到开始位置和结束位置然后切片读取。日志量再大查找位置也很快真正花时间的只是读取和解析那部分。这类场景的共同特点是数据预排序、查询频繁、区间定位需求。如果在座的读者遇到类似的性能问题先别上复杂数据结构试一下二分 预排序这个组合往往已经能解决 80% 的需求。6. 常见 Bug 与排查技巧写二分最容易踩的坑6.1 死循环的根因mid 会不会等于 left“二分死循环”是所有初学者都会遇到的梦魇。死循环的本质是某次循环中区间没有缩小导致 left 和 right 永远不变。最容易触发死循环的场景是半开区间模板中配合left mid使用。我以前见过很多人写“找最后一个小于等于 target 的位置”代码是// 错误示例 int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; // 问题在这 } else { right mid; } }当 left right - 1 时mid 会等于 left。此时如果 nums[mid] targetleft 被赋值为 mid——也就是它自己区间没有变化循环永远跑不完。修复方案有两个一是把循环条件改成left 1 right让 mid 永远不等于 left二是把 left 的更新改成mid 1但这可能跳过答案需要重新推导。我个人更推荐第一个方案当你要找“最后一个满足条件的位置”时用left 1 right的循环条件配合left mid / right mid的更新方式既不会死循环语义也清晰。// 安全版本找最后一个 target 的下标 int lastLE(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; } else { right mid; } } if (nums[right] target) return right; if (nums[left] target) return left; return -1; }这个模板的核心思想是让区间里至少留两个候选位置left 和 right循环退出后再分别判断。用空间换确定性非常实用。6.2 越界的常见姿势right 的初始化和 mid 的取整方向越界问题主要集中在两个地方第一right 初始化错误。闭区间模板里 right 应该是nums.size() - 1如果写成nums.size()配合循环条件left right第一次循环 nums[mid] 可能访问到越界下标。半开区间模板里 right 应该是nums.size()如果写成nums.size() - 1会漏掉最后一个元素。第二mid 取整方向。整数除法是向下取整的。mid left (right - left) / 2在 left right 时永远偏向 left 一侧。如果你写的逻辑里需要“取偏右的中间位置”比如找左边界时特别容易出现应该用mid left (right - left 1) / 2也就是向上取整。这个细节决定了很多边界算法的生死。一个经典案例当 left 每次更新为 mid 时必须用向上取整的 mid否则 left mid 之后 mid 仍然等于 left死循环。所以规则要记牢更新 left mid 时mid 要向上取整。更新 right mid 时mid 可以向下取整。6.3 调试二分问题的三个实用技巧二分代码一旦出错肉眼很难看出来问题在哪因为循环体内就那么几行。我分享三个实验下来效率最高的调试方法第一小规模暴力对拍。写一个普通的线性查找函数作为“标准答案”然后随机生成小规模的升序数组对每个 target 同时跑线性查找和二分查找比较结果。这个方法能在几分钟内验证二分逻辑的正确性比人肉推演快太多。验证边界查找firstEqual、lastEqual时就用线性遍历找第一个和最后一个等于 target 的位置来对拍。第二打印循环变量。在循环里加几行临时输出打印 left、mid、right 和 nums[mid]。跑几个 case观察区间是否按预期收缩。这个方法对付死循环特别有效——你能直接看到哪一轮 left 没有再前进。第三把抽象变成具体。二分出问题时不要停留在抽象的“左区间、右区间”上而是用一个具体的数组比如{1, 2, 3, 4, 5}和具体 target 手动模拟一遍循环每一步都写下来。很多 bug 在“手推一遍”的过程中自己就暴露了。下面是我整理的一个常见问题速查表照着排查能省不少时间症状可能原因修复方向死循环left mid 时 mid 向下取整改用 mid 向上取整或循环条件改为 left 1 right返回了错误下标循环条件或收缩方向不匹配统一用闭区间或半开区间不要混搭查找结果漏掉首尾元素right 初始值错误闭区间设 size()-1半开区间设 size()mid 访问越界right 初始值过大 循环条件不配套检查初始化并确保循环退出前区间非空实数二分结果精度不够eps 设太大或迭代次数不足固定迭代 100 次或减小 eps6.4 “排序 二分”还是“线性遍历”怎么选才对最后聊一个策略问题。很多初学者容易走入“所有查找都用二分”的误区。实际上二分查找虽然有 O(log n) 的优势但前提是你已经有一份有序数据。如果数据经常变化每次增删后都要重新排序排序成本 O(n log n) 远高于线性扫描的 O(n)这时候二分反而不划算。我的选择标准是这样的静态数据、查询量大有序数组 二分最优。动态数据、写入频繁考虑 B 树、红黑树std::map/set、跳表这类自带排序和平衡的数据结构不要硬套二分。数据量极小比如小于 100线性查找比二分更快因为二分有分支预测和数组访问的额外开销。这个权衡在实际工程里很重要。比如做一个小工具几千条配置需要按 key 查找排序 二分完全合理但如果每秒都在插入删除配置还是用 map 稳。算法课上学的是“怎么算”工程里更要懂“什么时候不用算”。二分并不万能但它作为基础算法理解得越深你在设计系统时的选择就越有底气。写在最后的一点体会二分查找这个算法代码量不大但能把边界写对、把变形玩明白的人真没有想象中那么多。我自己带过几个新人发现他们最常见的瓶颈不是不懂“分治思想”而是太依赖背模板从不理解模板里每个判断的“为什么”。你只要把闭区间和半开区间两套模型的推导逻辑吃透再遇到旋转数组、找边界、二分答案这些题目本质上都是同一套思考方式的不同组合。另外有个小建议平时刷题时可以刻意用一次 STL 自带函数解题再手写一次原生二分互相验证结果。这个习惯能同时锻炼两件事——理解标准库的设计哲学以及保持对底层实现的手感。毕竟工程里更常用标准库但面试考场上手写二分的功底才是真正决定你能不能拿下面试官那一关的东西。 C++二分查找全攻略：从模板到边界处理与常见Bug排查
二分查找大概是很多人学算法的“入门第二课”——第一课通常是排序。但老实说能把二分查找写到一次提交就通过的人从来都不算多。那个经典的“循环里到底用 left right 还是 left right”“mid 要不要加 1”“会不会死循环”的纠结几乎每个用 C 写过二分的人都经历过那么几回。这篇文章用我自己踩过的坑把二分查找这件事用 C 完整讲一遍从最基础的模板开始到边界查找、实数域二分、二分答案、STL 里的现成轮子lower_bound、upper_bound最后再拆几个面试高频题轮转数组找最小值、找峰值。不管你是刚学算法的学生还是在准备面试、想查漏补缺的开发者照着这篇文章把代码敲一遍、把边界想明白后面遇到二分的题基本不会再慌。1. 二分查找的本质与适用边界1.1 为什么有序和随机访问是硬前提先说一个最容易被忽略的点二分查找的前提不只是“有序”还需要“可随机访问”。序列有序我们才能根据中间元素和目标值的大小关系一次性排除掉一半的数据支持随机访问我们才能用 O(1) 的时间拿到任意下标对应的元素。这两个条件缺一不可。对比一下就清楚了数组天然支持随机访问所以 vector、array 上直接二分没问题。链表虽然可以有序但你要取中间元素必须从头遍历。每次“二分”都要付出 O(n) 的定位成本整体复杂度退化到 O(n log n)还没线性扫描快。所以如果面试里有人问“链表能不能做二分查找”标准答案不是“能”而是“能做但没必要复杂度反而更差”。C 里你要是想在 list 上二分STL 也不会给你基于随机访问迭代器的 lower_bound而是走线性扫描的通用版本。1.2 复杂度优势到底体现在哪二分查找的时间复杂度是 O(log n)。这个“log”有多强我用具体数字说话数据规模 100 万线性查找最坏要比较 100 万次二分最多比较 20 次。数据规模 10 亿线性查找几十亿次基本不可接受二分最多比较 30 次。增长非常慢。你每多比较一次能排除的数据范围就翻一倍。换句话说二分查找把“规模”问题变成了“深度”问题这是几乎所有高效算法共通的底层逻辑——分治。当然前提是你先得排序。排序的复杂度是 O(n log n)所以“排序 二分”这套组合拳适合“一次排序、多次查找”的场景。如果只查一次直接线性扫反而是最优的。这个场景判断我后面在实战章节再展开。1.3 二分不只是“查数字”本质是“砍半搜索”很多人对二分的理解停在“在一个有序数组里找一个数”其实二分的通用模型是在一个“具有二段性”的序列上通过中间值判断应该往左还是往右走。什么叫二段性就是存在一个分界点分界点的一侧全部满足某个性质另一侧全部不满足。比如有序数组中“元素 target”这个条件在某个下标之后全为 true之前全为 false。一个先降后升的数组“最小值”左边右边的单调性不同。一个单调函数 f(x)“f(x) target”这个条件从某个 x 开始恒成立。只要能定义出这种“一侧全真、一侧全假”的性质就能用二分去找那个分界点。很多人学二分觉得模板背不住其实是没有理解这个统一模型。后面讲边界查找和二分答案时全部围绕这个模型展开。2. C 标准实现与边界处理闭区间和半开区间两种模板2.1 先给一套“背下来不会错”的闭区间模板先说结论我平时写二分默认就是闭区间 [left, right] 这套模板。它最直观也是大部分教材的写法。下面是标准实现// 在升序数组 nums 中查找 target返回下标找不到返回 -1 int binarySearch(const vectorint nums, int target) { int left 0; int right (int)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; } } return -1; }核心规则有三条循环条件是 left right因为闭区间下 left 和 right 都可能指向还未检查的合法位置。mid 用left (right - left) / 2而不是(left right) / 2避免整数溢出。虽然现代 64 位环境下 left right 一般不会溢出但这是好习惯面试官看了也舒服。left 更新为 mid 1right 更新为 mid - 1。因为 mid 已经比较过了下一步必须在它的两侧找。这套代码看似简单真正容易错的地方是“区间收缩后会不会跳过答案”。可以想一下当 nums[mid] target 时答案只可能在 mid 右边所以 left mid 1 是安全的当 nums[mid] target 时答案只可能在 mid 左边right mid - 1 同样安全。while 循环每次都会让区间长度至少减 1所以不会死循环。2.2 半开区间模板理解 STL 的思维起点闭区间模板好写但你要是去看 C STL 的 lower_bound 实现会发现它用的是“左闭右开”区间也就是 [first, last)。这套风格的典型实现长这样// 返回第一个 target 的元素下标类似 lower_bound int lowerBound(const vectorint nums, int target) { int left 0; int right (int)nums.size(); // 注意right 是开区间端点指向最后一个元素的下一个位置 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这套模板为什么 long 是左闭右开因为 STL 的迭代器设计本身就是“左闭右开”begin() 指向第一个元素end() 指向最后一个元素的下一个位置end() 是“哨兵”不指向真实元素。所以[first, last)可以完整表达一个空区间这是 C 标准库风格的底层习惯。半开区间模板的关键区别初始 right nums.size()不是 size() - 1。循环条件是 left right不是 left right。因为当 left right 时区间为空没必要再循环。right 收缩时指向 mid不做加减。因为右端是开区间right 指向的位置可以留给下一轮继续判断。循环结束时 left rightleft 就是第一个不满足nums[mid] target的位置也就是第一个 target 的位置。这套模板天然处理了“找不到精确值”的场景返回的是应该插入的位置而不是 -1。这也是 STL 把 lower_bound 设计成“返回迭代器”而不是“返回 bool”的原因。这里容易困惑的是“right mid 而不是 right mid - 1”。画个图就清楚了假设数组是 [1, 3, 5, 7]target 4mid 一开始是下标 1值为 3因为 nums[mid] target所以 left 变成 2下一轮 mid 是下标 2值为 5因为 nums[mid] target我们把 right 设置成 2。此时 left right 2直接返回 2这个位置就是 5就是第一个大于等于 4 的元素。正因为 5 这一轮还没“被排除掉”right 才能指向它这就是 right mid 的意义。2.3 两种模板怎么选看你要的是“找位置”还是“验存在”闭区间模板适合“查找精确值是否存在”比如搜索某个用户 ID、邮件地址。半开区间模板适合“找边界”比如第一个大于等于某个阈值的位置。实际工程里lower_bound 这类边界查找用得更频繁因为数据库索引、区间统计、二分答案全都依赖它。我的习惯是面试写算法题时如果题目明确是“查找某个值存在返回下标”用闭区间模板。如果题目是“找边界”“找插入位置”“二分答案”用半开区间模板。两种模板别混用。一旦定下来循环条件和收缩规则就要全部配套否则左指针右移规则、右指针收缩规则各用各的很容易出死循环或漏解。3. 二分查找的变体与边界查找不只是“找一个数”3.1 找左边界、右边界最常考的二分变形很多题目不满足于“找到 target 就返回”而是问你 target 第一次出现的位置、最后一次出现的位置或者统计 target 在数组里出现了几次。这种问题在闭区间模板上扩展一下就能解决。找左边界第一个等于 target 的下标int firstEqual(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; int ans -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { ans mid; // 先记录当前候选位置 right mid - 1; // 继续往左搜 } else { left mid 1; } } if (ans ! -1 nums[ans] ! target) return -1; return ans; }找右边界最后一个等于 target 的下标int lastEqual(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; int ans -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { ans mid; // 先记录当前候选位置 left mid 1; // 继续往右搜 } else { right mid - 1; } } if (ans ! -1 nums[ans] ! target) return -1; return ans; }这两种写法的思路是一样的不着急 return而是把“找到 target”变成一个持续逼近的过程。每次命中 target就记下当前下标然后继续向左或向右压缩区间直到区间清空。最后 ans 里存的就是最左最右的那个目标位置。统计出现次数也简单lastEqual - firstEqual 1前提是存在。不过这里我要提个醒——如果只是统计次数STL 里有更优雅的做法equal_range一趟搞定后面第四部分会专门讲。平时练习用上面的代码理解原理工程上直接用 STL两头都顾到。注意一个细节上面的代码里ans初始化成 -1最后还要二次检查 nums[ans] 是否等于 target。这是因为循环结束时 ans 可能是“大于等于 target 的最左位置”或者“小于等于 target 的最右位置”但 target 可能根本不存在。比如数组 [1, 3, 5]target 2左边界算法得到的 ans 是下标 1值为 3必须检查值才能确定 2 是否真的存在。3.2 实数域二分控制迭代次数代替判断相等前面都是整数数组能判断nums[mid] target。但遇到实数二分比如二分浮点答案时相等判断就废了——浮点数没法精确比较也不能用整数区间的 left right因为浮点数永远可以再细分下去。实数二分的标准写法// 求 f(x) x^3 在 [0, 100] 中等于 target 的近似解 double cubicEqual(double target) { double left 0.0, right 100.0; for (int i 0; i 100; i) { // 固定迭代次数 double mid left (right - left) / 2.0; double val mid * mid * mid; if (val target) { left mid; } else { right mid; } } return left; // 或 right两者已经非常接近 }为什么不用while (right - left eps)因为 eps 的设置和使用场景强相关。收敛速度不稳定区间越小同样步数下的精度提升越慢eps 选大了提前退出选小了循环次数不可控。固定 60 ~ 100 次迭代在双精度 double 下几乎能把区间压到极限精度这个技巧在 ACM 比赛里很常用我建议直接记下来。3.3 二分答案把“最优化问题”变成“判定问题”二分查找最大的价值不是找数组里的值而是解决“最优化问题”——典型场景让“最大化最小值”“最小化最大值”。这类题目一旦识别出来解法套路很固定对答案做二分然后写一个判断函数检查某个候选答案是“可行”还是“不可行”。我拿一个非常常见的问题举例有 n 根绳子长度分别是 Li现在要切出 k 段长度相等的绳子每段最长能有多长这个问题你直接算很难但反过来判断“每段长 x 是否可行”就很简单——把每根绳子长度除以 x向下取整后求和如果总段数 k说明 x 可行。于是流程变成答案的范围是 [0, max(Li)]可能的最长段长不会超过最长的那根绳子。在这个区间上二分 x用判断函数验证。因为答案是实数用固定迭代次数控制收敛。伪代码如下bool canCut(const vectordouble ropes, double len, int k) { int cnt 0; for (double r : ropes) { cnt (int)(r / len); if (cnt k) return true; } return false; } double solve(const vectordouble ropes, int k) { double left 0.0, right *max_element(ropes.begin(), ropes.end()); for (int i 0; i 100; i) { double mid left (right - left) / 2.0; if (canCut(ropes, mid, k)) { left mid; // 可行尝试更大 } else { right mid; // 不可行减小 } } return left; }这类题目的核心是你能写出“候选答案是否可行”的判定函数二分本身反而是最简单的部分。而且“二分答案”不限于数值题很多算法竞赛里的经典难题比如“最小化最大距离”“最大化平均值的子段”都能转化过来。做多之后你会发现看到“求最大...的最小值”“求最小...中的最大值”这类措辞基本可以条件反射式地往二分答案方向想。4. C STL 现成实现lower_bound、upper_bound、equal_range、binary_search4.1 四个函数的功能和对应用法很多刷题党和工程党可能没有意识到C STL 的 头文件里已经内置了一套完整、经过大量测试的二分查找函数。日常开发里99% 的场景可以直接用它们不需要自己写二分。函数功能返回值binary_search(first, last, val)判断 [first, last) 中是否存在等于 val 的元素boollower_bound(first, last, val)返回第一个大于等于val 的元素的迭代器迭代器upper_bound(first, last, val)返回第一个大于val 的元素的迭代器迭代器equal_range(first, last, val)返回一个 pairfirst 是 lower_bound 结果second 是 upper_bound 结果pair迭代器, 迭代器配合 vector 使用时最典型的姿势#include algorithm #include vector using namespace std; int main() { vectorint v {1, 2, 2, 2, 3, 5, 8}; auto itL lower_bound(v.begin(), v.end(), 2); // 指向第一个 2 auto itR upper_bound(v.begin(), v.end(), 2); // 指向 3 bool exists binary_search(v.begin(), v.end(), 2); // true auto range equal_range(v.begin(), v.end(), 2); // range.first 指向第一个 2range.second 指向 3区间内全是 2 // 统计 2 的个数 int count itR - itL; // vector 迭代器是随机访问可以直接相减 return 0; }这套东西的简洁程度真的没话说。你不用自己维护 left、right不用担心中间 bug直接用就行。注意这些函数的前提是区间已经有序如果你传进去一个无序区间行为是未定义的编译器不会帮你检查。这是最常见的误用场景。4.2 如何用标准库实现“统计某个值出现了几次”前面手动写的 firstEqual、lastEqual在 STL 里一句话就能替代auto p equal_range(nums.begin(), nums.end(), target); int count p.second - p.first;这个做法比upper_bound - lower_bound更直观而且只遍历一次虽然 lower_bound 和 upper_bound 本身各是 O(log n)合起来也是 O(log n)。要注意的是迭代器相减只对随机访问迭代器有效vector、array、dequelist 的迭代器不支持这个操作。如果你用的是 map 或 set 这类关联容器还有更贴心的成员函数版本setint s; s.lower_bound(x); s.upper_bound(x);mapstring, int m; m.lower_bound(key);成员函数版本利用了红黑树内部结构查找效率是 O(log n) 且不需要随机访问迭代器。而通用版本接受的是双向迭代器在 set/map 上会退化到 O(n)。这是个很容易被忽略的性能坑规则很简单对 vector/deque 用 的版本对 set/map 用成员函数版本。4.3 自定义比较器lower_bound 的进阶用法lower_bound 默认按比较处理升序数组。如果你想降序排列或者按自定义规则找边界可以传入比较器。这里最容易出错的是比较器的语义——lower_bound 找的是“第一个不满足 comp(element, val) 为 true 的位置”。举个例子。数组降序 {8, 5, 3, 2, 1}找第一个小于等于 target 的位置可以这样写vectorint v {8, 5, 3, 2, 1}; int target 4; auto it lower_bound(v.begin(), v.end(), target, [](int a, int b) { return a b; }); // 返回指向 3 的迭代器因为 3 是第一个 4 的元素这里的比较器a b不是“降序排序器”那么简单而是告诉 lower_bound我定义了一个“偏序”在这个偏序下前面元素都“大于”后面元素。lower_bound 会在这样的序列里找第一个不满足element target的位置也就是第一个element target的元素。理解这个语义需要多琢磨但一旦想通了你会发现能用 STL 解决很多自定义规则的边界查找问题。5. 典型场景实战从轮转数组到峰值查找5.1 轮转数组的最小值二段性的经典体现“轮转排序数组”rotated sorted array是二分查找在面试里的王牌题目几乎没有大厂不考。题目形态大概是一个原本升序的数组被从某个位置切开并交换前后两段比如 [1,2,3,4,5] - [3,4,5,1,2]让你找最小值。这个数组不是全局有序的但单调性在“断开点”两侧各自保持所以仍然有二段性。有个思路非常直接——用闭区间模板比较 mid 和 right// 无重复元素版本 int findMin(const vectorint nums) { int left 0, right (int)nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; // 最小值在右半段 } else { right mid; // 最小值是 mid 或 mid 左边 } } return nums[left]; }为什么和 nums[right] 比较因为轮转数组的右半段一定是从小到大的如果 nums[mid] nums[right]说明 mid 不在这段递增区里最小值一定在 mid 右边如果 nums[mid] nums[right]nums[mid] 本身及左边可能存在更小值所以把 right 收过来。这个判断非常优雅把二段性的边界一步步逼近到最小值。如果数组里有重复元素比如 [2,2,2,0,2]直接比较 nums[mid] nums[right] 就不够了。因为当 nums[mid] nums[right] 时无法确定最小值的区间方向。应对办法是把右边界往左挪一位int findMinWithDup(const vectorint nums) { int left 0, right (int)nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; } else if (nums[mid] nums[right]) { right mid; } else { right--; // 无法判断退一步缩小范围 } } return nums[left]; }这个退让看起来很“笨”但最坏情况下确实需要 O(n) 时间比如数组里全是相同元素时右边界只能一格一格挪。面试时能讲清楚“重复元素导致无法二分最坏退化到线性”这个结论是加分项。5.2 轮转数组中查找目标值两段单调性怎么合并处理进阶版问题在轮转数组里找一个具体 target存在返回下标不存在返回 -1。最经典的做法还是闭区间模板但多了“判断 mid 落在哪一段有序区间”的步骤int searchRotated(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; // 左半段有序 if (nums[left] nums[mid]) { // 如果 target 在左半段区间内 if (target nums[left] target nums[mid]) { right mid - 1; } else { left mid 1; } } // 右半段有序 else { if (target nums[mid] target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }核心判断就一个先确认 mid 左边有序还是右边有序通过 nums[left] nums[mid] 判断然后看 target 是否落在那段有序区间的范围内决定收缩方向。每次循环依然排除一半数据整体复杂度 O(log n)。5.3 对应题目的工程启发id 范围统计与日志时间戳定位聊完算法题说点实际的。二分查找在工程里的典型应用场景我遇到过两类特别值得讲第一类是 ID 范围统计。系统里有海量用户 ID按升序排序需要快速统计落在某个区间 [minId, maxId] 的用户数量。这时候直接lower_bound(begin, end, minId)和upper_bound(begin, end, maxId)拿到两个迭代器相减就得到数量。即使数据量几千万这个查询也是毫秒级。第二类是日志时间戳定位。日志按时间排序要找出某个时间段内的所有日志。做法一样对时间戳数组做二分找到开始位置和结束位置然后切片读取。日志量再大查找位置也很快真正花时间的只是读取和解析那部分。这类场景的共同特点是数据预排序、查询频繁、区间定位需求。如果在座的读者遇到类似的性能问题先别上复杂数据结构试一下二分 预排序这个组合往往已经能解决 80% 的需求。6. 常见 Bug 与排查技巧写二分最容易踩的坑6.1 死循环的根因mid 会不会等于 left“二分死循环”是所有初学者都会遇到的梦魇。死循环的本质是某次循环中区间没有缩小导致 left 和 right 永远不变。最容易触发死循环的场景是半开区间模板中配合left mid使用。我以前见过很多人写“找最后一个小于等于 target 的位置”代码是// 错误示例 int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; // 问题在这 } else { right mid; } }当 left right - 1 时mid 会等于 left。此时如果 nums[mid] targetleft 被赋值为 mid——也就是它自己区间没有变化循环永远跑不完。修复方案有两个一是把循环条件改成left 1 right让 mid 永远不等于 left二是把 left 的更新改成mid 1但这可能跳过答案需要重新推导。我个人更推荐第一个方案当你要找“最后一个满足条件的位置”时用left 1 right的循环条件配合left mid / right mid的更新方式既不会死循环语义也清晰。// 安全版本找最后一个 target 的下标 int lastLE(const vectorint nums, int target) { int left 0, right (int)nums.size() - 1; while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; } else { right mid; } } if (nums[right] target) return right; if (nums[left] target) return left; return -1; }这个模板的核心思想是让区间里至少留两个候选位置left 和 right循环退出后再分别判断。用空间换确定性非常实用。6.2 越界的常见姿势right 的初始化和 mid 的取整方向越界问题主要集中在两个地方第一right 初始化错误。闭区间模板里 right 应该是nums.size() - 1如果写成nums.size()配合循环条件left right第一次循环 nums[mid] 可能访问到越界下标。半开区间模板里 right 应该是nums.size()如果写成nums.size() - 1会漏掉最后一个元素。第二mid 取整方向。整数除法是向下取整的。mid left (right - left) / 2在 left right 时永远偏向 left 一侧。如果你写的逻辑里需要“取偏右的中间位置”比如找左边界时特别容易出现应该用mid left (right - left 1) / 2也就是向上取整。这个细节决定了很多边界算法的生死。一个经典案例当 left 每次更新为 mid 时必须用向上取整的 mid否则 left mid 之后 mid 仍然等于 left死循环。所以规则要记牢更新 left mid 时mid 要向上取整。更新 right mid 时mid 可以向下取整。6.3 调试二分问题的三个实用技巧二分代码一旦出错肉眼很难看出来问题在哪因为循环体内就那么几行。我分享三个实验下来效率最高的调试方法第一小规模暴力对拍。写一个普通的线性查找函数作为“标准答案”然后随机生成小规模的升序数组对每个 target 同时跑线性查找和二分查找比较结果。这个方法能在几分钟内验证二分逻辑的正确性比人肉推演快太多。验证边界查找firstEqual、lastEqual时就用线性遍历找第一个和最后一个等于 target 的位置来对拍。第二打印循环变量。在循环里加几行临时输出打印 left、mid、right 和 nums[mid]。跑几个 case观察区间是否按预期收缩。这个方法对付死循环特别有效——你能直接看到哪一轮 left 没有再前进。第三把抽象变成具体。二分出问题时不要停留在抽象的“左区间、右区间”上而是用一个具体的数组比如{1, 2, 3, 4, 5}和具体 target 手动模拟一遍循环每一步都写下来。很多 bug 在“手推一遍”的过程中自己就暴露了。下面是我整理的一个常见问题速查表照着排查能省不少时间症状可能原因修复方向死循环left mid 时 mid 向下取整改用 mid 向上取整或循环条件改为 left 1 right返回了错误下标循环条件或收缩方向不匹配统一用闭区间或半开区间不要混搭查找结果漏掉首尾元素right 初始值错误闭区间设 size()-1半开区间设 size()mid 访问越界right 初始值过大 循环条件不配套检查初始化并确保循环退出前区间非空实数二分结果精度不够eps 设太大或迭代次数不足固定迭代 100 次或减小 eps6.4 “排序 二分”还是“线性遍历”怎么选才对最后聊一个策略问题。很多初学者容易走入“所有查找都用二分”的误区。实际上二分查找虽然有 O(log n) 的优势但前提是你已经有一份有序数据。如果数据经常变化每次增删后都要重新排序排序成本 O(n log n) 远高于线性扫描的 O(n)这时候二分反而不划算。我的选择标准是这样的静态数据、查询量大有序数组 二分最优。动态数据、写入频繁考虑 B 树、红黑树std::map/set、跳表这类自带排序和平衡的数据结构不要硬套二分。数据量极小比如小于 100线性查找比二分更快因为二分有分支预测和数组访问的额外开销。这个权衡在实际工程里很重要。比如做一个小工具几千条配置需要按 key 查找排序 二分完全合理但如果每秒都在插入删除配置还是用 map 稳。算法课上学的是“怎么算”工程里更要懂“什么时候不用算”。二分并不万能但它作为基础算法理解得越深你在设计系统时的选择就越有底气。写在最后的一点体会二分查找这个算法代码量不大但能把边界写对、把变形玩明白的人真没有想象中那么多。我自己带过几个新人发现他们最常见的瓶颈不是不懂“分治思想”而是太依赖背模板从不理解模板里每个判断的“为什么”。你只要把闭区间和半开区间两套模型的推导逻辑吃透再遇到旋转数组、找边界、二分答案这些题目本质上都是同一套思考方式的不同组合。另外有个小建议平时刷题时可以刻意用一次 STL 自带函数解题再手写一次原生二分互相验证结果。这个习惯能同时锻炼两件事——理解标准库的设计哲学以及保持对底层实现的手感。毕竟工程里更常用标准库但面试考场上手写二分的功底才是真正决定你能不能拿下面试官那一关的东西。