企业官网建设流程全解析

我打ACM和刷LeetCode这几年，最常被人问的一个问题就是：二分查找到底怎么才能一次写对？很多人把二分模板背得滚瓜烂熟，改个两三行就出bug，不是死循环就是边界不对。后来我彻底想明白了，问题不在二分框架本身，而在check()函数——你根本没想清楚“要找的到底是什么”，代码写出来自然飘。

这篇文章我就把自己一直在用的二分查找板子，以及围绕check()函数的一套设计思路完整拆开讲。不管是应付笔试、打算法比赛，还是平时处理浮点数二分、离散化后的下标二分，都能直接用。内容偏实战，适合刚入门二分但经常被边界折磨的朋友，也适合想看别人板子找灵感的竞赛党。

1. 二分查找的整体思路：与其背板子，不如先构建模型

很多人写二分喜欢条件反射式地写left和right的更新，写完就交，错了再试。这样等于在赌边界。正确的方式是先回答三个问题：二分对象是谁，判定条件是什么，要找的位置属于哪种类型。这三个问题想明白了，代码只是顺手的事。

1.1 为什么所有二分都能统一成“check()函数”问题

二分查找的底层逻辑其实很简单：在某个单调的序列上，通过不断缩小范围来逼出一个满足性质的分界点。单调性这个词听着很学术，但生活里到处都是。你每天点外卖，同一家店，买满30元才免配送费，买得越多优惠力度越大，这就是一个关于金额的单调关系：金额小的时候不划算，大到一定程度就划算了。你下单选多少钱合适，本质上就是一个在金额轴上的二分。

把这种直觉写成代码，就是check()函数干的活。check(mid)返回true/false，代表“当前的mid这个值能不能满足我的目标条件”。至于整个二分怎么走，完全由check()的设计决定。两个不同的check()，哪怕二分框架一模一样，解出来的东西也完全不同。

我见过最常犯的错误，就是先写了框架，再来想check()怎么填。顺序一旦反了，就会在更新边界时凭感觉瞎猜。正确顺序是先把check()定义清楚，再根据check()的语义去确定该动left还是right，这样每一步都有依据，不会玄学调参。

1.2 二分板子的分类：找等于、找左边界、找右边界

标准的二分有三种目标：查找某个值是否存在；查找第一个满足条件的位置；查找最后一个满足条件的位置。很多人只背第一种，然后在LeetCode上碰到“搜索插入位置”“爱吃香蕉的珂珂”就直接懵，因为那根本不是简单的等值查找。

把视角从“找值”换成“找分界点”之后，二分题就变成了两类：

• 找左边界：从左往右第一个让check(mid)为true的位置，也就是“最早的合法点”。
• 找右边界：从右往左第一个让check(mid)为true的位置，也就是“最晚的合法点”。

这句话看起来空，其实特别有用。比如在有序数组里查找目标值，可以拆成两个二分：先找目标值第一次出现的位置，再找目标值最后一次出现的位置，两次分别对应找左边界和找右边界。我在写C++的lower_bound和upper_bound时，脑海里的模型就是这个。实际做题时只要有“第一个大于等于”“最后一个小于等于”这类措辞，对应关系几乎是一一对应的。

1.3 单调性才是二分的命根子

这里必须强调一个前提：能用二分的序列，必须具有单调性，或者至少满足“前半段为false、后半段为true”（反过来也行）。如果check()的结果在mid左右乱跳，二分框架无论如何都会错。

竞赛里有些题表面看不出单调性，需要你手动构造。比如“给定数组，求所有子段和里第k大的值”，子段和没有天然顺序，但如果二分枚举可能的答案x，check(x)表示“子段和大于等于x的段数是否大于等于k”，这个判定是随x增大而单调递减的，于是也能套二分。这就是check()函数的高级用法：它把不规则的原始问题，想办法转换成一个关于答案的单调判定问题。

写check()之前，先花两分钟确认单调性，往往能省下两小时的调试时间。

2. 核心细节解析：check()函数的设计与边界更新逻辑

二分的框架说来说去就那几行，但换一个check语义，边界更新就可能完全相反。这节我拆开讲每种写法的设计逻辑，帮助你把板子吃透，而不是死记。

2.1 找第一个满足条件的元素（最常用模板）

