LeetCode 4 二分查找法求解两个有序数组的中位数

我最早刷到这个题的时候，心里想的还是“合并两个数组，取中间值”这种朴素方案。直到有一次面试被追问“能不能做到 O(log(m+n)) 甚至 O(log(min(m,n)))”，我才意识到 LeetCode 4 寻找两个正序数组的中位数 这道题真正的考点不在中位数本身，而在“如何用二分法处理两个有序数组的划界问题”。LeetCode 4 作为一道高频面试题，几乎每个大厂题库里都有它的位置，但绝大多数解法讲得云里雾里，上来就贴代码，边界条件一团乱麻，自己照着写一遍根本过不了。今天这篇我会把二分查找的核心推导、切分条件的来源、边界处理逻辑全部拆开讲清楚，确保你读完能自己从零写出来，而不是背题。

这道题适合所有正在刷题准备面试的开发者，也适合已经工作但想补一补算法基础的朋友。不管你是刚接触二分查找，还是已经能写出暴力解但想优化到最优复杂度，这篇文章都会给你一个完整、可复现的思考路径。

1. 题目理解：为什么中位数问题值得反复研究

1.1 题目描述的完整拆解

题目本身很好理解：给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2，要求找出并返回这两个正序数组的中位数。注意“正序”两个字，这是整个算法能优化的基石，如果没有这个前提，任何二分思路都无从谈起。

但真正把这道题推上“必刷题”位置的是最后那句：算法的时间复杂度应该为 O(log (m+n))。这个复杂度要求直接排除了合并排序 O(m+n) 的做法。要知道在面试现场，如果第一反应是开一个新的数组做归并，面试官大概率会继续追问一句“能不能再快一点”。所以这道题表面考的是中位数，实际考察的是你能否从“找中位数”这个具体问题里抽象出“第 k 小元素”的通用模型，再结合二分法将复杂度降到对数级别。

1.2 中位数定义的数学本质

在动手写代码之前，先要把中位数的定义吃透，因为后续所有切分条件都是从这里推出来的。

对于一个有序数组，中位数满足一个关键性质：它把数组分成左右两半，使得左边元素的数量与右边元素的数量之差不超过 1，并且左边所有元素都不大于右边所有元素。用数学语言说，设数组长度为 n：

• n 为奇数时，中位数是第 (n+1)/2 个元素。
• n 为偶数时，中位数是第 n/2 个和第 n/2+1 个元素的平均值。

这个定义看似简单，但当你面对的是“两个数组合并后的中位数”时，你就会发现：你不能真的把两个数组合并，因为那样复杂度就变成了 O(m+n)。你要做的，是直接在那个“虚拟的、合并后的数组”上找到正确的切分位置。怎么不合并却能知道切分位置？这就是二分查找要解决的问题。本质上，你是在两个数组里各找一个切分点，使这两个切分点左边元素的数量之和等于“虚拟合并数组”总长度的前半部分。

我个人的体会是，一旦你把中位数理解为“一种满足左右数量平衡和大小顺序的切分结果”，这道题就从一个“找数”的问题变成了一个“找切分点”的问题，思路会一下子打开。

1.3 这道题在面试中的考察权重

从面试角度看，LeetCode 4 是一道“讲了暴力解能拿及格分，讲了 O(log(min(m,n))) 能拿高分”的题目。因为它的解法本身包含了好几个经典算法思想：二分查找、分治、边界条件处理、数学建模。很多候选人能在白板上写出 O(m+n) 的归并解法，但你让他解释为什么切分条件是 L1 <= R2 && L2 <= R1，他就卡住了。

另外，这道题在第二轮的复杂度优化上还有一层隐含逻辑：为什么要在较短的数组上二分？这里面涉及时间复杂度的细节权衡。后面我会专门讲，这里先记住结论——在短数组上二分，复杂度是 O(log(min(m,n)))，这就是最优解。

2. 思路演进：从合并排序到二分查找

