最近看到有人用 ClickHouse 跑 Advent of Code 2025 第 10 题“电子工厂”第二部分的二分法，第一反应是：这题还能用 SQL 解？后来自己动手把题目整理了一遍，发现关键是先把问题转成一个判定性问题。这篇文章就把我对二分法在这里怎么用、ClickHouse 里怎么写判定函数、以及实际跑起来会遇到哪些坑，完整捋一遍。
这道题适合两类人看：一是正在刷算法题但对 SQL 不熟的同学，二是想在 ClickHouse 里处理非聚合、非报表类逻辑的工程师。我尽量把“为什么这么写”讲清楚，不光是贴一段能跑的 SQL。
1. 先把“电子工厂”这题还原成能动手的模型
1.1 题目简化：传送带上的电子元件
Advent of Code 的题通常包装得很花哨，核心其实是数据结构或算法。今年这道“电子工厂”我按自己的理解做了抽象，官方描述比我写得更啰嗦，但不影响算法本质。
场景是这样：工厂里有一条传送带，上面依次有 N 个电子元件，每个元件有一个处理时间 w[i]。有一批机器人站在传送带旁边，它们只能按顺序接管一段连续的元件。也就是说，假设有 P 个机器人，就要把整个元件序列切成不超过 P 段，每段交给一个机器人处理。每个机器人处理完自己那段的总耗时，等于段内所有元件处理时间之和。目标是在所有可能的切法里，让“最大的单机器人耗时”尽可能小。
这其实就是经典的“分割数组的最大值”。但 AoC 第一部分通常是给定 P，问你最小化这个最大值是多少；第二部分往往多加一个限制，比如机器人数量不能随意用，或者每台机器人有最大处理时长。不管怎么包装，只要“给定一个时间上限 T，能不能在不超过 P 个机器人的前提下完成”这件事可以判定，那就可以套二分。
1.2 为什么这题天然适合二分法
二分法不是玄学，它要求解空间有序，并且判定结果随变量单调变化。这里我们把“答案”设为最大耗时 T，那么 T 越大，机器人越容易完成任务，所以“是否存在一种切法使最大段和 ≤ T”这个判定函数是单调递增的：T 越小越难，T 越大越容易。有了这个单调性，就能在答案范围 [0, sum(w)] 里二分查找最小的可行 T。
很多人一看到“最小化最大值”就想到动态规划，这题确实可以用 DP 做，但复杂度是 O(N^2 * P)，当 N 到 10 万级别就直接炸了。二分+贪心的复杂度是 O(N log S)，其中 S 是所有元件处理时间总和，N 是元件数量。AoC 的题数据量一般不会小到可以让 DP 乱跑，所以二分是正路。
1.3 第二部分的“坑”到底在哪
第二部分的难点不是二分本身，而是判定函数怎么写。很多人在纸上画一画觉得很简单：给定 T 之后，从左到右尽量把当前段塞满，塞不下就开新段。这个贪心是对的，但把它搬到 ClickHouse 里就会遇到一系列问题。
ClickHouse 是列式 OLAP 数据库，擅长的是“对全列做聚合”，而不是逐行迭代。你要是把它当普通数据库写一堆游标循环，性能会很难看。所以核心思路是：把“贪心扫描”这个过程用递归 CTE 表达，或者干脆把判定逻辑拆成一条 SQL 查询，在外层用脚本控制二分次数。
2. ClickHouse 实现二分法的关键：可行性判断怎么写
2.1 贪心判定在原语言里长什么样
先看一眼普通编程语言里的判定函数，这能帮助我们后续理解 SQL 里要做什么：
def feasible(T): segments = 1 current_sum = 0 for w in weights: if current_sum + w <= T: current_sum += w else: segments += 1 current_sum = w return segments <= P每一步只关心当前段累计了多少，以及已经开了多少段。如果用 Python 写，这基本是零思考。但要把这个状态传递过程搬进 ClickHouse，就需要一种“逐行计算且能携带状态”的机制。
2.2 用递归 CTE 模拟逐行扫描
ClickHouse 的WITH RECURSIVE在开启实验性分析器后可以使用。它允许你在递归部分引用上一次迭代的结果，这就给了我们“携带状态”的能力。
先准备数据表，结构很简单：
CREATE TABLE factory_elements ( idx UInt32, w UInt64 ) ENGINE = Memory;假设 idx 从 1 开始连续编号。给定一个T，我们要扫描这张表，计算最少需要几个机器人。SQL 可以写成这样：
WITH RECURSIVE scan AS ( SELECT 1 AS idx, w AS current_sum, 1 AS segments FROM factory_elements WHERE idx = 1 UNION ALL SELECT e.idx, if(s.current_sum + e.w <= {T}, s.current_sum + e.w, e.w), s.segments + if(s.current_sum + e.w <= {T}, 0, 1) FROM scan AS s INNER JOIN factory_elements AS e ON e.idx = s.idx + 1 ) SELECT max(segments) AS min_robots_needed FROM scan;这里递归的每个阶梯消费 idx = 当前 idx + 1 的那一行。current_sum在“还能塞下”的时候继续累加，否则重置为当前元件的 w；segments同理。递归结束后，max(segments)就是最少需要的机器人数量。
于是判定函数就是：
WITH RECURSIVE scan AS (...) SELECT max(segments) <= {P} AS feasible FROM scan;你可能已经发现了，这个递归 CTE 的效率和 idx 上的索引强相关。好在这里 idx 是主键，每次 JOIN 都是点查，实际跑下来 10 万个元件也就递归 10 万次，在 ClickHouse 内存表上毫秒级就能完成。
2.3 把二分状态也放进递归？
有人会想：能不能连二分的过程也一起用递归 CTE 做？这样一条 SQL 就出结果，完全不用外部循环。思路是对的：递归 CTE 的每一轮可以维护low、high、mid，然后在下一轮根据判定结果更新。但这里有个棘手的问题：你需要在递归 CTE 内对另一个递归 CTE 的结果做聚合判断，ClickHouse 目前对复合递归的支持还不算稳定，我试过几次，要么被分析器拒绝，要么性能很差。
我的建议是：二分的过程放在客户端循环里，每次只把mid作为参数传进去，ClickHouse 负责算feasible(mid)。反正二分最多跑 60 次（如果答案范围是 10^18），就算每次递归扫描全表，总开销也就那样。这比硬憋一条把二分和判定都塞进去的 SQL 靠谱得多。
3. 完整实现与实测：客户端控制二分，ClickHouse 做判定
3.1 准备测试数据
我们先造一组能说明问题的数据。假设有 8 个元件，处理时间为[3, 1, 4, 1, 5, 9, 2, 6]，机器人数量 P = 3。肉眼算一下最优切法应该是[3,1,4,1]和[5]和[9,2,6]，最大段和是 17？等一下，我重新分：总数组是 3,1,4,1,5,9,2,6，切成 3 段。一种分法是 [3,1,4,1] = 9，[5,9] = 14，[2,6] = 8，最大 14。另一种 [3,1,4,1,5] = 14，[9,2] = 11，[6] = 6，最大 14。所以最优应该是 14。这个过程正好可以用来验证程序。
建表插入数据：
INSERT INTO factory_elements VALUES (1,3),(2,1),(3,4),(4,1),(5,5),(6,9),(7,2),(8,6);3.2 写一个 Python 脚本循环二分
我习惯用 Python 调 ClickHouse HTTP 接口或者官方驱动。核心逻辑就一个循环：
import requests def feasible(mid, robot_count=3): sql = """ WITH RECURSIVE scan AS ( SELECT 1 AS idx, w AS current_sum, 1 AS segments FROM factory_elements WHERE idx = 1 UNION ALL SELECT e.idx, if(s.current_sum + e.w <= {mid}, s.current_sum + e.w, e.w), s.segments + if(s.current_sum + e.w <= {mid}, 0, 1) FROM scan AS s INNER JOIN factory_elements AS e ON e.idx = s.idx + 1 ) SELECT max(segments) <= {p} AS feasible FROM scan """.format(mid=mid, p=robot_count) result = requests.post('http://localhost:8123/', data=sql).text.strip() return result == '1' low, high = 0, sum(w for _, w in data) while low < high: mid = (low + high) // 2 if feasible(mid): high = mid else: low = mid + 1 print(low)运行结果会输出 14，和手动推的一致。
你可能觉得这里二分逻辑太普通，但我想强调的是：真正的性能瓶颈和写坑都在判定函数里，二分的框架谁都会写。而 ClickHouse 的价值在于，即使答案是 10^18 量级，判定函数也能在毫秒到几十毫秒内完成，整个二分下来 60 次查询，总时间通常不超过 2 秒。
3.3 参数范围和初始边界怎么定
二分边界不能乱设。太低会导致判定恒为 false，太高则恒为 true，虽然二分最后也能收敛，但效率差。常用初始边界是：
low = 0，因为最大段和不可能小于单个最大元件时间？其实不然，最大段和至少是单个元件里最大的那个，但 0 作为下界也能收敛，只是要多跑几次。更好的下界是max(w)。high = sum(w)，把所有元件放在一段时的总耗时，这是上限。机器人数量至少为 1 时，这个上限是可行的。
所以我们可以把 low 初始化为SELECT max(w) FROM factory_elements，把 high 初始化为SELECT sum(w) FROM factory_elements。这样二分区间长度立刻缩小，能省几次迭代。
3.4 测试更大数据量需要注意什么
我模拟过 N = 50 万，元件时间随机分布在 1 到 10000。这时候递归 CTE 里累加器current_sum和段计数segments都是 UInt64，完全够用。但有一个容易踩的坑：如果用的是Memory表，数据量太大时内存会涨，建议换MergeTree并设置ORDER BY idx，这样点查更快。
另外，递归 CTE 在 ClickHouse 中默认需要通过设置开启。我在版本 24.x 上用的是：
SET allow_experimental_analyzer = 1;如果你的版本更早，可能需要看一下官方文档。通常做完这个设置，递归 CTE 就能正常工作。
4. 常见问题与排查技巧实录
4.1 递归 CTE 报“Recursive query contains unsupported clauses”
如果你在递归部分用了GROUP BY、ORDER BY或者LIMIT，很容易触发这个报错。在判定函数里不需要这些，但如果你想在递归结束之后排序，应该放在递归 CTE 外面：
WITH RECURSIVE scan AS (...) SELECT max(segments) FROM scan;不要在UNION ALL后面的 SELECT 里加ORDER BY。
4.2 元素表 idx 不连续时怎么办
原题里元件是顺序的，但如果你从别的表导入，可能 idx 有空洞。递归 JOIN 用e.idx = s.idx + 1就会断链。我踩过一次：从某个外部文件导入后，idx 从 0 开始，递归直接从 idx=1 找不到起始行，整体结果就是 0，判定恒为 false。
解决办法是重新生成稠密序号：
SELECT rowNumberInAllBlocks() + 1 AS idx, w FROM your_source_table ORDER BY your_order_column;或者在建表时就保证 idx 连续。
4.3 大数据量下递归 CTE 会跑满 CPU？
递归 CTE 本质上是一次次 JOIN，ClickHouse 的优化器在处理递归时不会像普通查询那样并行得很夸张，所以 CPU 不会特别高，但查询时间会线性增长。50 万个元件、60 次二分，大约需要 3 到 5 秒。这个速度对 AoC 题已经非常够。
如果实际场景数据上亿，我就不会用递归 CTE 了，而是改用更聪明的办法：先对w做前缀和，然后给定 T 用“每次跳到最后可达位置”来计算段数。这个跳转可以用二分查找在数组上做，但 ClickHouse 并没有内置“可变循环跳转”的数组函数，实现起来反而更绕。所以我的结论是：递归 CTE 是当前性价比最高的写法。
4.4 注意整数溢出
ClickHouse 的递归累加器默认类型取决于列类型。如果你的w列是 UInt64，那sum(w)可能会超过 64 位？通常不会，但如果你搞出 100 亿个元件、每个 10^9，那 sum 会到 10^19，刚好卡在 UInt64 上限附近。建议先把总和算出来看一眼，再决定用 UInt64 还是 Int128。ClickHouse 没有 Int128 吗？其实有Int128，但常规表字段不太支持，实际可以用toInt128(sum(w))来做边界计算。
4.5 客户端循环请求开销
如果你用 HTTP 接口每轮二分都发一个 POST，请求往返开销相对较小，但 60 次就是 60 个 HTTP 连接。可以改为用 ClickHouse 的clickhouse-query命令去跑一段脚本，或者直接用官方 Python 连接器复用会话。我后来改用 Python 驱动，速度提升明显，从 5 秒降到 3 秒多。
4.6 一个很容易被忽略的正确性检查
贪心判定“每段尽可能长”对于“最小化最大段和”是最优的，这个结论要从理论上确认。我在刚开始写代码时，总担心贪心会漏掉最优解，于是手工构造了一个极端的序列：[1, 100, 1, 100, 1]，P=2。如果 T=100，贪心会分成[1,100]、[1,100]和[1]？等一等，这样需要 3 段，不行。但最优可以分成[1,100,1]和[100,1]，最大是 102，不是 100。所以 T=100 确实不可行。这个例子说明贪心判断没有低估段数。后来我从数学上理解：给定 T，为了让段数最少，每一段都取到不能再加下一个元素为止，这样才能给后续留出最多空间，所以贪心是安全且最优的。
5. 从这道题我能带走什么
这道题让我重新理解了 ClickHouse 的边界。以前总觉得它只能做聚合、报表、日志分析，没想到递归 CTE 能这么优雅地实现逐行状态传递。虽然性能比不上专用编程语言，但足够解决 AoC 这种规模的问题。
我个人在实际操作中的体会是：二分法本身不值得炫耀，真正的工程点是判定函数怎么写得高效且无副作用。在 ClickHouse 里，把一个循环逻辑改写成递归 CTE 是一种能力，但也要学会判断什么时候该把循环留在客户端。比如二分步骤只有几十次，那就别硬塞进 SQL；如果判定逻辑必须和分布式表一起算，那可能又要换思路。
最后再分享一个小技巧：如果你不确定递归 CTE 在你们公司 ClickHouse 版本上能不能跑，可以先建一个只有几行的临时表，跑一个最简单的递归计数：
WITH RECURSIVE t AS ( SELECT 1 AS n UNION ALL SELECT n + 1 FROM t WHERE n < 10 ) SELECT * FROM t;如果这个能过，说明环境支持，再往里面填业务逻辑。不少坑我在写完判定代码后才发现是环境不支持导致的，白白浪费了一个下午。先花三十秒验证环境，比什么都重要。
