京公网安备11010502063487号给定两个已经排好序的数组 nums1 和 nums2，求它们合并后的中位数，要求时间复杂度是对数级。把两个数组合并再取中间当然可以（线性时间），对数级的做法是二分：不合并，只找一个"切点"，把两个数组各自切成左右两半，使得两个左半合起来正好是全部元素的前一半，并且左半的最大值不超过右半的最小值。本文实测线性合并和二分切点的耗时差距，演示一个很隐蔽的边界错误（Python 的负下标不会报错，而是悄悄取错值），给出五种语言的实现，并把二分的过程做成分步演示。
完整题目见官方页面（链接在文末）。前几组基准用例和结果由一个独立的做法算出（把两个数组拼起来重新排序再取中间）。一共 11 组，覆盖：其中一个数组为空、两个数组完全没有交叠、全部元素相同、总数为奇数和偶数、负数：
输入 [[1,3],[2]] 输出 2.0 输入 [[1,2],[3,4]] 输出 2.5 输入 [[0,0],[0,0]] 输出 0.0 输入 [[],[1]] 输出 1.0 输入 [[2],[]] 输出 2.0 输入 [[1,3,5,7],[2,4,6,8,10,12]] 输出 5.5
设两个数组长度是 m 和 n（让 m ≤ n），左半部分一共需要 half = (m + n + 1) / 2 个元素。如果在 nums1 里取前 i 个进左半，那么 nums2 里就要取前 j = half - i 个。切对的条件是：nums1 左半的最大值不超过 nums2 右半的最小值，并且 nums2 左半的最大值不超过 nums1 右半的最小值。二分 i：如果 nums1 左半的最大值比 nums2 右半的最小值还大，说明 i 取多了；反过来说明取少了。切对之后，总数为奇数时，中位数是左半的最大值；偶数时，是左半最大值和右半最小值的平均。因为只在较短的数组上二分，时间是 O(log min(m, n))。
当 i = 0 时，nums1 的左半是空的，"左半的最大值"不存在，应该当作负无穷；i = m 时，"右半的最小值"应该是正无穷。如果偷懒直接写 a[i - 1]，Python 里 i = 0 会变成 a[-1]，不报错，而是悄悄取到数组的最后一个元素。下面是没有哨兵的写法在会触发边界的用例上的真实结果：
# 左侧没有元素时直接取 a[i-1]（没有 -∞ 哨兵）的写法：Python 的负下标不会报错，而是悄悄取到最后一个元素 nums1=[1, 2], nums2=[3, 4]: 无哨兵写法 -> 3.5 正确写法 -> 2.5 暴力解 -> 2.5 nums1=[], nums2=[1]: 无哨兵写法 -> 抛出 IndexError 正确写法 -> 1.0 暴力解 -> 1.0 nums1=[2], nums2=[]: 无哨兵写法 -> 抛出 IndexError 正确写法 -> 2.0 暴力解 -> 2.0 nums1=[1000000], nums2=[-1000000]: 无哨兵写法 -> 1000000.0 正确写法 -> 0.0 暴力解 -> 0.0
nums1 = [1, 2]、nums2 = [3, 4] 这种两个数组完全不交叠的输入，正确答案是 2.5，没有哨兵的写法得到 3.5，没有任何报错，很容易被当成"逻辑对了、只是漏了一个边界"。有一个数组为空时，没有哨兵的写法直接抛出 IndexError。这是 Python 特有的、更难发现的错误：Java 里 a[-1] 会抛出数组越界异常，Go 会 panic，而 C++ 的 vector 用 [-1] 访问是未定义行为（这次没有实测它的表现）。
五种语言都用同样的结构。哨兵的取法不同：Python 和 JavaScript 用 ±Infinity，Java 和 C++ 用 Integer.MIN_VALUE / INT_MIN、INT_MAX（并在偶数情况下先转成 long 再相加，防止两个极值相加溢出），Go 用一个很大的常量。五种语言都是真实编译运行的。
Python · 解法代码def solve(nums1, nums2): a, b = nums1, nums2 if len(a) > len(b): a, b = b, a # 在较短的数组上二分 m, n = len(a), len(b) half = (m + n + 1) // 2 # 左半部分的元素个数（总数为奇数时，左半多一个） INF = float("inf") lo, hi = 0, m while lo <= hi: i = (lo + hi) // 2 # a 的左半取 i 个 j = half - i # b 的左半取 j 个 a_left = a[i - 1] if i > 0 else -INF a_right = a[i] if i < m else INF b_left = b[j - 1] if j > 0 else -INF b_right = b[j] if j < n else INF if a_left > b_right: # a 的左半取多了 hi = i - 1 elif b_left > a_right: # a 的左半取少了 lo = i + 1 else: # 左半的最大值 <= 右半的最小值，切对了 if (m + n) % 2: return float(max(a_left, b_left)) return (max(a_left, b_left) + min(a_right, b_right)) / 2 raise ValueError("输入不是有序数组")
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,3],[2]] → 2.0 [[1,2],[3,4]] → 2.5 [[0,0],[0,0]] → 0.0 [[],[1]] → 1.0 [[2],[]] → 2.0 [[1,3,5,7],[2,4,6,8,10,12]] → 5.5
Java · 解法代码class Solution { public double findMedianSortedArrays(int[] a, int[] b) { if (a.length > b.length) return findMedianSortedArrays(b, a); // 在较短的数组上二分 int m = a.length, n = b.length, half = (m + n + 1) / 2; int lo = 0, hi = m; while (lo <= hi) { int i = (lo + hi) / 2, j = half - i; // a 的左半取 i 个，b 的左半取 j 个 int aL = i > 0 ? a[i - 1] : Integer.MIN_VALUE, aR = i < m ? a[i] : Integer.MAX_VALUE; int bL = j > 0 ? b[j - 1] : Integer.MIN_VALUE, bR = j < n ? b[j] : Integer.MAX_VALUE; if (aL > bR) hi = i - 1; else if (bL > aR) lo = i + 1; else { int left = Math.max(aL, bL); if ((m + n) % 2 == 1) return left; return (left + (long) Math.min(aR, bR)) / 2.0; } } throw new IllegalArgumentException("输入不是有序数组"); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,3],[2]] → 2.00000 [[1,2],[3,4]] → 2.50000 [[0,0],[0,0]] → 0.00000 [[],[1]] → 1.00000 [[2],[]] → 2.00000 [[1,3,5,7],[2,4,6,8,10,12]] → 5.50000
Go · 解法代码func findMedianSortedArrays(a, b []int) float64 { if len(a) > len(b) { return findMedianSortedArrays(b, a) // 在较短的数组上二分 } const inf = 1 << 60 m, n := len(a), len(b) half := (m + n + 1) / 2 lo, hi := 0, m for lo <= hi { i := (lo + hi) / 2 // a 的左半取 i 个 j := half - i // b 的左半取 j 个 aL, aR, bL, bR := -inf, inf, -inf, inf if i > 0 { aL = a[i-1] } if i < m { aR = a[i] } if j > 0 { bL = b[j-1] } if j < n { bR = b[j] } if aL > bR { hi = i - 1 } else if bL > aR { lo = i + 1 } else { left := max(aL, bL) if (m+n)%2 == 1 { return float64(left) } return float64(left+min(aR, bR)) / 2 } } panic("输入不是有序数组") }
$ go build -o bin . && ./bin < cases.jsonl [[1,3],[2]] → 2 [[1,2],[3,4]] → 2.5 [[0,0],[0,0]] → 0 [[],[1]] → 1 [[2],[]] → 2 [[1,3,5,7],[2,4,6,8,10,12]] → 5.5
JavaScript · 解法代码function findMedianSortedArrays(a, b) { if (a.length > b.length) return findMedianSortedArrays(b, a); // 在较短的数组上二分 const m = a.length, n = b.length, half = Math.floor((m + n + 1) / 2); let lo = 0, hi = m; while (lo <= hi) { const i = Math.floor((lo + hi) / 2), j = half - i; // a 的左半取 i 个，b 的左半取 j 个 const aL = i > 0 ? a[i - 1] : -Infinity, aR = i < m ? a[i] : Infinity; const bL = j > 0 ? b[j - 1] : -Infinity, bR = j < n ? b[j] : Infinity; if (aL > bR) hi = i - 1; else if (bL > aR) lo = i + 1; else { const left = Math.max(aL, bL); if ((m + n) % 2 === 1) return left; return (left + Math.min(aR, bR)) / 2; } } throw new Error('输入不是有序数组'); }
$ node run.js < cases.jsonl [[1,3],[2]] → 2 [[1,2],[3,4]] → 2.50000 [[0,0],[0,0]] → 0 [[],[1]] → 1 [[2],[]] → 2 [[1,3,5,7],[2,4,6,8,10,12]] → 5.50000
C++ · 解法代码#include <algorithm> #include <climits> #include <stdexcept> #include <vector> using namespace std; class Solution { public: double findMedianSortedArrays(vector<int>& a, vector<int>& b) { if (a.size() > b.size()) return findMedianSortedArrays(b, a); // 在较短的数组上二分 int m = a.size(), n = b.size(), half = (m + n + 1) / 2; int lo = 0, hi = m; while (lo <= hi) { int i = (lo + hi) / 2, j = half - i; // a 的左半取 i 个，b 的左半取 j 个 int aL = i > 0 ? a[i - 1] : INT_MIN, aR = i < m ? a[i] : INT_MAX; int bL = j > 0 ? b[j - 1] : INT_MIN, bR = j < n ? b[j] : INT_MAX; if (aL > bR) hi = i - 1; else if (bL > aR) lo = i + 1; else { int left = max(aL, bL); if ((m + n) % 2 == 1) return left; return ((long long)left + min(aR, bR)) / 2.0; } } throw invalid_argument("输入不是有序数组"); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,3],[2]] → 2.00000 [[1,2],[3,4]] → 2.50000 [[0,0],[0,0]] → 0.00000 [[],[1]] → 1.00000 [[2],[]] → 2.00000 [[1,3,5,7],[2,4,6,8,10,12]] → 5.50000
共 11 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 11/11 Java 通过 11/11 Go 通过 11/11 JavaScript 通过 11/11 C++ 通过 11/11
下面比较的"暴力解"是把两个数组拼起来再排序取中间。这里两个数组交错排列（一个全是偶数，一个全是奇数），每个规模取三次中最快的一次：
每个数组的长度 n | 暴力解 | 本文解法
1000 | 0.023 ms | 0.001 ms
10000 | 0.157 ms | 0.001 ms
100000 | 1.542 ms | 0.002 ms
1000000 | 21.590 ms | 0.011 ms数组长度扩大 1000 倍（从 1000 到 1000000），暴力解耗时从 0.019ms 涨到 21.9ms，约 1150 倍，基本是线性；二分解法从 0.001ms 涨到 0.012ms，不到 12 倍，远小于线性。前几个规模的二分耗时已经接近计时器的分辨率（0.001ms），所以这里不能用这些数字去拟合出严格的对数曲线，只能说明"远慢于线性增长"。
Python 版本另外和暴力解做了随机对拍：
随机对拍 10000 组（两个长度各 0 到 10（不同时为空）、取值 -20 到 20 的随机有序数组，重复值很多），solve 与 brute 的结果全部一致。
另外四种语言只在上面 11 组固定用例上验证过，其中包含空数组和无交叠的边界用例，没有做大规模随机对拍。
下面的演示用 nums1 = [1, 3, 8, 9, 15]、nums2 = [7, 11, 18, 19, 21, 25]（共 11 个数）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的中位数与 solve 的返回值一致。绿色的格子是划进左半的部分，蓝色的格子是切点两侧紧挨着的元素。