2.1 暴力方案：合并排序 O(m+n)

最直观的思路是：新开一个长度为 m+n 的数组，用双指针归并排序的方式把 nums1 和 nums2 合并，然后直接取中间位置。

这一步的代码逻辑很简单：两个指针分别指向两个数组开头，比较大小，小的先放进新数组，直到某个数组耗尽，再把剩下的部分接上。合并完成后，如果总长度是奇数，中位数就是新数组第 (m+n)//2 个元素；如果总长度是偶数，中位数就是第 (m+n)//2 个和第 (m+n)//2 - 1 个元素的平均值。

这个方案没有任何错误，但问题在于空间复杂度和时间复杂度都是 O(m+n)。当两个数组各有一百万个元素时，你需要额外分配两百万个元素的数组，这在数据规模上来以后是不现实的。而且它完全没利用到“两个数组已经有序”这一条额外信息（理论上可以利用指针移动而不用合并）。

如果你在现场只能想到这个方案，先说清楚它的复杂度，再补充一句“我可以继续优化”，通常也能让面试官点头。但如果你连优化方向都没有，分数就不会太高。

2.2 等价转化：寻找第 k 小元素 O(log(m+n))

在合并方案的基础上，有一个经典的优化思路：把“求中位数”转化为“求两个有序数组的第 k 小元素”。

具体做法是：写一个函数 findKth(nums1, nums2, k)，每次比较两个数组第 k/2 个位置上的元素，哪个小就排除哪个数组前 k/2 个元素，然后 k 减去排除的个数，递归或迭代继续。这样每轮 k 减半，时间复杂度是 O(log(m+n))。

这个思路是正确的，代码也不难写，但它有一个坑：它没有把“排除半个数组”的决策最优化。要知道，你可以只排除较短的数组的一部分，而不是总在两个数组上都操作一轮。这是后续 O(log(min(m,n))) 方案的核心出发点。

2.3 最优方案：在较短的数组上二分 O(log(min(m,n)))

真正的最优解，是在两个数组之间找一个全局的切分线，用来模拟“虚拟合并数组”的左半边和右半边。这个切分线由两个切分点组成：nums1 切在位置 i，nums2 切在位置 j。它需要满足两个条件：

1. 左边的元素总数等于右边的元素总数（或左边比右边多一个，具体取决于总长度奇偶性）。
2. 左边的最大值不大于右边的最小值。

由于两个数组都升序，只要满足上面的两个条件，就可以确认：合并数组的左半部分由 nums1[0..i-1] 和 nums2[0..j-1] 组成，右半部分由 nums1[i..m-1] 和 nums2[j..n-1] 组成。然后，如果总长度是奇数，中位数就是左半部分的最后一个元素（即 max(L1, L2)），如果是偶数，就是 (max(L1, L2) + min(R1, R2)) / 2。

这里最关键的是怎么找 i 和 j。由于总左半元素数量是固定的，j 实际上由 i 唯一确定，公式是：j = (m+n+1) / 2 - i。这意味着你只需要在一个变量上做二分。为了减少二分范围，选择在较短的数组上二分，移动 i 就能推算出 j。

• 如果 nums1[i-1] > nums2[j]，说明 i 切大了（左边多了 nums1 的元素），需要把 i 左移。
• 如果 nums2[j-1] > nums1[i]，说明 i 切小了（左边少了 nums1 的元素），需要把 i 右移。

这个二分思路最优雅的地方在于：它不关心每个数组各自的中点在哪里，只关心“总左半部分”是否平衡，并通过交叉比较来判断切分方向，逐步逼近正确切分点。

3. 核心细节：切分条件的推导与边界处理

3.1 为什么切分点只需要一个变量？

你把两个数组想象成一条整体的序列。合并后的总长度是 m+n，中位数要求左半部分元素个数为 totalLeft = (m+n+1) / 2（这个表达式无论奇偶，都能保证左半部分不多于右半部分超过 1 个）。