有些题要求“找出满足要求的最早位置”，典型的如：有序数组中第一个大于等于target的下标，也就是C++的lower_bound。这类问题对应下面的板子：

int l = 0, r = n; // 注意r取值，通常取长度n而不是n-1 while (l < r) { int mid = l + (r - l) / 2; if (check(mid)) { r = mid; // mid可能是答案，所以不能跳过mid } else { l = mid + 1; // mid不可能是答案，所以跳过 } } // 循环结束后，l == r，指向目标位置

这个板子的核心就是把区间维护成“左侧全是false、右侧全是true”的形态。check(mid)为true，就把右边界收到mid，因为mid可能是正确答案，右边不要了；check(mid)为false，说明mid及它左边都不可能是答案，左边全部丢弃，l变成mid+1。

为什么这个板子不会死循环？因为mid算式是l + (r - l) / 2，在整数除法下，当区间长度为1时，mid等于l。此时如果走r=mid分支，区间不变，这不就死循环了吗？不会，因为走r=mid分支的条件是check(l)为true，此时l本来就是答案，循环条件l < r已经不成立。换句话说，唯一的停滞情况只发生在已经收敛时，这正好是退出时机，不算死循环。

2.2 找最后一个满足条件的元素（对称写法）

另一种常见需求是找“最后一个小于等于target的位置”或“二分答案时右边界的解”。比如C++的upper_bound返回的是第一个大于target的位置，它前面一个位置就是“最后一个小于等于target”的答案。对应板子要稍微调整mid取整方向：

