企业官网建设流程全解析

二分这个“老熟人”，可能是很多人算法入门的第一个正儿八经的思路，但也是我见过翻车率最高的基础算法。一提到二分，大多数人的第一反应就是“有序数组里找一个数”，然后背个模板就完事了。可等到真正上手做题，尤其是碰到蓝桥杯、PTA或者笔试里的“最小值最大化”“最大值最小化”这类题，却经常不知道该从哪里下手，甚至写出了死循环还一脸懵。

这篇文章会把“二分”当成一整套算法思想来拆，而不是单纯讲查找。我尽量把原理、模板、边界处理、实战套路一次讲透，顺手解决掉那些让你挠头的细节问题。无论是准备刷题的新手，还是想在面试前把这个点彻底吃透的人，都参考一下，帮你少走点弯路。

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

1.1 从“猜数字”到“可行性判断”

很多人了解二分查找，是从一个经典游戏开始的：心里想一个1到100之间的数，问几次能猜中，答案是最多7次。这个游戏的每一步都在做同一件事——猜一个中点，然后根据“大了”还是“小了”砍掉一半的候选范围。整个过程中，你不需要关心最终答案具体是多少，真正有用的信息其实只有两个词：可行，还是不可行。

二分查找这一具体算法，只是这套思想最直白的一个壳。掌握二分思想的标志，是你看到一段有序序列时能想到用中点去试探；而真正的应用场景，要宽得多——你能给某个“答案”定义出“是否可行”的判断规则，并且这个规则存在单调性，那就能二分。

这也是我把这篇博客定位为“算法思想”而不是“算法模板”的原因。二分查找是做选择题，有确定目标值给你比对大小；二分答案是做判断题，不断给一个答案去验证行不行。前者是后者的一个特例，但两者共用同一副骨架。搞懂了骨架，你就能理解为什么有些题乍一看和二分八竿子打不着，最后却能用二分解得漂亮。

1.2 单调性才是二分的灵魂

如果给二分思想找一个关键词，我会选“单调性”，而不是“有序”。我们说数组必须有序才能二分查找，本质上是因为有序数组保证了下标和数值之间呈单调关系：下标越靠后，值越大（或越小）。二分每次通过中间点判断目标在左还是在右，依赖的就是这个规律。

现实中的题目往往不会直接给你一个排序好的数组。你要找的是“某个答案是否可行”，而这个可行性和参数之间的单调关系，很多时候需要你自己挖掘。举个例子，给你一根长10米的木头，问切成k段，每段最长能多长。把每段长度从0往上枚举，段数会单调递减——长度设得越大，能切出来的段数只会变少或不变，绝不会变多。这就是可以用来二分的单调性。

事实上，不只是二分查找和二分答案，很多优化问题的解法和单调性都脱不开关系。比如四边形不等式优化DP里用的“决策单调性”，本质上就是让候选决策点随着DP状态单调右移，再利用二分去定位转移点，把复杂度降一个量级。可见二分这台发动机的燃料就是单调性，有没有那个“有序”的外表并不重要。

1.3 见到什么信号该想到二分

我们做题时最难受的就是看到题目不知道用什么方法。其实二分场景有很多典型信号：题目要求“最大化最小值”“最小化最大值”“求满足某条件的最大/最小可能值”；答案范围是一个连续区间，且你不好直接算出来，但给定一个候选值后，能写出高效的check函数去验证；一些解法中你面临在海量候选值里的暴力枚举，且线性枚举必然超时。

举个经典场景：给一堆石头，要你搬走若干块，使得剩余石头之间的最小间距尽可能大。求这个最小间距的最大可能值。如果你是直接贪心，要考虑“搬哪几块、总共搬多少”组合爆炸，极其痛苦。但如果你换一个角度，先假设间距是d，再去判断“在保留间距至少为d的前提下能不能办到”，一下子就好办多了。判一次d是否可行只要一趟扫描。既然判断单个d的代价很低，那就从d的取值区间里去二分搜索最大的可行d。这是典型的“答案区间可枚举、直接构造答案困难、验证单点可行性容易”的题目，一见这种组合就该条件反射地想到二分答案。