问题在于，这个“总左半”到底由 nums1 贡献多少、由 nums2 贡献多少？假设 nums1 切在 i（表示 nums1 的左半部分是 nums1[0..i-1]），那么 nums2 的左半部分必须包含 totalLeft - i 个元素。换句话说，j = totalLeft - i。

这个公式是硬性的，因为它要保证元素总数固定。所以在整个二分过程中，你只需要调整 i，j 随之变化，不需要同时调整两个变量。这就是“一个变量控制全局”的直觉来源。为了保证 i 的取值范围足够窄，你可能要在较短的数组上做二分；如果两个数组长度相差悬殊，在长数组上二分会让 j 可能变成负数，边界情况会更难处理。

3.2 四个边界值的定义与含义

在代码中，你需要时刻维护四个值：

• L1 = nums1[i-1]：nums1 左半部分的最大值（如果 i=0，说明 nums1 全部属于右半部分，此时 L1 为负无穷）。
• R1 = nums1[i]：nums1 右半部分的最小值（如果 i=m，说明 nums1 全部属于左半部分，此时 R1 为正无穷）。
• L2 = nums2[j-1]：nums2 左半部分的最大值（如果 j=0，L2 为负无穷）。
• R2 = nums2[j]：nums2 右半部分的最小值（如果 j=n，R2 为正无穷）。

注意负无穷和正无穷在这里不是真的设成 -inf 和 +inf，而是用语言里的哨兵值代替。在写代码时，常用的做法是，如果索引越界，就返回 Integer.MIN_VALUE 或 Integer.MAX_VALUE。这样做的理由是：如果左半部分没有元素，那么左边最大值应该“非常小”，永远不会成为那个 max(L1, L2)；如果右半部分没有元素，那么右边最小值应该“非常大”，永远不会成为那个 min(R1, R2)。

3.3 切分正确的判定条件：交叉比较的直觉

你已经知道正确切分要满足两个条件：

1. 数量平衡：i + j == totalLeft。
2. 顺序正确：nums1 左半部分最大值 <= nums2 右半部分最小值，同时 nums2 左半部分最大值 <= nums1 右半部分最小值。

翻译成四个变量就是：

• L1 <= R2
• L2 <= R1

如果这两个条件同时成立，恭喜你，i 就是我们要的切分位置。

如果条件不成立，分两种情况：

• L1 > R2：说明 nums1 左半部分里有一个元素比 nums2 右半部分的最小值还要大，那这个元素无论如何都应该挪到 nums1 的右半部分去。也就是说 i 切多了，需要减小 i。对应的二分搜索操作是 high = i - 1。
• L2 > R1：说明 nums2 左半部分里有一个元素比 nums1 右半部分的最小值还要大，那么这个元素应该挪到 nums2 的右半部分去，而 nums2 的左半部分要减少，意味着 j 要减小。又因为 j = totalLeft - i，j 减小等价于 i 增大。因此这里应该让 low = i + 1。

这个“谁大谁往右挪”的直觉可以用生活场景类比：想象你把一堆苹果（nums1）和一堆梨（nums2）混合在一起，要放在两个筐里，左边筐必须比右边筐要么相等要么多一个，而且所有苹果和梨中，小的往左、大的往右。如果发现左边筐里有苹果比右边筐里的梨还大，那就说明这个苹果切错了边，应该往右挪；如果反之，就说明梨切错了边，该往左挪。由于 i 和 j 是绑定的，挪一个变量就行。

3.4 奇偶处理与中位数取值公式

当 i、j 满足切分条件后，中位数的取值分为：

• 总长度 m+n 为奇数：中位数 = max(L1, L2)。因为左半部分恰好比右半部分多一个元素，所以多出来的那一个就是左半部分的最后一个元素，也就是整个合并数组的中点。
• 总长度 m+n 为偶数：中位数 = (max(L1, L2) + min(R1, R2)) / 2。因为左半部分和右半部分数量相等，中位数由最中间的两个元素决定，一个是左半部分最大值，一个是右半部分最小值。

