二分查找这东西很多同学学到后期会觉得“不就是个 lower_bound 嘛”但真到竞赛题里二分考的从来不是“会不会写模板”而是“能不能看出来这里能用二分”。我当年刷《算法竞赛进阶指南》0x04 这一节时前几道题还算友好做到“特殊排序”这道题直接卡了一晚上。不是代码写不出来而是根本想不通一个连传递性都不满足的偏序关系凭什么能用二分去排序搞清楚这个问题之后我对二分的理解算是上了一个台阶。这篇文章就把这道题的完整推导过程、正确性证明、代码实现和踩坑记录都摊开来讲适合正在刷进阶指南、准备 ACM/蓝桥杯或者想真正理解二分本质的读者。1. 先搞清楚“特殊排序”到底特殊在哪1.1 题目说的不是普通排序题目背景大致是这样有 N 个元素编号从 1 到 N系统提供了一个比较函数compare(a, b)返回a是否小于b。注意这个“小于”并不是我们熟悉的数值大小而是题目自定义的一种关系。要求你把所有元素排成一个序列使得序列中任意相邻的两个元素都满足compare(a[i], a[i1]) true也就是前一个元素“小于”后一个元素。比较函数的调用次数有上限限制大概是 O(N log N) 级别。如果你第一次看到这个题很容易觉得这有什么特殊的不就是一个排序吗我用sort加自定义比较器不就行了问题就出在“特殊”这两个字上题目明确告诉你这个compare函数表示的关系不满足传递性。这意味着即使compare(a, b)和compare(b, c)都为真你也不能推出compare(a, c)为真。这在普通排序里是不可想象的因为所有经典排序算法快排、归并、堆排的正确性都建立在“全序关系”之上。一旦传递性不成立整个排序算法的逻辑地基就塌了。1.2 为什么说这是二分章节的“压轴题”这道题放在 0x04 二分章节而不是排序章节本身就透露了出题人的意图它根本不是在考排序而是在考二分的本质。普通二分查找要求数组有序但数组有序只是“单调性”的一种表现形式。这道题里你要维护的是一个满足相邻关系的序列然后对每个新元素找插入位置。看似是在做插入排序但查找插入位置的过程本质上是一个二分查找——而且这个二分查找成立的前提不是全局有序而是一个被隐藏起来的单调性。换句话说这道题是让你“用二分的眼光看排序”把二分从“在有序数组里找数”这个具体场景中抽象出来上升到“在一个满足单调性的判定序列里定位分界点”的高度。想明白这一点后面遇到各种奇奇怪怪的二分题交互题、带权二分、二分答案才能举一反三。2. 为什么不能用快排也不能用普通插入排序2.1 经典排序算法全部默认“全序关系”先复习一个概念所谓全序关系要求满足三个性质——自反性、反对称性、传递性。比如整数大小关系a b且b c一定能推出a c这就是传递性。快速排序在 partition 的时候会把比 pivot 小的元素放左边、大的放右边这个“比 pivot 小”的判断隐含假设了如果x pivot且pivot y那么x一定也“小于”y至少不会出现 x 应该放在 y 右边的情况。归并排序的 merge 阶段同理堆排序的向下调整也同理。一旦compare不满足传递性这些假设全部失效。举个例子假设有三个元素 A、B、Ccompare(A, B) truecompare(B, C) true但compare(A, C) false。快排选 B 作为 pivotA 会被分到左边C 会被分到右边看起来没错但最终序列里 A 在 B 前面、B 在 C 前面而 A 和 C 相邻时如果它们最后相邻compare(A, C) false直接不满足题目要求。2.2 反例演示快排和归并在特殊关系下直接翻车我们可以构造一个具体的小规模反例来加深印象。假设有 3 个元素 1、2、3compare函数定义为compare(1, 2) truecompare(2, 3) truecompare(1, 3) false如果调用系统排序无论快排还是归并排序算法大概率会输出[1, 2, 3]因为它会认为 1 2 3但这个序列里 1 和 2 相邻没问题2 和 3 相邻没问题可一旦 1 和 3 在序列中相邻比如某些分区方式下就直接违反了相邻递增的条件。更麻烦的是算法内部比较的顺序是任意的它可能在某次比较中出现compare(1, 3) false但依然按照已有逻辑处理导致不可预测的结果——连 WA 的报错方式都是随机的调试起来非常痛苦。2.3 普通插入排序为什么可行但不够好既然经典排序算法不行那插入排序呢插入排序有一点很特殊它只依赖“当前元素”和“已排序序列中某个位置的元素”进行比较然后把当前元素插到那个位置后面。它并不要求整个序列满足全局传递性只需要保证每次插入后新序列仍然满足相邻递增。如果每次插入都找到正确的位置那么插入排序在这个特殊关系下是能正确工作的。但普通插入排序找插入位置是逐个往前比较的最坏情况下总共要比较 O(N^2) 次。题目明确限制了比较次数所以必须优化查找过程。怎么优化用二分。这就是整道题最关键的一步在已排序序列中二分查找插入位置。3. 核心思路在“不传递”的关系里找到隐藏的单调性3.1 维护一个“合法序列”我们从头开始用一个vectorint res维护当前已经排好的序列。这个序列满足一个性质对任意i都有compare(res[i], res[i1]) true。初始时序列为空逐个把元素插进来。每插入一个元素 x我们要找到一个新的位置 pos使得插入后x 在 pos 位置上即 res[pos-1] 和 x 相邻、x 和 res[pos] 相邻序列仍然满足相邻递增性质。问题转化为对于当前序列如何确定 x 应该插在哪个位置3.2 关键的单调性能插入的位置是连续的这里需要停下来想一想。普通有序数组里二分查找靠的是数组值单调递增。我们现在这个序列只满足相邻递增并不是全局递增那怎么二分核心观察是这样一个性质如果 x 可以插入在位置 i即compare(res[i-1], x) compare(x, res[i])都成立那么 x 一定也可以插入在某个更靠后的位置 jj i吗答案是否定的因为这个关系并不满足传递性。但《算法竞赛进阶指南》里给的解法利用了另一个更微妙的单调性。我们定义一个判定条件check(mid)表示“x 是否可以接在 res[mid] 后面”即compare(res[mid], x)是否为真。关键结论是这个判定条件在序列上是单调的——如果check(mid)为假那么对于所有k midcheck(k)也一定为假如果check(mid)为真那么对于所有k midcheck(k)也一定为真。这看起来不可思议因为 compare 不满足传递性。但这个性质不是从 compare 本身推出来的而是从“序列合法性”这个构造过程中归纳出来的。换句话说我们维护的序列虽然只要求相邻满足条件但它隐含了一个更强的结构对于任意两个元素 res[i] 和 res[j]i j我们都能通过归纳构造保证一种“可插入性”的单调性。具体证明放到后面这里先用直觉理解每次插入都是通过二分找到的合法位置所以整个序列的“接受新元素”能力从前往后呈现一种阶梯变化——前半段不接受 x 接在后面后半段接受。二分就是在找这个转折点。3.3 为什么二分能找到合法插入点我们想在序列 res 中找一个位置 pos使得如果 pos n需要满足compare(res[pos-1], x)且compare(x, res[pos])如果 pos n插到末尾只需要满足compare(res[n-1], x)。利用上面的单调性我们先找最后一个满足compare(res[i], x)的 i也就是 x 能接在哪个元素后面记为 p。如果不存在这样的 p说明 x 比所有元素都“小”应该插到开头。如果 p 存在我们再验证compare(x, res[p1])是否成立——如果成立就把 x 插在 p 和 p1 之间如果不成立呢这里其实有个细节很多题解直接说“二分找到最后一个满足 compare(res[mid], x) 的位置然后插在后面”这是不够严谨的。需要再往前或者再往后调整。实际上标准的解法是对序列中每个位置 i我们判定“x 是否应该插在位置 i 之后”可以用一个更巧妙的方式——通过比较compare(x, res[mid])来决定二分的走向。具体的二分过程是这样的int l 0, r res.size(); // 插入位置范围 [0, n] while (l r) { int mid (l r) / 2; if (compare(res[mid], x)) { l mid 1; } else { r mid; } } // 此时 l 是第一个满足 compare(res[l], x) false 的位置 res.insert(res.begin() l, x);这段代码的逻辑是我们在一个“虚拟判定数组”上做二分判定条件是compare(res[mid], x)。如果为真说明 x 应该排在 res[mid] 后面mid 之后所以左边界右移如果为假说明 x 应该排在 res[mid] 前面mid 之前或等于 mid所以右边界左移。最终得到的 l 就是插入位置。这其实是“lower_bound”的等价写法只不过比较方向是自定义的。3.4 从“找值”到“找位置”的二分离谱抽象这一段是对二分理解的升华。普通二分的模板是“在一个有序数组里找某个值”而这道题的二分是在“一系列布尔判定结果”里找边界。判定的结果是true/ false组成的序列这个序列天然满足单调性前面一段是 true后面一段是 false或者反过来所以可以二分。你看二分完全不关心底层的比较是否有传递性它只关心判定结果是否有单调性。这是这道题最反直觉也最精华的地方。4. 完整代码实现与逐行解析4.1 注意题目给的接口格式《算法竞赛进阶指南》配套的 AcWing 113 特殊排序题需要实现一个vectorint specialSort(int N)函数系统会提供compare函数要求在函数内返回排好的序列。直接可以在本地调试时实现一个模拟的compare来测试。4.2 代码实现C// Forward declaration of compare API. // bool compare(int a, int b); // 返回 a 是否小于 b注意这个关系不满足传递性。 class Solution { public: vectorint specialSort(int N) { vectorint res; for (int x 1; x N; x) { int l 0, r res.size(); while (l r) { int mid (l r) / 2; if (compare(res[mid], x)) { l mid 1; } else { r mid; } } res.insert(res.begin() l, x); } return res; } };4.3 逐行解释这段代码整个实现只有十几行但每一行背后的含义都值得掰开揉碎讲。vectorint res是已排序序列初始为空。外层循环从 1 到 N 逐个插入元素。这里有几个新手的疑问为什么要从小到大遍历编号编号的顺序有关系吗答案是没有。你可以从任意顺序处理元素每个元素都会通过二分找到自己的位置。从小到大遍历只是方便循环而已。内层二分l 0表示插入位置范围的下界r res.size()表示上界注意不是size()-1因为插入位置的范围是 0 到 n共 n1 个可能位置。这里用的是左闭右开区间[l, r)。mid (l r) / 2取中间位置注意当序列长度为奇数时mid 指向中间元素为偶数时mid 指向中间两个元素中靠左的那个。关键就是if (compare(res[mid], x))这一句。如果res[mid]小于 x说明 x 应该插入到中间位置的右边所以l mid 1否则说明 x 应该插入到中间位置的左边所以r mid。循环结束时l r而且 l 指向的位置就是“第一个不满足compare(res[mid], x)的位置”也就是要插入的位置。最后res.insert(res.begin() l, x)把 x 插入到 vector 的 l 位置。注意 vector 的 insert 会把之后的元素全部后移这一步是 O(N) 的。但由于 N 最大只有 1000题目数据范围O(N^2) 的移动操作完全可以接受真正的瓶颈是比较次数而比较次数被二分控制在了 O(N log N)。4.4 为什么compare(x, res[pos])不需要单独判断很多第一次接触这道题的人会问插入之后x 和它后面的元素之间需要满足compare(x, res[pos])为 true 才对吧代码里怎么没验证答案藏在二分结束的位置里。循环结束后l 是第一个不满足compare(res[mid], x)的位置从左往右数。也就是说对于所有 i l都有compare(res[i], x) true对于 i l都有compare(res[i], x) false这由单调性保证。插入到 l 位置后x 前面的元素是 res[l-1]满足compare(res[l-1], x)x 后面的元素是 res[l]如果存在它不满足compare(res[l], x)但这不代表compare(x, res[l])为假——注意 compare 并不是非真即假的对偶关系它可能两者都为真、两者都为假甚至结果与调用顺序有关。这正是特殊关系的诡异之处也是很多题解没有讲清楚的地方。实际证明中我们需要额外证明在 l 位置插入后compare(x, res[l])也成立。这个证明比较复杂但结论是成立的——而这个证明依赖于“合法序列的归纳构造”不是简单看一眼就能信服的。算法竞赛里通常直接背结论在 l 处插入即可。4.5 比较次数估算每插入一个元素 k第 k 次插入时res 的长度为 k-1二分查找需要约ceil(log2(k))次比较。总的比较次数约为 Σ log2(k) ≈ N log2 N。以 N1000 为例大约是 1000 * 10 10000 次比较远小于题目限制的 20000 次如果题目有明确上限的话完全没问题。如果用普通插入排序逐个比较最坏情况要接近 50 万次比较直接超限。这就是用二分优化的意义。5. 正确性证明为什么这个二分是可靠的5.1 用归纳法证明算法正确这个题的证明并不简单但它是理解整道题的关键值得花时间看。归纳假设当处理第 k 个元素之前res 是一个长度为 k-1 的合法序列并且满足以下额外性质对于任意 i (0 ≤ i len)序列 res 中的前缀 res[0..i] 中每个元素都能“接受”后面的新元素插入而不会破坏相邻递增关系。更具体地说是在插入新元素 x 时能提供二分所需的单调性。插入过程二分找到一个位置 l使得对于所有 i l都有compare(res[i], x) true对于所有 i l都有compare(res[i], x) false。我们声称把 x 插到 l 位置后序列仍然合法。需要验证如果 l 0x 变成第一个元素需要满足compare(x, res[0])。由二分结果可知i0 不满足compare(res[0], x)但我们真正需要的是compare(x, res[0])。这两个不一样。关键证明在于利用归纳假设里的单调性可以推出如果compare(res[0], x) false且 x 能带来合法插入那么compare(x, res[0])必然成立。这部分证明用到反证法假如compare(x, res[0]) false那么 x 放在开头会导致第一对我相邻元素不合法。但我们知道 res 本身是某个顺序合法插入得到的这里的矛盾需要具体分析了——篇幅限制不展开全部细节大致思路是利用“插入过程的对称性”和“先前插入时对应位置的性质”推出矛盾。如果 l lenx 变成最后一个元素需要满足compare(res[len-1], x)。由l len可知compare(res[len-1], x) true直接满足。如果 0 l len需要同时满足compare(res[l-1], x)和compare(x, res[l])。前者由二分的性质直接得到因为 l-1 l。后者同样需要用归纳假设和反证法证明。5.2 反证法为什么二分找到的位置一定合法假设把 x 插到 l 位置之后出现了一个不合法的相邻对那只能是compare(x, res[l]) false因为前一对已经验证是合法的。现在考虑这个不合法的相邻对它意味着 x 必须在 res[l] 之后才符合某种顺序这里的推理会比较绕但可以提供一个直观理解我们实际上把整个插入过程看成“从后往前扫找可以接受 x 的最后一个位置”。在合法的构造过程中如果 x 不能被插在 l 位置那它应该能被插在更早或更晚的位置但二分把可选范围压缩到了唯一一个“临界点”。临界点的两侧一侧满足“x 能接在元素后面”另一侧满足“x 不能接在元素后面”而恰恰是这个临界点保证了“既能接在前面元素后面也能被后面元素接受”。这就是隐藏在题目中的对称性也是这个“特殊排序”能够成立的根本原因。5.3 复杂度分析汇总时间上二分查找每轮 O(log N) 次比较vector insert 每轮 O(N) 次移动总时间 O(N^2)N 比较小时可以接受数据范围 1000 量级完全没问题。比较次数是 O(N log N)这是题目的核心约束。空间复杂度 O(N)。如果想进一步优化移动开销可以用链表但 vector 的 cache 友好性和简单性在这个数据规模下更有优势。6. 实战调试与易错点6.1 边界条件错while (l r) 写成了 while (l r)这是最容易犯的错误。插入位置的二分目标是[0, n]这 n1 个位置中的某一个而不是在一个闭区间里找一个确定元素的值。如果用l r闭区间写法配合mid的计算很容易死循环或者最后得到的位置多 1 少 1。建议直接使用左闭右开[l, r)的 lower_bound 模板不要自由发挥。6.2 compare 参数顺序写反题目里compare(a, b)返回 a 是否小于 b。代码里写compare(res[mid], x)是在问“已排序序列里的中间元素是否小于新元素”这是判断 x 应该插入到中间元素后面还是前面。如果写成compare(x, res[mid])二分的走向就反了排序结果会错。调试时可以先在本地用一个正常的小于号模拟 compare如果排序结果不是递增先检查参数顺序。6.3 打乱插入顺序测试我在调试时就犯过这个错只用从小到大插入的方式测结果正确但换成从大到小插入就错了。后来发现是二分代码里边界写死了一个特殊情况。建议在本地把元素的插入顺序随机打乱当然 compare 要相应调整确保算法不依赖于插入顺序。这个测试很重要因为正确的做法应当对任意插入顺序都能得到合法序列。6.4 本地构造特殊 compare 进行对拍因为题目不提供完整可运行的样例本地自测需要自己构造一个 compare。一种最简单的构造是return a b;这样特殊排序退化成普通排序可以验证输出是否为[1, 2, ..., N]。但这样测不出“非传递性”的情况。另一种构造可以故意制造非传递关系比如compare(a, b)返回(a b) % 3 ! 0之类的随机规则只保证不矛盾然后检查输出序列的相邻关系是否真的满足 compare。写一个校验函数输出后逐对检查能抓出很多隐蔽错误。6.5 用stable_sort或sort的诱惑我见过有人试图用sort(res.begin(), res.end(), compare)来投机取巧。这在普通全序关系下是可行的但在非传递关系下标准库的sort行为是未定义的——它可能在任何一次比较后做出不合理的调整甚至触发越界。千万别这么干。7. 从这道题抽象出的二分思维还能用在哪7.1 交互题里的二分查找很多交互题会提供一个黑盒查询函数要求你通过有限的查询次数确定某个隐藏值。只要你能定义出一个“单调”的判定条件不管这个条件背后的关系多复杂都可以用二分来压缩查询次数。比如猜数游戏、CP 里的“猜排列”问题本质都是这道题的一维版本。7.2 二分答案与带权二分二分答案的经典模型是给定一个可行性函数check(mid)它的返回值随着 mid 增大而单调变化true 一段、false 一段然后二分求边界。“带权二分”则是在 DP 优化里对某个代价函数加一个惩罚项 λ用二分去逼近最优分割点。这些场景的共同点都是检查 mid 是否可行的代价远小于枚举所有情况就像本题中的 compare 调用代替了线性扫描。7.3 二分在“不可排序数据”上的应用普通排序算法要求数据满足全序关系但很多场景下数据之间的关系是“弱”的偏序、互不传递、甚至随机。当你遇到这样的数据时先不要慌试着从“插入”的角度思考能否维护一个已经满足局部条件的序列然后对每个新元素用二分定位这种思路在一些构造题里偶尔会出现属于“非模板化二分”的典型代表。8. 关于这道题我想说的最后几句这道题我前前后后重写了好几遍每次重写都有新的理解。第一遍照抄题解AC 了但完全不知道发生了什么第二遍自己推证明发现证明里有一个细节就是 5.1 提到的反证部分之前根本没注意到第三遍为了写这篇总结又去翻了进阶指南对应章节才真正意识到“特殊排序”这个标题起得有多妙——它特殊的地方不是“排序”本身而是“排序所依赖的关系不满足传递性”这在算法竞赛里是很不常见的设定。如果你刷到这里卡住了我的建议是别急着看代码先拿纸笔模拟 4 个元素的情况写出每一步二分后插入的状态再对照推导过程去体会那个单调性是怎么“凭空出现”的。想明白这个二分这个章节对你来说才算真正过关。之后再遇到任何“感觉能用二分但不知道单调性在哪”的题你就有了一个靠谱的思路先找一个判定函数再去证明它的结果是单调变化的最后才套模板。顺序反了就会做得很痛苦。最后分享一个小技巧刷进阶指南的时候每一章后面的习题最好都自己总结成一句话——这道题考的本质到底是什么。比如追求二分章节普通题是“在有序数组里找值”这道题是“在单调判定序列里找边界”。把每道题抽象到一句话你会发现自己对算法的理解会和之前完全不一样。