顺带提一个常见误区：很多人一提到“大范围搜索”就只会写暴力枚举或者DFS。二分不是暴力的替代品，而是暴力的进化版。你从暴力枚举每一个可能答案，进化成只枚举整数倍的中点，每一次用check把大量候选区间丢弃，本质上就是把一个O(n)的过程压缩成O(log n)。这个思维转变，比会写任何具体模板都要值钱。

2. 二分查找的三种经典写法

2.1 闭区间写法：最朴素也最易错的模板

最经典的二分查找模板，是用两个指针分别指向数组的左右边界，且左右边界都被包含在搜索范围内。标准写法是初始化left=0，right=n-1，循环条件是left<=right，mid取(l+r)//2，判断中间值和目标的关系后更新left=mid+1或right=mid-1。

def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1

这套模板看起来简单，却暗藏两个最容易错的点。第一，mid的计算最好写成left + (right - left)//2，而不是(left+right)//2。当数组长度接近int上限时，left和right相加可能溢出，虽然很多现代语言会自动升级类型，但C++等语言里溢出是实打实的风险。第二，left=mid+1和right=mid-1这两个更新方向不能乱改。如果左边界更新前已经是mid，而mid又指向已经排除过的位置，那就会重复访问，进而引发死循环。

我早年在面试里见过有人把更新写成left=mid，导致两个指针永远指向相邻位置，结果mid永远等于left，于是left原地踏步，循环永不退出。这在闭区间模板里是特别容易出的毛病，很多人背模板时根本不去想这里为什么是+1或-1。

2.2 左闭右开写法：让STL告诉你为什么这么写

C++的标准库里，lower_bound和upper_bound这两个函数背后用的就是左闭右开区间，也就是搜索范围是[left, right)，循环条件是left＜right，mid落在区间内部某个位置。这种写法的好处，是和STL的区间概念完全一致，不容易出现指针等于边界时语义混淆的问题。

int lower_bound(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; }

注意这套模板在更新右边界时用的是right=mid，不是right=mid-1，因为右端点本身不包含在搜索区间内。如果你把它当作闭区间来理解，会觉得它明明还包含mid位置却舍弃了，小白很容易绕晕。但一旦接受“右端点永不入界”这个设定，它反而会比闭区间更顺手：你只需要盯住“mid是候选答案还是该被排除”，剩下交给固定的半边更新方式即可。

我对这种写法的评价是：一旦熟悉，它比闭区间更不易错，因为判断条件的空集情况天然被排除。很多人在LeetCode上做“寻找旋转排序数组中的最小值”这类题时遇到index越界，根源往往就是使用了闭区间却忘记right=n-1和right=mid-1的组合会让区间过早变空。换成左闭右开，这类边界错位几乎消失。

2.3 找边界值：lower_bound 和 upper_bound

实际做题里，你很少只需要判断“某个值是否出现”，更多时候要找到“第一个大于等于target的位置”和“第一个大于target的位置”，也就是lower_bound和upper_bound。找到这两个位置，等于拿到了目标值在数组里的完整区间。统计重复元素个数、查找插入位置、求解“最接近target”这类问题，全都能在一趟二分里解决。

def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] >= target: right = mid else: left = mid + 1 return left def upper_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] > target: right = mid else: left = mid + 1 return left

这里的关键是理解nums[mid]>=target和nums[mid]>target这两个判断条件分别决定了中点位置归属哪一侧。查找第一个不小于目标值时，等于目标的情况也不能返回，必须继续向左压缩右边界，保证返回的是最左的那个。查找第一个大于目标值时，等于目标的情况要向右压缩左边界，跳过所有相等项。

这种写法和C++标准库语义一致，也算是我个人推荐的主力写法。原因很简单：二分查找最怕的就是“找到了”但找错位置，尤其是要求返回左侧或右侧边界的题目。lower_bound和upper_bound把边界语义固定下来，从源头规避掉模棱两可的情况，任何含重复元素的数据结构都不会把你绕晕。

3. 二分答案：从查找数据到解答问题

3.1 把最优化问题翻译成判定问题