这个看似简单，但很多人会在奇数情形的公式上踩坑。注意：你不能在奇数情形直接用(L1 + L2) / 2，你必须取 max(L1, L2)。原因是 L1 和 L2 分别是两个数组左半部分的最大值，合并后左半部分的“最大值”自然要取两者中较大的一个。

3.5 为什么选择在短数组上二分？

这是很多人忽略的细节。如果两个数组长度分别是 m、n，你在 nums1 上二分，二分的复杂度是 O(log m)；但切分点的正确性依赖于 j = totalLeft - i 这个公式，如果 m > n，你选的 i 变化范围很大，j 很容易越界。更实际的问题是：如果你想保证边界处理简单，应该保证 i 对应的数组是较短的那个。因此，代码开头通常加一步：

if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1

这样二分搜索只发生在较短的数组上，复杂度从 O(log(m+n)) 降到 O(log(min(m,n)))。这不只是理论上更优，实际代码里边界处理也简单得多，因为 j = totalLeft - i 永远不会因为 i 过大而变成负数（确保在较长的 nums2 上切出的 j 一定落在 [0, n] 范围内，前提是 i 在 [0, m] 且 totalLeft 足够容纳）。

4. 代码实现：二分查找的落地写法

4.1 Python 完整实现与逐行解读

下面给出我调试过多遍、最终稳定通过的实现，注释尽量详细，保证每一行都能对应到前面的推导：

def findMedianSortedArrays(nums1, nums2): # 保证 nums1 是较短的数组 if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) total_left = (m + n + 1) // 2 # 在 nums1 上二分切分点 i left, right = 0, m while left <= right: # i 表示 nums1 左半部分包含的元素个数（即切分位置） i = (left + right) // 2 # j 由总数约束推导 j = total_left - i # 取出四个边界值，注意越界时的哨兵值 nums1_left_max = float('-inf') if i == 0 else nums1[i - 1] nums1_right_min = float('inf') if i == m else nums1[i] nums2_left_max = float('-inf') if j == 0 else nums2[j - 1] nums2_right_min = float('inf') if j == n else nums2[j] if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min: # 找到正确切分点 if (m + n) % 2 == 1: return max(nums1_left_max, nums2_left_max) else: return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2 elif nums1_left_max > nums2_right_min: # i 切大了，左移 right = i - 1 else: # nums2_left_max > nums1_right_min，i 切小了，右移 left = i + 1 # 正常情况下不会走到这里 return 0.0

4.2 关键点：为什么循环条件是 left <= right

这里我用的是闭区间二分。当 left == right 时，我们还要再判断一次当前 i 是否满足条件，如果不满足再更新 left 或 right，最终 left 会大于 right 退出循环。这个写法和标准的“在有序数组中查找目标值”的二分一致，更容易推导正确性。

如果你选择left < right，那么当某个边界情况发生时，可能漏掉最后的检查。建议新手用left <= right，不容易出死循环，也更容易和二分模板对应。

4.3 边界值哨兵的作用

我见过不少同学在写这个题的时候，一开始不处理 i=0 或 i=m 的情况，直接用 nums1[i-1] 和 nums1[i] 取数，结果程序直接抛越界异常。处理方式有两个：

• 第一种：像上面的代码，在取值时用条件表达式判断越界并返回无穷值。
• 第二种：在数组两端虚拟地加上哨兵节点，比如把 nums1 逻辑上看成 [-inf, ..., +inf]，但这样会影响数组长度计算，代码会更绕。

我建议用第一种。用无穷值的好处在于，无论你如何调整 i，切分条件里的比较都不会因为你取了越界值而出错。比如 i=0 时，nums1 左半部分没有元素，但为了计算左边的最大值，我们设定它是负无穷，那它一定小于右边的任何数，不会干扰判断。

4.4 其他语言的适配注意

