企业官网建设流程全解析

二分查找大概是算法世界里争论最多、看起来最简单、但实现起来最容易翻车的一个基础算法。别的不说，光是一个mid = (left + right) / 2还是mid = left + (right - left) / 2，就能在代码评审里吵上半天。刷 LeetCode 或者打蓝桥杯的时候，二分相关的题目看着都不难，但真正动手写对边界条件的人没几个。这篇内容我就围绕二分思想展开，从最基础的查找模板讲到二分答案、带权二分这类进阶玩法，把我在实际刷题、面试和工程里遇到的二分经验一次性讲透，让新手能避开那些我踩过的坑，也让已经会写的朋友回头检查一下自己的模板到底稳不稳。

1. 先搞懂二分到底在解决什么问题

1.1 二分的核心前提：单调性

很多人学二分是从"猜数字游戏"开始的——你心里想一个 1 到 100 之间的数，我每次猜一个数，你告诉我大了还是小了，最多 7 次就能猜中。这个游戏背后藏着一个关键性质：数字之间是有序的，或者说具有某种单调性。如果每次反馈是"大了"或"小了"，那就能通过缩小一半的搜索范围来逼近答案。

**单调性是二分能够成立的命根子。**没有单调性，二分就是在瞎猜。比如给你一个无序数组，让你找一个目标值，你没法用二分，只能遍历或者先排序再二分。很多人写二分翻车，根本原因是只顾着套模板，没先确认"这个问题具备什么单调性"。单调性不一定非要在数组上体现，它可以是一个函数关系：f(x)随着x增大而单调递增或递减。只要能构造出这种关系，就能用二分。

举个工程例子：你要在日志文件里找一个时间戳对应的位置，日志本身按时间排序，这就是单调性；但要是在一个乱序的集合里找某个值，那就只能老老实实遍历。判断二分的适用性，第一步永远先问自己：这个问题的搜索空间是不是有序的、单调的？

1.2 为什么暴力枚举会输给二分

暴力枚举的思路很简单：从 1 查到 n，遇到满足条件的就返回。时间复杂度是 O(n)。当 n 是 10 万的时候没感觉，但 n 到 10 亿数量级，逐一遍历就完全没法看了。二分通过每次排除一半的搜索空间，把 O(n) 降到了 O(log n)。10 亿的数据量，暴力可能要跑几秒甚至更久，二分只需要 30 次左右的比较。

这里有一个很多人忽略的点：**二分不是"快一点"的问题，而是"能不能跑完"的问题。**比如在一个超大表格里做范围查找，或者在高频接口里反复定位数据，O(n) 和 O(log n) 的差距是数量级的。这也是为什么所有主流数据库的索引多多少少都用到了类似二分的树形查找结构。明白暴力枚举和二分之间的差距，比多背几个模板更能帮你建立算法直觉。

2. 二分查找的工程实现细节

2.1 三种经典模板，到底该背哪一种

二分查找的模板全网到处都是，但核心其实只有三种变体：标准查找、找左边界、找右边界。先把这些模板理清楚，再去谈别的。

标准模板（左闭右闭区间，[left, right]）：

int binarySearch(vector<int>& nums, int target) { 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; } } return -1; }

找左边界（第一个大于等于 target 的位置）：

