Rippling 两个有序数组中位数：短数组二分分割

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 两个数组已按非降序排好，元素为范围可由 float 精确表示的整数，至少一个数组非空；返回普通数值中位数。
• 若原题允许流式数据、无序列表、字典频数或多个量化指标，本文的二分分割前提不成立。

解题路线

1. 总长 T，令左半边含 `(T+1)//2` 个元素；在较短数组 a 中选切点 i，较长数组 b 的切点 j 自动等于左半总数−i。
2. 定义 a 左最大/右最小、b 左最大/右最小；若 aLeft≤bRight 且 bLeft≤aRight，则左右分割正确。奇数返回两边左最大，偶数返回左最大与右最小的平均。
3. 若 aLeft>bRight，a 切得太靠右，缩小 high；否则 bLeft>aRight，a 切得太靠左，增大 low。短数组二分保证搜索 O(log min(m,n))。
4. 空侧用 ±∞ 哨兵仅参加比较，不进入实际求平均；全空明确拒绝。用全量合并排序作为独立 oracle 穷举 15,875 组小有序数组，覆盖空一侧、重复值、负数与奇偶长度。

手动走一遍

a=[1,3]、b=[2]，先交换使 a=[2] 较短；T=3 左侧要 2 个。切 a 后 1、b 后 1，左边最大 2，右边最小 3，中位数 2。a=[1,2]、b=[3,4] 则合法分割后取 (2+3)/2=2.5。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def median_two_sorted(a: list[int], b: list[int]) -> float:
    """Training contract: ascending arrays, at least one value, bounded ints."""
    if not a and not b:
        raise ValueError("both arrays empty")
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    left_size = (m + n + 1) // 2
    low, high = 0, m
    while low <= high:
        i = (low + high) // 2
        j = left_size - i
        a_left = a[i - 1] if i else float("-inf")
        a_right = a[i] if i < m else float("inf")
        b_left = b[j - 1] if j else float("-inf")
        b_right = b[j] if j < n else float("inf")
        if a_left <= b_right and b_left <= a_right:
            max_left = max(a_left, b_left)
            if (m + n) % 2:
                return float(max_left)
            return (max_left + min(a_right, b_right)) / 2
        if a_left > b_right:
            high = i - 1
        else:
            low = i + 1
    raise ValueError("arrays must be sorted")

复杂度

对较短数组长度 m、长数组 n≥m，时间 O(log(m+1))，只保存切点与边界值，辅助空间 O(1)；完整合并参考法是 O(m+n) 时间/空间。

易错点与追问

容易失分的边界

• 在较长数组上二分，虽然仍对数但失去最优短数组界。
• j 计算错位，使左侧数量不固定。
• 奇数时平均两个中心值。
• 空侧时访问下标 −1 或 len。
• 把 1155222 的待解析/字典中位数任务误认为原本就是两个有序数组。

继续深挖

• 两个数组都空时怎样约定？
• 如果数组降序或未排序会怎样？
• 若元素是巨大的整数，float 平均的精度如何处理？
• 怎样推广到第 k 小而非中位数？