如果你用的是 Java 或 C++，注意整数除法和浮点返回。Java 里(m + n) % 2 == 1判断奇偶没问题，但偶数情况求和时要用2.0而不是2，否则整数相除会丢精度。C++ 里同理。

另外，Java 中可以用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 作为哨兵，但要注意不能直接用 int 表示无穷大参与后续的除法运算，要先把它们转成 double 再计算。Python 因为支持大整数和 float('inf')，就没这些烦恼，写起来最顺畅。

5. 如何验证切分是否“正确”：可视化与实例走查

5.1 手动实例：两个数组都较长时

假设 nums1 = [1, 3, 8, 9, 15]，nums2 = [7, 11, 18, 19, 21, 25]，m=5，n=6，总长度 11，total_left = 6。

第一步：因为 m < n，保持不变。初始 left=0，right=5，mid=2，所以 i=2，j=6-2=4。

• nums1_left_max = nums1[1] = 3
• nums1_right_min = nums1[2] = 8
• nums2_left_max = nums2[3] = 19
• nums2_right_min = nums2[4] = 21

检查条件：3 <= 21 成立，19 <= 8 不成立，说明 nums2 左半部分的最大值太大，切小了（i 需要右移）。于是 left=3。

第二步：left=3，right=5，mid=4，i=4，j=6-4=2。

• nums1_left_max = nums1[3] = 9
• nums1_right_min = nums1[4] = 15
• nums2_left_max = nums2[1] = 11
• nums2_right_min = nums2[2] = 18

检查：9 <= 18 成立，11 <= 15 成立，找到正确切分点。总长度奇数，中位数 = max(9, 11) = 11。

手动走查一遍，你就能清晰看到二分是如何一步步“逼近”正确切分的，而不是靠直觉盲目移动。

5.2 手动实例：两个数组有大量重复元素

假设 nums1 = [1, 1, 1, 1]，nums2 = [1, 1, 1, 1]，m=n=4，总长度 8，total_left=4。

初始 i=2，j=2。

• nums1_left_max = 1
• nums1_right_min = 1
• nums2_left_max = 1
• nums2_right_min = 1

条件全部成立。偶数总长，中位数 = (max(1, 1) + min(1, 1)) / 2 = 1。结果正确。这个例子提醒你：切分条件的关键是不等式是否成立，而不是边界值是否“不同”。即使左右值相等，依然满足 L1 <= R2 和 L2 <= R1，所以代码是安全的。

5.3 特别关注：某一个数组为空的情况

如果 nums1 为空（m=0），那么直接返回 nums2 的中位数即可。但在上面的统一算法里，你并不需要单独写这个分支。因为 m=0 时，初始 left=0，right=0，i=0，j=total_left-0 = (0+n+1)//2，正好是 nums2 左半部分的元素个数。然后四个边界值中 nums1 的两个全是无穷哨兵，切分条件必然成立，直接按公式返回。这就是统一解法的好处：边界情况被自然吸收，代码更简洁。

我建议你先跑几个极端用例再提交：nums1=[], nums2=[1]；nums1=[1], nums2=[]；nums1=[], nums2=[1,2]；nums1=[1,2], nums2=[]。这些用例能把哨兵逻辑彻底验证清楚。

6. 复杂度分析：为什么能做到对数级

6.1 时间复杂度的严谨推导

整个算法只在较短的数组上进行二分，每轮迭代 i 的范围减半。较短数组长度为 m（m <= n），所以二分次数是 O(log m)。因为 m + n 整体可能非常大，但 log m 严格不超过 log((m+n)/2)，所以 O(log(min(m,n))) 也是 O(log(m+n)) 的下界。从实际对比来看，当 m=1，n=1_000_000 时，暴力合并需要遍历百万级数据，而归并找第 k 小可能需要 O(log(1_000_001)) 次，但二分短数组只需常数次级别，差距非常明显。