如果说二分查找是在一组数据里找一个确定目标，那二分答案则是在一个巨大的答案区间里猜最合适的那个值。翻译的方法是：把“求某值最大/最小”的优化问题，改写成“给定一个候选值，判断它是否可行”的连续判定任务。这个改写越顺手，你就越算正式跨进了二分思想的大门。

以“分巧克力”这道经典蓝桥杯题为例：有若干块矩形巧克力，要实现切出k块边长相同的正方形，求最大边长。直接想边长和怎么切，你头脑会很快被可能的分割方案淹没。但如果你随便猜个边长c，然后从每块巧克力上算一算能分割出多少个c×c的小正方形，把总数加起来和k比一比，瞬间就有了结论。c越大，分出来的块数只会越少，可行性随c的增大单调递减。于是问题变成在区间[1,最大边长]上二分搜索那个“还能满足总数≥k”的最大c。

再举一个“带权二分”的典型应用。有些涉及DP的问题，在转移时附带单位代价，最优解会随代价权重偏斜。这时可以二分这个权重，把原问题转化为一个“用辅助惩罚项修正”的判定问题，从而找到满足平衡条件的最优解。二分答案在这里不直接查找最终结果，而是搜索一个外部参数来指导DP转移，起到调节天平的作用。

我觉得记住一句话就行：二分答案，不是去找答案本身，是去找“可行域和不可行域之间的那道墙”。从左往右，前面一串都是可行的，某一点之后全是不可行的，你要找的就是最后一个可行点或第一个不可行点。只要你找到了这堵墙，答案自然就在墙头。

3.2 check函数的质量决定二分的上限

在二分答案流程里，二分本身的复杂度只有O(log n)，真正耗时的大头几乎是check函数。很多题的难点也在check函数怎么写。我总结过三点，在写check时特别管用。

第一，check的返回值必须严格符合“可行/不可行”的二元语义，不要用模糊的“差不多”。“可行”要有明确定义——是段数够？是距离够？是重量不超？再复杂的辅助操作，都要落到这个binary的结果。第二，check内部的计算过程要防溢出和防负值，尤其是涉及乘法、总和或者取模的场景，很多新手的check函数看似逻辑对，但一跑就卡在中间某一步的越界或溢出上。第三，如果check过程中能提前确定结果，就直接返回，别把整个数组跑完，比如找跳石头题里，一旦发现需要搬走石头数量已经超过限制，立刻返回false可以省掉大量无用功。

def check(c): count = 0 for w in woods: count += w // c if count >= k: return True return False

这段代码来自“切木头”题。这里的count累加一旦达到k就提前返回，避免无用的遍历。这也是check函数最常见的实用写法——一旦可行就直接短路返回，省时省力。check函数本身往往只负责一件事：计算给定c值下的某个属性值，再和门限比较。

从实战角度说，check函数越简单，二分越不容易出错。如果发现check里写了大量分支和状态变换，你得警觉：要么是问题理解不透，要么是改成二分答案的时机未到。复杂的check本身没有错，但查错难度会成倍上升，笔试时间紧张时你不会有那个耐心去逐行调它。

3.3 整数二分和实数二分的取舍

二分答案在题目里遇到的基本有两种取值范围：整数区间和实数区间。整数二分的更新靠left=mid+1或right=mid-1，循环条件用left＜right或left<=right，mid计算用整除。关键是让每一次循环都让区间长度严格减少，防止死循环。这也是早前讲过的：闭区间模板里mid和两侧更新的方向要匹配。

实数二分的循环条件则有所不同，最常用的两种做法是：固定迭代次数，比如100次，直接写while(iter--)，不用关心精度问题；或者用while(right-left＞eps)判断区间宽度，当宽度小于精度阈值时停止。相比之下，我更推荐固定迭代次数的写法。原因很朴素：不管答案的规模多大、精度要求多高，double的表示范围是有限的，100次迭代已经把区间宽度缩到了2的100次方分之一，这在绝大多数题目里早就超过精度要求。用eps时反而容易因为精度阈值设大设小而反复微调，换题还可能失效。