int l = 0, r = n; while (l < r) { int mid = l + (r - l + 1) / 2; // 注意向上取整 if (check(mid)) { l = mid; // mid可能是答案，所以不能跳过mid } else { r = mid - 1; // mid不可能是答案，所以跳过 } } // 循环结束后，l == r，指向最后一个满足条件的位置

这里关键的坑在mid的取整方向。为什么这里是l + (r - l + 1) / 2而不是普通的整除？看一个具体例子就能明白：假设当前l=3, r=4，如果mid按下取整得到3，check(3)为true，走l = mid分支，l还是3，区间没有任何变化，死循环。为了避免这种情况，当更新方向是“l = mid”时，mid必须向上取整；反之，当更新方向是“r = mid”时，mid向下取整。这是整数二分的铁律。

不少人把两款板子搞混，要么两个都用向下取整，要么两个都用向上取整，结果在边界上反复横跳。记住一句话：“谁往mid靠，谁就要有退路。”如果答案可能落在mid的左边，r要收过来；如果答案可能落在mid的右边，l要挤过去。为了保证区间减小，mid的对半分割方向必须和移动方向配套。

2.3 实数域二分的特殊处理

整数二分在意的边界问题，在实数域二分里会被精度问题取代。比如求一个函数的零点，或者求一个带根号的方程，题目可能要求精度到1e-6。板子就变成了这样：

double l = 0, r = 1e9; for (int i = 0; i < 100; i++) { // 固定迭代次数，比while更稳妥 double mid = (l + r) / 2; if (check(mid)) { r = mid; } else { l = mid; } } // 最终答案可以是l或r，取决于check的语义

很多刚入门的朋友喜欢写while (r - l > eps)，但eps设小了可能迭代超时，设大了答案精度又不够。我个人更推荐固定迭代100次，因为double的有效数字大约是15到17位，从1e9范围开始二分，每轮区间减半，100轮后区间长度远小于任何实际需要的精度，而且不会因为浮点数比较的舍入误差陷入死循环。

实数域二分中check()的设计和整数版没有本质区别，唯一要留意的是浮点相等判断别用==，要么用区间长度，要么用迭代次数来截止。

2.4 check()函数里最容易踩的几个坑

把check()单独拎出来看，最常见的坑有三个。

第一个是越界。有些题的check需要访问数组元素，比如检查mid作为答案是否可行时，要遍历数组。每轮二分都调用一次check，整体复杂度就是O(logN * checkCost)。如果check内部不加边界判断，在l和r极端取值时很容易数组越界。我习惯在check里尽量用long long，并在涉及下标的地方显式判断边界，宁可多写一行，不赌数据。

第二个是类型溢出。写left + (right - left) / 2而不写(left + right) / 2，根本目的就是防止left和right都很大时相加溢出int。这个习惯在C++里尤其重要，因为int上限只有21亿，两个1e9相加就翻车。改用l + (r - l) / 2之后，不仅数学上等价，数值上还安全。这个写法我一直用到今天，不管日子过得多紧，二分这行字永远不省。

第三个是判断条件的取反逻辑。check(mid)返回true代表的语义，和if分支里的动作要一致。如果你定义“check(mid) == true表示mid可作答案”，但二分代码里写的是check(mid)为true时l=mid+1，那答案就会被跳过。写完代码检查一遍：check为真时，答案在闭区间[left, mid]还是在[mid+1, right]？把这句话在注释里写出来，比对着数据发呆要高效得多。

3. 实操过程：完整实现“二分查找板子(check()函数)”的应用

光讲理论不过瘾，我直接拿一个具体题目来跑一遍完整过程。很多教程给的是抽象模板，但真实比赛和面试里，你面对的是具体题目，如何从题目抽象成check()函数才是真正考验。

3.1 实战题：有序数组中查找目标值的区间

这是“在排序数组中查找元素的第一个和最后一个位置”的经典问题，LeetCode 34题。题目很简单：给定一个非递减数组nums和一个整数target，找出target在数组中的开始位置和结束位置，不存在则返回[-1, -1]。

第一步先想check()。要找开始位置，本质是找第一个下标i满足nums[i] >= target。为什么是>=而不是==？因为如果数组里没有target，第一个>=target的位置恰好是插入点，这就直接把“搜索插入位置”这种变体也一并解决了。

int lowerBound(vector<int>& nums, int target) { int l = 0, r = nums.size(); // 注意：右边界是size()而不是size()-1 while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] >= target) { r = mid; } else { l = mid + 1; } } return l; }

这里让r从nums.size()开始，而不是size()-1，是有讲究的。如果target比数组里所有数都大，第一个满足条件的位置应该是数组结尾的“插入点”，也就是nums.size()这个位置。把r初始化为size()，让搜索区间一开始就包含这个“虚拟位置”，返回l时就不会错。很多板子写成r = n - 1，虽然也能应付某些情况，但一旦要找的位置是数组最后一个元素之后，逻辑就崩了。

有了lowerBound，再找结束位置就是对称操作。结束位置就是最后一个满足nums[i] <= target的下标，也就是第一个满足nums[i] > target的位置再往前移一位。

int upperBound(vector<int>& nums, int target) { int l = 0, r = nums.size(); while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] > target) { r = mid; } else { l = mid + 1; } } return l; // 第一个大于target的位置 }

调用upperBound(...) - 1就能得到结束位置。然后判断一下开始位置是不是真的等于target，不等说明target不存在，返回[-1,-1]。整套逻辑稳得很，而且不用写一堆乱七八糟的特判。

3.2 实战题：二分答案型check()——在D天内送达包裹的能力

LeetCode 1011题是个特别能说明check()函数价值的例子。题目要求你设计一个船的运载能力，使得能在D天内把包裹按顺序运完。运载能力是答案，但数组本身不是单调的能直接二分的东西，需要你写出一个能“判断某个运载能力是否可行”的函数。

这个题和上一题最大的差异在于，check(mid)不再是一个简单的数组下标比较，而是要模拟整个运输过程。运载能力越大，天数越小或不变，因此随着运载能力单调增加，check(mid)的返回结果会从false变为true，具备二分所需的单调性。

check的设计思路是：给定一个能力mid，按顺序装载包裹，逐天累加，如果当前包裹装不下了，就开新的一天。以此统计完成全部运输所需的天数，然后和D比较。

bool check(vector<int>& weights, int cap, int D) { int days = 1; int cur = 0; for (int w : weights) { if (cur + w > cap) { days++; cur = w; } else { cur += w; } } return days <= D; }

注意一个隐患：如果单个包裹的重量都大于cap，那这艘船压根装不下这个包裹，上面的检查也会在模拟时错误地开新的一天。所以二分下界不能从0开始，要从max(weights)开始，上界取sum(weights)。这样保证任何单个包裹都能被装入，问题就只剩下“在合理区间内找最小可行运载能力”。

主函数里的二分就完全复用之前的框架：

int shipWithinDays(vector<int>& weights, int D) { int l = *max_element(weights.begin(), weights.end()); int r = accumulate(weights.begin(), weights.end(), 0); while (l < r) { // 找第一个满足check的位置，即最小运载能力 int mid = l + (r - l) / 2; if (check(weights, mid, D)) { r = mid; } else { l = mid + 1; } } return l; }

这个例子想说明的是：check()函数完全可以是任意一个判定过程，不一定非要是数组比较。它能从“下标判断”扩展到“算法过程模拟”，甚至可以是DP、图论等复杂程序。二分查找的框架只是容器，check()才是真正承载题目逻辑的地方。

3.3 实战题：实数域二分的check()写法

再举一个实数域的例子：“求一个正整数x的平方根，要求误差不超过1e-6”。这种题框架很成熟，直接套实数板子：

double sqrt(double x) { double l = 0, r = max(1.0, x); for (int i = 0; i < 100; i++) { double mid = (l + r) / 2; if (mid * mid > x) { r = mid; } else { l = mid; } } return l; }

这里check(mid)就是mid * mid > x这个判断。如果乘积大于x，说明mid在真实答案的右边，右端点要收回来；否则说明mid不比答案大，左端点可以往右挤。这套逻辑除了在实数域中不用处理mid+1这类整数偏移，其他和整数二分完全一致。

如果你的取值区间里有负数，左右端点的初始化就需要改成区间上下界，保证答案落在区间内。这类实数二分的题，精度基本靠迭代次数保证，120次迭代已经非常充裕，我一般用100次，稳妥且不会拖慢程序。

3.4 板子的体系化：把框架封装成可复用代码

写了这么多题之后，我习惯把二分框架封装成通用函数，比如在C++里用模板函数：

template <typename Predicate> int firstTrue(int l, int r, Predicate check) { while (l < r) { int mid = l + (r - l) / 2; if (check(mid)) r = mid; else l = mid + 1; } return l; } template <typename Predicate> int lastTrue(int l, int r, Predicate check) { while (l < r) { int mid = l + (r - l + 1) / 2; if (check(mid)) l = mid; else r = mid - 1; } return l; }

以后做题时，只需要把具体的判断逻辑写进lambda或函数对象里，传进去即可。在算法比赛里，这套封装能省下重复写二分框架的时间，把注意力集中到check的构造上。不过这属于“个人板子”的优化，新手阶段我更建议先把裸循环写熟练，再用封装，避免脱离底层思维。

4. 常见问题与排查技巧：二分板子是死循环重灾区

二分代码短，但出问题的时候一个比一个隐蔽。我把自己踩过坑和帮别人排查过的问题整理成速查表，方便你对号入座。

4.1 二分死循环与错误边界整不明白

死循环是最常见的现象。如果你在循环内部打印mid，会发现区间长度一直没有下降。这类问题基本可以归为两个原因：mid取整方向不对，或者边界更新时把可能的答案排除了。

我自己排查死循环的方法是：选一个长度为2的区间，手动模拟一遍代码。比如l=0, r=1，假如mid按向下取整得到0，check(0)为true走l=mid，发现l没变，这就说明当前情况下会死循环。然后判断该用哪种取整方向即可。

边界更新不正确导致的错误，通常表现为答案始终差一。比如找第一个满足条件的元素，如果写成了check(mid)为true时l = mid + 1，那最终答案不会是第一个满足条件的位置，而是它后面一个位置。要解决这类问题，核心是记住你维护的那个区间分别代表什么性质：左边是false右边是true，边界更新时确保区间性质不被破坏。

4.2 整数溢出与mid计算方式

在极端数据下用int保存left和right时，(left + right) / 2可能溢出。改成left + (right - left) / 2以后，由于差值不会超过right-left本身，上限通常在可控范围内。另外，如果数据范围更大，可以考虑把mid声明成long long，避免隐式转换带来的bug。

这类问题虽然只在数据规模很大的题目出现，但比赛里卡数据的题最喜欢在这种地方下套。答题时直接用安全写法，就不会在细节上栽跟头。

4.3 check()内部引发的隐性问题——越界、性能、逻辑混淆

越界的排查思路是：在check()开头加一行断言。比如assert(idx >= 0 && idx < n)。如果你用的在线评测系统不支持输出调试信息，断言会在出错时给出崩溃信息，帮你快速定位。

性能问题同样要重视。二分本身的复杂度是O(logN)，但check()如果每轮都做O(N)甚至更高的操作，整体可能变成O(NlogN)或更高。有些题会在check里做排序、遍历全数组、跑最短路等操作，这时要估算整体复杂度能不能过。如果超时，优先优化check的实现，而不是换更快的输入输出。

逻辑混淆指的是你把check()写成了判定“不合法”而不是“合法”，或者把大于号小于号方向写反。这类错误单看代码很难发现，我的建议是先在草稿纸上写清楚一句话：check(mid) == true 表示 mid 依然满足条件，还是已经满足条件。两种情况对应边界移动恰好相反，一旦混淆，结果会完全跑偏。

4.4 调试二分的实战小技巧

调试二分有一种很实用的方法：把每轮的l、r、mid、check(mid)、移动方向全部打印出来，跑小规模样例观察变化是否符合预期。尤其要善用printf或cout配合循环，看区间是不是每次都能缩小。

另一个技巧是准备几个边界测试数据：空数组、数组长度为1、答案在数组首尾、答案不存在、有大量重复元素。每次写完二分，先用这几组数据过一遍，能淘汰掉大部分肉眼发现不了的边界问题。重复元素多的数组特别能考验边界更新逻辑，因为target相同的时候，lower_bound和upper_bound区分起来就容易出错。

如果你用我上面的模板封装，记住在main函数里测试三个不同场景：check全部为false、check全部为true、check一半true一半false。三个场景都通过了，基本说明板子本身没有问题，剩下的就是专注核心逻辑。

5. 扩展思考：check()函数在竞赛进阶场景的玩法

除了基础题型，check()函数还有很多高级用法值得琢磨。理解这些用法后，你对“二分答案”的理解会上一个台阶。

5.1 二分答案与常见判定模型的结合

二分答案的经典套路就是用二分去枚举答案，然后判断答案是否可行。判定过程五花八门：可能是“模拟一遍运输过程”，可能是“跑一遍贪心区间覆盖”，也可能是“检查图是否存在满足条件的路径”。这几种题型里，check()的复杂度直接决定整体性能，也因此产生了“整体二分”“带权二分”等进阶技巧。

我举一个贪心判定模型的例子。题目是“把数组分成连续的k段，使每一段的最大值最小”，很多人叫它分割数组的最大值。二分答案mid表示每一段的和的上限，check(mid)里用贪心：从左往右尽量让每段装更多元素，如果无法在k段内装完就返回false。这个贪心判定的逻辑很简单，但和二分答案结合后就是一道很经典的题。它让你看到check()函数可以是“用某个策略去验证答案”，而不是简单的比较判断。

5.2 把check()函数可视化为单调分界函数

有个很直观的理解方式：把所有可能的答案排列在一个数轴上，每个答案对应一个check结果，true和false形成段式分布。如果从左到右是false段到true段，那就用找左边的板子；如果是从true段到false段，那就用找右边的板子。这个直觉能帮你快速判断应该用哪个模板，以及返回的到底是哪个位置。

我画过很多次这种“颜色分界图”来做题。手上有图，心里有底，写起二分来可以一气呵成，不会每个分支都停顿三秒。

5.3 自己在实战中屡试不爽的check()设计顺序

最后分享一套我写check()时固定的思考顺序，希望能给你一个可以照着做的路径。

先理解题目要的答案是什么：是下标，是数值，还是某个方案的可行性。然后明确单调方向：答案变大时，check结果是往true变还是往false变。接着选择一个最小的“自变量区间”，把答案的范围确定下来，也就是二分区间。最后再写check()函数体，保证能在O(checkCost)内返回判定结果。

这套顺序我自己用了很久，好处在于：每一步都在降低下一步的决策难度。刚开始接触二分时，我总喜欢一上来就开while循环，写完再想check干什么，结果经常拧巴。后来把顺序彻底倒过来，先干check再套框架，准确率直线上升。

最后再说一个我实际踩过很多次的体会：二分代码一旦超过20行，九成是你把问题想复杂了。用上面的思路拆解，二分查找的核心不过是对check()的理解和对边界移动方向的把握。这套板子我用了这么多年，从没在二分题上翻过车。如果你看完这篇还是有点含糊，找两三道二分答案的题，按我给的顺序先写check再套框架，跑通一次你就知道它有多顺了。