每一次循环内部，只做了常数次索引访问和比较，没有额外的数组复制或排序。因此时间复杂度的上界不仅是 O(log(m+n))，而是更紧的 O(log(min(m,n)))。

6.2 空间复杂度：为什么是 O(1)

代码中只用了有限个变量：m、n、total_left、left、right、i、j，以及四个边界值。没有新建数组，也没有递归调用栈。因此空间复杂度是 O(1)，也就是原地操作。这也让这个解法在嵌入式或内存受限的面试场景里显得更优雅。

6.3 与其他解法的横向对比

6.4 复杂度优化的实际意义

你可能觉得，反正 O(m+n) 在面试里也能过，何必费劲写二分？但如果这道题的输入是两个非常大的数组，比如各一百万个元素，O(m+n) 意味着你要遍历两百万次，而 O(log(min(m,n))) 只需要移动大约 20 次。在真实的数据处理场景里，比如两个数据库表的有序主键求中位数，或者两个日志文件的时间戳数组求中位数，这种差距是数量级的。面试官要的不仅是你能解出题，更是你有没有意识到规模增长后的性能差异。

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

7.1 问题一：循环陷入死循环 或 left/right 不收敛

最常发生在你把 right 更新成 i 而不是 i-1 的时候。如果你对二分模板不熟悉，很容易在切大可切小时更新成 right = i，结果 i 永远不变，形成死循环。解决办法是，循环条件用 left <= right，更新时严格用 right = i - 1 和 left = i + 1。因为每次迭代要么 right 减小、要么 left 增大，最终一定退出。

另一个隐蔽的坑是 total_left 计算用的是(m + n + 1) // 2，如果写成(m + n) // 2，奇偶情形下总数会差 1，尤其是奇数总长度时，左半部分元素数量不够，导致 j 取到 n+1，越界访问。

7.2 问题二：越界访问，无法正确处理哨兵

如果你没有对 i == 0 或 i == m 做特殊处理，直接靠数组访问一定会抛异常。一个常见的错误写法是：

nums1_left_max = nums1[i - 1] nums1_right_min = nums1[i]

当 i=0 或 i=m 时，直接 IndexError。正确的思路是：任何可能越界的访问都先判断，越界则赋予无穷。在 Java/C++ 里尤其要注意，数组下标不能为负。

7.3 问题三：奇数偶数判断错误导致结果不对

总长度奇偶的判断应该是(m + n) % 2 == 1，这个没问题。但有人会把 total_left 的奇偶判断混在一起，比如想通过 total_left 的奇偶性来判断中位数是取一个还是两个元素，这是错误的。总长度奇偶，才是决定合并数组中位数的唯一依据。total_left 只是左半部分的个数，不代表合并数组的奇偶性。

7.4 问题四：误以为只需要满足 L1 <= R2

很多简化版讲解只写了 nums1_left_max <= nums2_right_min，漏掉了 nums2_left_max <= nums1_right_min。实际上两个条件必须同时满足，否则左半部分中 nums2 的最大值可能大于右半部分中 nums1 的最小值，合并顺序就被破坏了。你可以把elif nums1_left_max > nums2_right_min和else两个分支分别对应了两个方向的调整，漏掉任何一边都会导致二分方向错乱。

7.5 问题五：把递归实现改成迭代实现时出错

递归找第 k 小的写法也存在，但如果你把那一套逻辑硬套到“切分法”里，容易混淆“排除前 k/2 个元素”和“在短数组上调整 i”的区别。切分法不是递归地想“删掉哪些元素”，而是直接维护切分点的位置，通过 i 的移动来逼近正确边界。我建议你把两种解法分开记：一种是二分排除法（用于找第 k 小），一种是二分切分法（用于本题最优解），不要混着理解。

7.6 实测记录与调试建议

我在本地调试这道题时，最常用的调试手段是在循环内部打印 i、j、L1、R1、L2、R2，然后走查一个随机用例。比如：