比如求一个函数的最大值或最小值，范围在0到1e9之间，精度要求1e-6。固定迭代100次后区间长度只剩约1e9除以2的100次方，约等于0。这种稳定性要比你费心想个合适eps省心得多。实操中，凡是精度题目我一律写100次迭代，脑子里再不用为浮点比较头疼。唯一要注意的是浮点输出的格式控制，保留小数位数要依据题意来，别被默认的六位坑了。

4. 边界处理的坑与死循环排查

4.1 为什么你的二分会死循环

二分代码看着简单，死循环起来却也格外丢人。最常见的死循环成因，是mid的计算取整方向和区间更新方式不匹配。我用一个具体场景来演示：当前left=0，right=1，如果要找的是右边界，你写了一个mid=(left+right)//2，算出mid=0，然后逻辑命中“向右走”，把left=mid更新，导致left还是0，永远循环。

另一个高频错误是把“闭区间”写法和“左闭右开”更新方式混搭。左边用闭区间的初始化left=0,right=n-1，右边却套用左闭右开的更新right=mid，结果right永远指不到真正的右边界，循环里mid范围反复横跳，区间很快变成非法状态但循环继续跑，最终越界或者死循环。这两种错误的病根都是：mid取哪个方向（向下取整还是向上取整），必须和“区间缩小时期望保留哪些元素”保持一致。

排查死循环，我有一套固定套路。第一步，把循环的入口条件打印或者手算几个中间状态，观察left和right是否在缩小。第二步，重点是看left=mid还是left=mid+1、right=mid还是right=mid-1的语义有没有被严格遵守。理论上来说，每一次循环后，区间长度都应该严格变小，如果某次更新后两个指针没有任何变化，那死循环就板上钉钉了。第三步，直接换成左闭右开模板重写，等于换一套思维模式来检查逻辑，很多时候比盯着代码找半天快多了。

4.2 典型边界错误速查表

我把这么多年看到过、踩过的高频二分错误汇总成一张表，排错时对照着看，效率很高。

这里最值得展开说一下的是lower_bound场景里的等号处理。很多人一看到等于target，下意识返回mid，这在不存在重复元素时没问题，但重复元素一多就错。正确找第一个等于target的位置的方法是，等号出现时继续压缩右边界；找最后一个等于target的，等号出现时再压缩左边界。等号的归属直接决定返回值是哪一侧，也直接决定是否会漏掉目标。

4.3 中值取整方向的记忆方法

关于mid取整，其实不需要死记硬背，也不应该靠背模板硬套。我用一个很直观的记忆法：如果你希望“未来的搜索区间偏向右边”，也就是要找右边界、尽量把可行中点往右找，那mid就得向上取整。反之，如果你在找左边界、希望搜索过程偏向左侧，mid就取向下取整。

为什么会有这种对应关系？因为mid向下取整时，中点天然偏向left。若这时更新left=mid，left不会前进，死循环风险最大；而如果更新right=mid-1，right会老老实实左移，不会卡死。向上取整时，mid偏向right，反过来，更新right=mid时right不会后退。所以记住一句话：mid偏向哪一侧，哪一侧的更新就不能是mid本身，得稍微收缩一下或保证区间必然缩短。

举个例子，求“最小的可行值”，模板通常写成下面的样式。

left, right = min_value, max_value while left < right: mid = left + (right - left) // 2 if feasible(mid): right = mid else: left = mid + 1 return left

而求“最大的可行值”，因为要找右边界，要把mid改造成向上取整。

left, right = min_value, max_value while left < right: mid = left + (right - left + 1) // 2 if feasible(mid): left = mid else: right = mid - 1 return left

这两套代码非常对称，几乎可以做经典模板来背。核心就是：找左边界的模板用mid往下取整，找右边界的模板用mid往上取整。这样就不会出现 左边界模板+left=mid 导致原地踏步的情况。我发现很多人之前背的都是闭区间模板，一旦换成这种非严格的left<right循环，思维会短暂混乱。但只要用几次之后，你会明显感觉到边界处理比以前利索得多。

5. 经典题目实战拆解

5.1 蓝桥杯“跳石头”：最大化最小值的思路