int lowerBound(vector<int>& nums, int target) { int left = 0, right = nums.size(); // 注意这里是开区间 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; }

找右边界（最后一个小于等于 target 的位置）：

int upperBound(vector<int>& 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 - 1; }

这三种模板的差异看起来很微妙，其实就是区间的开闭和收缩方向不同。我的建议是：**不要贪多，先选定一套左闭右开模板用熟。**左闭右开在处理 C++ 的迭代器、STL 的lower_bound/upper_bound时天然一致，理解成本反而低一些。

2.2 边界条件的核心坑：左闭右闭 vs 左闭右开

写二分最折磨人的不是思想，而是while条件的等号、left和right的更新到底要不要加 1 或减 1。我见过太多人在这个环节"看起来对了但一跑就死循环"。

先说结论：**左闭右闭区间[left, right]下，while (left <= right)，收缩时left = mid + 1、right = mid - 1；左闭右开区间[left, right)下，while (left < right)，收缩时left = mid + 1、right = mid。**这两套规则不能混着用。如果你写着写着用了左闭右闭却忘了right = mid - 1，很容易在剩两个元素时陷入死循环。

关于为什么right = mid而不是mid - 1，你可以这样理解：左闭右开区间里的right本身是"边界外"的位置，当前 mid 已经在区间里了，但右侧边界不该被包含进去，所以right = mid恰好把区间缩到[left, mid)。这是这套写法的自洽逻辑。

2.3 mid 的取法陷阱：不只是防溢出

mid = (left + right) / 2在 left 和 right 比较小的时候没问题，但一旦 left + right 超过 int 范围，就会溢出。标准写法是mid = left + (right - left) / 2。这个细节看起来小，却是很多算法工程师面试时爱挖的坑。C++ 里left + right可能溢出为负数，然后mid变成负数，直接数组越界崩溃。

还有一点，当区间只剩两个元素时，mid取"左中位"还是"右中位"会影响死循环与否。在找左边界模板里，如果left = mid而不用mid + 1，就可能永远停在某个区间出不去。我的习惯是：只要收缩时左边用的是mid + 1，mid 取左中位数就安全；如果哪边用了mid本身，就要检查会不会出现区间不缩小的死循环。后来我甚至靠这个规律反推别人的代码哪里有 bug。

3. 二分的灵魂：从「查找」到「二分答案」

3.1 二分答案：把最优化问题变成判定问题

很多人以为二分只能用于查找某个数，实际上二分最重要的应用是"二分答案"。典型的题目特征是：求某个最优值（最大值最小、最小值最大、最小满足条件的值等），且答案具有单调性。比如"把 n 个物品分成 k 组，每组容量尽量平均，求最大组的最小值"这类问题，直接求最优解很难，但给定一个容量值mid，判断"能不能做到"就简单多了。

做法是：先确定答案的上下界，然后对答案进行二分，每次用贪心或简单的检查函数判定mid是否可行，可行就往更优的方向收缩。这个思路在 OI 竞赛里叫"二分答案 + 贪心判定"，实际工程里也有应用场景，比如任务调度中的负载均衡判断，或者视频编码里某个参数是否满足码率约束。

3.2 带权二分：当单调性变得不那么明显

带权二分（也叫 WQS 二分）听起来高级，本质上还是利用"决策次数"与"权值"之间的单调关系。它解决的问题通常是：在限制选择次数的条件下，要最大化或最小化某个值，而且选择的收益和次数有某种抵消关系。原理是先给每个选择额外加一个罚分（或奖励），调整这个权重，直到最优解的选择次数恰好落在限制条件上。

这个技巧在四边形不等式优化 DP 里也常见——很多 DP 优化的题目，正解就是"二分答案 + 分治决策单调性优化"。说句实在话，带权二分一般面试不太考，但你要是打算法竞赛或做难度较高的题，遇到了就会知道它的价值。我当年第一次见到"带权二分"这四个字时也是一头雾水，但看懂之后发现它并没有离开二分的核心——对参数进行二分，再利用判定结果调整参数。

3.3 二分与排序、分治的关系

二分和排序的关系很自然：**排序是为二分提供有序前提的预处理。**经典组合就是先sort再lower_bound，这也是 STL 里常见的操作。不过要提醒一句，如果数据是无序且只查一次，排序后再二分的复杂度是 O(n log n)，反而不如直接遍历 O(n)；只有在多次查询时，排序预处理才有优势。

和分治的关系则更本质。二分的每一趟递归都在把问题规模减半，本质上是分治思想的一个特例。归并排序的"分"阶段和二分查找的"缩小区间"在思维上是同源的。理解了二分就是分治的一种特殊形态，你在复习归并排序、快速排序时思路也会更通透。

4. 实战场景与刷题复现

4.1 高频题型模板：STL、蓝桥杯、面试题通用解法

在实际刷题场景里，二分最常见的几类题：

• 有序数组中查找某个数：标准binary_search，直接返回下标；
• 查找第一个 / 最后一个满足条件的元素：lower_bound / upper_bound 的变体；
• 旋转有序数组查找最小值或目标值：比如 [4, 5, 6, 7, 0, 1, 2]，核心是判断 mid 落在左半段还是右半段；
• 二分答案：如"分割数组的最大值""运送包裹的最低运载能力"；
• 浮点数二分：求方程的根、求某个单调函数的零点，注意迭代次数或精度控制。

C++ 里可以直接用 STL 的lower_bound和upper_bound，但面试官大概率会让你自己手写一个。手写的好处是你真的理解边界收缩逻辑，而不只是吃饭调用 STL。Java 里对应的是Arrays.binarySearch，底层逻辑相同。

这里分享一个我在蓝桥杯题目里总结的通用检查函数套路：遇到"最大值最小化"的题，先写一个bool check(int mid)，再用二分去枚举可能的答案范围。伪码长这样：

int l = minPossible, r = maxPossible; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } // 最终 l 就是满足条件的最小值

这个套路覆盖了蓝桥杯、PTA 上相当大一部分二分答案题。

4.2 面试高频考点：死循环、溢出、边界检查

面试时二分出现频率极高，因为问题小、坑多、能快速看出候选人基本功。面试官常出的变体：

1. 查找第一个坏版本（LeetCode 278）：本质是 lower_bound；
2. 搜索旋转排序数组（LeetCode 33）：先判断有序段，再决定搜索方向；
3. 寻找峰值（LeetCode 162）：虽然不是严格有序，但用"比较 mid 和 mid+1"来维护某种局部单调性，也是二分思想。