i=2, j=4, L1=3, R1=8, L2=19, R2=21 i=4, j=2, L1=9, R1=15, L2=11, R2=18

对比打印结果，你能直观看到为什么切分方向会调整。等到送你上生产环境的算法题，你不可能再用 print 调试，所以强烈建议你现在就养成“手动构造小规模用例 + 打印中间状态 + 对照推导验证”的习惯。

7.7 边界用例速查表

8. 题目延伸：一套思想解决多道题

8.1 从“找中位数”到“找第 k 小元素”的抽象

掌握了切分法之后，你会发现它不只是解这一道题的工具。LeetCode 上还有一系列“两个有序数组合并求某种统计量”的题目，本质都可以转成“找第 k 小元素”的二分模型。切分法的核心思想是：用元素计数约束来替代实际合并，用交叉比较来确定搜索方向。这个思想在“求两个有序数组的上四分位数”“求 K 个有序数组的中位数”等变体里同样适用。

8.2 扩展到 K 个有序数组

如果面试官再问“如果有 K 个有序数组，怎么求中位数？”切分法的思路就需要延伸：K 个数组时，需要同时确定 K 个切分点，但计数约束只有一个，因此无法像两个数组那样用一个变量推导所有变量。常见的做法是改用优先队列（小顶堆）来模拟第 k 小元素的选择，或者用“多路归并 + 淘汰”的二分策略。这时候你会更深刻地理解，为什么这道题只要求两个数组却如此经典——它恰好提供了“一个变量推导另一个变量”的数学结构，这是不可多得的教学场景。

8.3 实际工程场景：在线分位数估算

在真实的后端系统里，分位数的计算通常不是一次性给你两个数组，而是持续追加数据。比如某个监控系统要统计请求耗时的中位数，日志源源不断写入，你不可能每次新来一条日志就归并排序一次。常见的工程方案有：

• 用两个堆（一个大根堆、一个小根堆）维护数据流的中位数。
• 用蓄水池抽样或 t-digest 等近似算法估算分位数。
• 如果数据来自两个有序列，且需要反复查询，则可以用“二分固定切分点 + 局部调整”的思路做缓存。

LeetCode 4 的切分思想，其实很像这种“维护两个分区的边界”的思路：你不需要关心所有元素，只需要知道边界位置在哪里。这个思维方式在工程上的价值，远超过刷题本身。

8.4 从这道题到二分查找能力的整体提升

说句掏心窝的话，我见过很多开发者，二分查找永远只会在“有序数组里找一个数”这种模板里打转。一旦遇到“两个数组”“不直接查找而是查找切分点”“通过计数间接推导位置”这类变体，就手足无措。LeetCode 4 是打破这个局限的最好训练题。你一旦能完全独立推导出 L1/R1/L2/R2 这套逻辑，再回头去做普通的二分模板题，会发现自己对“搜索空间”和“单调性”的理解深了一个层次。

我个人在实际刷题过程中，每做完一遍这道题，都会隔一两个月重新手写一次，每次都会发现新的理解偏差。最近一次重写时，我甚至重新审视了 total_left 公式讨厌而精妙的奇偶处理：(m+n+1)//2不仅保证了左边元素数量正确，而且天然让奇数长度下左边多一个，偶数长度下左右相等。这种数学细节，只有反复手推才能真正内化。

最后再分享一个小技巧

日常如果你在面试中遇到这道题，即使你对最优解不能完全确定，也可以先把“暴力合并 O(m+n)”讲给面试官听，然后再补充一句“这个思路是 O(m+n)，我有更优的方案，可以在较短的数组上二分，达到 O(log(min(m,n)))”。这一个补充，就能让面试官看出你不仅会解题，还有复杂度意识。实际面试里，能清晰讲出切分条件的人已经能拿到良好以上的评价了。刷完之后，建议你把这段推导过程写成自己的笔记，过几周再手写一遍。我实践的体会是，这种“隔段时间重写”的方式，比连续刷十道同类题都管用。