寻找两个正序数组的中位数
Median of Two Sorted Arrays
求两个升序数组的中位数，要求 O(log(m+n))；不允许直接把两个数组合并后排序。
在力扣中练习题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
解题思路
二分分割 · 只切不合并
在较短数组上找一条切线，使左右两半元素个数相等且交叉有序
中位数把有序序列分成左右两半。与其合并，不如在两个数组上各切一刀：nums1 切在 i，nums2 切在 j，令左半部分一共 (m+n+1)/2 个元素，即 j = (m+n+1)/2 - i。
切得对不对，只看四个边界值：aLeft、aRight、bLeft、bRight。合法条件是
aLeft <= bRight 且 bLeft <= aRight
也就是说，左半部分的最大值不超过右半部分的最小值。
如果 aLeft > bRight，说明 nums1 切得太靠右，i 要左移；否则说明切得太靠左，i 要右移。i 的取值是单调的，所以可以二分。
切在 nums1[2]、nums2[3]：左边界 9 / 4，右边界 10 / 5；aLeft 太大，切点要左移。
- i
- 2
- j
- 3
自拟数组第一次切在 i=2,j=3 时 aLeft=9 大于 bRight=6，不合法；调整到 i=1,j=4 后四个边界满足交叉条件，左半最大 5、右半最小 6，中位数是 5.5。
i 在较短数组上枚举，范围只有 0..m，因此时间 O(log min(m,n))，空间 O(1)。
易错点
- 在长数组上二分：i 的范围大，j 可能越界。
- j 的公式写成 (m+n)/2-i：奇数长度时左半会少一个元素。
- 切点在边界时不使用 ±∞：i=0 或 i=m 时会访问 nums[-1]。
- 偶数是直接返回 max(aLeft,bLeft)：还要求和右半最小值取平均。
归并 · 合并后取中位
像归并排序一样合并两个数组，再取中间
结果正确，但需要 O(m+n) 时间与 O(m+n) 空间，不满足题目的 O(log) 要求；仅作直觉对照。
最直白的做法：用双指针把两个有序数组合并成一个 all，然后按下标取中位数。长度是奇数时取 all[n/2]，偶数时取中间两个的平均值。
它的优点是绝不会写错边界，适合用来验证二分分割版的结果。缺点是时间和空间都是 O(m+n)，面试中如果题目明确要求 O(log(m+n))，这个方案不满足要求。
实际工程里如果数据量不大，归并版反而更稳妥；但在算法题里要明确说明它的复杂度代价。
- 1双指针合并两个有序数组。
- 2按总长度奇偶取中位数。
- 3偶数长度取中间两个的平均。
易错点
- 只合并到中位数就停止时下标算错：可以先合并全部，逻辑最简单。
- 偶数长度用整数除法：会丢掉 0.5。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums1 = [1,9,10,11,12]，nums2 = [2,3,4,5,6]把两个数组各切一刀，使左半部分一共 (m+n+1)/2 个元素；中位数只由切点两侧的四个值决定。
查看 C++ 代码
延伸阅读
- “第 k 小”问题可以在两个有序数组上二分，每次排除 k/2 个元素；中位数是它的特例。
- 分割法的四个边界值需要用 ±∞ 处理空侧，这是写对边界的关键。