这几类题我都遇到过，也见过很多人栽在"边界条件一改就死循环"上。我记得一个有意思是：**有的面试官不是看你写对没有，而是看你能不能用口头讲清楚 mid 为什么这样收缩。**你如果能说出"我选左闭右开区间，因为 C++ 的迭代器语义就是这样"，面试官往往就会放你一马。

5. 常见问题与排查技巧实录

5.1 死循环的根源：区间没有真正缩小

死循环是二分最容易出的 bug。最常见的情况出现在区间只剩两个元素时，mid取到了左端点，然后收缩逻辑是left = mid，区间就永远缩不小。看下面这段错误示范：

while (left < right) { int mid = (left + right) / 2; if (condition(mid)) { left = mid; // 如果 condition 成立且 mid == left，就死循环了 } else { right = mid - 1; } }

排查死循环的办法很土但很有效：**在循环里打印当前的 left、right、mid，拿长度等于 2 的区间手推一遍。**一旦发现某次迭代后 left 和 right 没有变化，那就是收缩方向错了。修复时要么把left = mid改成left = mid + 1，要么把 mid 取成右中位数(left + right + 1) / 2。这里有个经验规律：left = mid和"上取整 mid"是配套的，left = mid + 1和"下取整 mid"是配套的，别配混。

5.2 边界总写不对？试试这套自查方法

我后来总结了一套自查流程，专门用来检查二分模板对不对：

1. 写出区间定义：左闭右闭还是左闭右开；
2. 写出循环不变式：每次循环开始时，搜索范围是什么；
3. 手动模拟长度为 1 和长度为 2 的区间，确认循环能正确退出；
4. 跑完后检查返回值是不是落在合法范围内。

每次写二分题都走一遍这个流程，看起来繁琐，但练熟之后写起来反而更快。我见过很多比我先写代码、但最后因为边界条件调试半小时的人，而用这套流程我基本一次过。

5.3 什么时候基本告别二分

另一种常见疑问是"我怎么知道这题能不能用二分"。除了一开始说的单调性，还有一个很实用的判断标准：**你能不能写出来一个check(mid)函数，且这个函数能在可接受时间内执行？**如果答案范围巨大，但每次check都要 O(n) 遍历且 n 也巨大，那总体复杂度依然可能超时。这时候实际工程里往往会选择先离线预处理、建立索引，而不是硬上二分。

还有一个很容易踩的坑：数据范围不确定就开始二分。比如有时候right开小了，答案正好卡在上界上，结果找不到最优值。这种问题在二分答案题里尤其阴，所以一定要根据题目给出的边界把right设够大，或者用long long，避免溢出和范围不足叠加在一起。

6. 我踩过的坑和一些实用经验

6.1 二分在真实工程里往往不是单独出现的

刷题久了你会发现，二分很少单独作为考点出现，它通常藏在排序、前缀和、贪心、DP 优化这些组合拳里。比如"查找数组中两个数的和是否小于某个值"，先排序再对每个元素二分，就是排序加二分的经典组合；而带权二分与四边形不等式 DP 的结合则是在更高级的竞赛题里才出现。把二分当成一个基础设施，而不是一个孤立算法，这个认知很重要。

6.2 关于 STL 与手写二分的取舍

写生产代码时，能用 STL 就用 STL。std::lower_bound正确性是经过千万次验证的，自己手写反而容易出错。但刷题和面试时，我强烈建议你手写至少二十道二分题，直到边界条件不用脑子想就能写对。走一遍弯路，才能真正理解为什么STL里的实现长那样，面试官问起来的时候你也能讲出个所以然。

6.3 浮点数二分的一个容易忽略的地方

浮点数二分的题不多，但一旦遇到就容易卡住，比如求方程的根。最大区别是浮点数没有"等于"一说，你没法判断f(mid) == 0，只能判断精度范围内是否收敛。一般有两种做法：循环固定次数（比如 200 次），或者当right - left小于某个阈值时退出。我习惯用固定迭代次数，因为写起来简单，而且不会因为精度设置不当导致死循环。但要注意EPS别设得太小，否则可能跑很久还达不到精度要求。

6.4 最后留个作业式的忠告

二分这种算法的奇妙之处在于，你十年后会忘了大部分排序细节，但一定还记得"每次排除一半"这个直觉。而你能不能顺利写出没有死循环的二分，往往也代表了你对边界条件的敏感度——这种敏感度是编程里非常值钱的一项能力。我后来面试别人时，出二分题不是为了考背诵，就是想看看对方能不能把"为什么这样收缩"讲清楚。能把一种基础算法讲到别人也懂，你的理解才算真正过关。

我自己的体会是：二分的坑几乎全在边界上，而边界问题的本质是你没有把"区间的定义"钉死在一套规则里。选好区间、守住收缩规则、每次检查区间是否缩小，这三个习惯一旦养成，二分基本就是送分题。希望这篇内容能帮你在下一次遇到二分题的时候，写得比我当年第一版代码稳得多。