“跳石头”是我在算法题里见过最能检验二分答案理解程度的一道题。它的描述简单到离谱：河流里有若干块石头，运动员要从起点跳到终点，现在要搬走M块石头，问搬完后最短跳跃距离的最大值是多少。难点不在于代码，而在于你是否能想到“二分答案”这四个字。

按二分答案的思路，我们二分的是“最短跳跃距离”，假设当前猜的值是mid。接下来要判断：如果要求任意相邻落脚点的距离都不小于mid，那最少要搬走多少块石头。判定方法有很多种，我常用的贪心写法是：遍历所有石头，记录上一个保留石头的坐标，如果当前石头和上一个保留石头之间的距离小于mid，就搬走当前这块；否则保留它，并更新上一个保留位置。最后统计被搬走石头的总数是否小于等于M。是则mid可行，说明还能尝试更大的距离；否则就缩小。

def check(d): removed = 0 last_pos = 0 for stone in stones: if stone - last_pos < d: removed += 1 else: last_pos = stone return removed <= m

这道题的核心是理解“最小的最大”为什么可以二分：距离d越大，需要搬走的石头越少，可行性单调递减。只要你能写出这个check，二分主体几乎是同一套骨架。整个题目最大的坑反而在check中的贪心策略——如果贪心策略写错，比如应该在距离过小时搬后一块而不是当前块，check的结果就会偏离真实，二分自然也会解错。建议每次写check前，先在草稿纸上把贪心模拟一遍，再落笔成代码。

5.2 PTA函数题：二分查找的隐蔽边界

PTA上有一类很经典的二分查找函数题，要求在数组中找到元素并返回其下标，但这个数组的索引从1开始编号。很多人拿常见的从0开始的模板往上套，结果边界直接错乱，尤其当目标值在第一个或最后一个位置时。

这类函数题的核心约束是你写的函数只负责返回结果，外部调用已经知道数组长度n和目标值。于是你初始化left=1，right=n，循环条件用left<=right即可。如果用了左闭右开模板，right就要初始化成n+1。这种小差异在本地测试不报错，但一提交到PTA就疯狂报错，原因就是左右边界的物理意义没有和题目一致。

int search(int array[], int n, int target) { int left = 1, right = n; while (left <= right) { int mid = left + (right - left) / 2; if (array[mid] == target) return mid; if (array[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

另外一个容易错的地方是“如果存在多个相同元素，返回任意一个即可”还是“返回最左侧那个”。PTA有些题不要求这一点，但面试时这往往是区分你懂不懂lower_bound分界的重点。建议你在做这类题时主动想想：如果要求返回最左出现的下标，你的代码需要如何改动。把这个细节想通，很多工程里二分查找的边界问题基本就出不了大乱子。

5.3 “最大值最小化”模型的经典例子

在二分答案题型中，“最大值最小化”是与“最小值最大化”对称的另一大金刚。典型题目是：给定一个数组，要求把它分成连续的M段，使得每段的和的最大值尽可能小。这个问题本身是DP也能做的，但二分答案的思路更直观。

我们二分一个候选值mid，判断它是否可行，就看“如果限制每段和不超过mid，最少能分成多少段”。检查方式很经典：从左往右贪心累加，只要当前段加上下一个元素还没超过mid，就继续加；一旦会超过，就新开一段。如果最少分出的段数小于等于M，说明mid这个限制可行，尝试更小的值；否则说明mid太小，所有段都会挤爆，必须加大。

def check(limit): segments = 1 current_sum = 0 for v in nums: if current_sum + v > limit: segments += 1 current_sum = v else: current_sum += v return segments <= m

这个贪心的正确性很好理解：要尽量少分段，每一段就该尽量多装；如果连这种最紧凑的分法都超过M段，那换成任何其他分法只会更多。它和二分答案组合起来，就是一套非常标准的“最大化最小/最小化最大”处理流程。把这个模型吃透，你会发现很多给数组分段、给任务分配资源的问题，都是它换了一张皮。

6. 实战中的经验技巧与算法延伸

6.1 二分和其他算法的组合玩法

二分答案真正的威力，往往在于它能和其他算法拧成一股绳。最常见的是二分+贪心，类似上面跳石头和分段问题。再往深一层走，还有二分+DP、二分+图论检边、二分+网络流之类的组合。这类题的出现背景也非常自然：如果直接求最优解很难，但枚举一个可能答案之后，用现成的经典算法来验证可行性，会轻松很多。

比如DP优化里的“带权二分”，就是在DP转移代价中引入一个惩罚项，通过二分惩罚系数来逼近原始问题的约束条件。这要求你会写DP也会二分，是一种进阶玩法。再比如二分+图论的典型应用，求“使得图中路径上最大边权尽量小的生成树”，先二分边权上限，再用并查集或DFS判断图是否连通。check内层使用图论算法，外层跑二分，复杂度从一次图的构建降到了log级别的多次构建。

我个人的建议是，先把二分+贪心玩熟，再到二分+DP和图论里尝试碰撞。不用一上来就啃最难的题，否则很容易因为check函数写不出来而怀疑自己是否真的理解了二分。一旦你体会到“外层二分、内层算法”的节奏感，之后见到很多带“最大值最小/最小值最大”字样的题，你一眼就能看穿结构。

6.2 六个提升效率的二分编码技巧

在日常写代码时，有几个二分相关的编码细节能明显提升你的效率和正确率。第一，所有用到的区间边界一律使用变量名left/right而不是l/r，语义清晰不说，排查问题时能少想好几秒。第二，mid统一写成left+(right-left)//2，或者(right-left+1)//2和left配合加1的写法，永远不要写成(left+right)//2来贪图省事。第三，所有二分答案的循环条件都用left<right，配合方向匹配的更新，这是最不容易出错的组合。

第四，在while循环体内不要多次计算mid条件，一次算出后存进变量，后面直接用。第五，对于实数二分，我前面说过，直接固定迭代100次或者取精度和范围匹配的固定次数就行，不要写eps然后调来调去。第六，养成给check函数单独写小测试的习惯——最少测一个边界情况，比如mid取到区间最小值时应该返回什么，mid取到最大值时又应该返回什么。

这些小技巧看似琐碎，实际能在紧张的笔试中帮你节省出很多试错时间。我见过不少人在正式比赛里因为mid取整方向写错然后一路查bug，最后什么都来不及。如果你平时就把模板焊死了，根本不会踩这种低级错误。

6.3 二分练习路线与难度分级

练习二分，不需要堆题海，但需要有层次地刷。我觉得一个比较合理的路线是：先刷纯二分查找类，比如LeetCode上的二分查找基础题、搜索插入位置、在排序数组中查找元素的第一个和最后一个位置。这些题帮你夯实模板，尤其是lower_bound和upper_bound的边界语义。

第二个层次是做二分答案类的基础题，比如蓝桥杯的分巧克力、切绳子、跳石头，PTA上的公路村村通这种带检查性质的题。重点训练从“求最值”到“判断可行性”的思维转换。第三层次可以挑战带复杂check函数的组合题，比如最大化最小值加贪心、最大值最小化加DP、检查图连通性等。到这一层，你才算真正把二分思想用活。

刷题时建议准备一个错题本，只记录二分的坑。比如哪个题是因为等号归属写错了，哪个题是因为mid取整方向不对，哪个题是为了精度调了半天eps。回头翻一翻，你会发现自己犯过的错误其实就那么几类，而这些恰是二分思想里最需要加强的地方。学算法很多时候就是这样一个把错误集齐再逐个击破的过程，二分尤其如此。

结尾

说到最后，其实二分给我印象最深的不是它能省多少时间，而是它逼着你换一种提问方式。很多难题直接问“最优解是多少”，你想破头也没思路；但只要你把它改写成“给定一个答案，验证它行不行”，一切都豁然开朗。这种思维上的转换，比记住几个模板值钱得多，我推荐每个刷算法的人都在这个点上多花点时间。

最后再分享一个小技巧：如果笔试时时间紧张，拿不准一个最值问题能不能用二分，你就先写一个check函数，再加上十几行的二分骨架，如果逻辑顺下来感觉不别扭，那基本就是二分题。多练几次，你会慢慢培养出这种直觉，到那时候二分就不再是背模板，而是真正的武器了。