寻找两个正序数组的中位数 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2，请你找出并返回这两个正序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。

示例 1

输入：nums1 = [1,3], nums2 = [2]

输出：2.0（合并后 [1,2,3]，中位数 2）

示例 2

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.5（合并后 [1,2,3,4]，中位数 (2+3)/2）

💭 模拟答题者思考

1. 暴力：合并两数组再取中位数，O(m+n)，但题目要 O(log)。

2. 中位数的本质：把两数组切成「左右两半」，左半所有数 ≤ 右半所有数，且左半元素个数固定。

3. 只要确定 nums1 在哪切（切 i 个），nums2 的切法 j 就唯一确定（i + j = 左半总数）。

4. 对较短数组二分 i：若 L1 > R2 说明 i 太大，左移；若 L2 > R1 说明 i 太小，右移。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`i`	int	定义：较短数组 nums1 划入「左半部分」的元素个数维护：二分范围 [0, m] 更新：切分不合法时 i 左移或右移
`j`	int	定义：nums2 划入左半部分的个数，由 i 决定维护：始终满足 i + j = 左半部分总数更新：j = total_left - i
`L1,R1,L2,R2`	int	定义：两数组在切分处的左/右边界值（越界用 ±∞）维护：合法切分需 L1≤R2 且 L2≤R1 更新：随 i,j 取值

⌨️ 落码步骤

1. 保证在较短数组上二分（必要时交换）

2. total_left = (m + n + 1) // 2，二分 i 于 [0, m]

3. j = total_left - i，取四个边界 L1/R1/L2/R2（越界用 ±∞）

4. 若 L1 ≤ R2 且 L2 ≤ R1：奇数返回 max(L1,L2)，偶数返回 (max(L1,L2)+min(R1,R2))/2

5. 否则据 L1 > R2 调整二分区间

💻 代码实现

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        if len(nums1) > len(nums2):      # 保证在较短数组上二分
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        total_left = (m + n + 1) // 2
        INF = float('inf')
        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2           # nums1 左边放 i 个
            j = total_left - i           # nums2 左边放 j 个
            L1 = nums1[i - 1] if i > 0 else -INF
            R1 = nums1[i]     if i < m else INF
            L2 = nums2[j - 1] if j > 0 else -INF
            R2 = nums2[j]     if j < n else INF
            if L1 <= R2 and L2 <= R1:    # 找到正确切分
                if (m + n) % 2 == 1:
                    return float(max(L1, L2))
                return (max(L1, L2) + min(R1, R2)) / 2
            elif L1 > R2:
                hi = i - 1               # i 太大
            else:
                lo = i + 1               # i 太小
        return 0.0

class Solution {
public:
    double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
        if (a.size() > b.size()) swap(a, b);
        int m = a.size(), n = b.size();
        int total_left = (m + n + 1) / 2;
        const long INF = LONG_MAX;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2;       // a 左边放 i 个
            int j = total_left - i;      // b 左边放 j 个
            long L1 = (i > 0) ? a[i - 1] : -INF;
            long R1 = (i < m) ? a[i]     :  INF;
            long L2 = (j > 0) ? b[j - 1] : -INF;
            long R2 = (j < n) ? b[j]     :  INF;
            if (L1 <= R2 && L2 <= R1) {
                if ((m + n) % 2) return max(L1, L2);
                return (max(L1, L2) + min(R1, R2)) / 2.0;
            } else if (L1 > R2) hi = i - 1;
            else lo = i + 1;
        }
        return 0.0;
    }
};
// 时间 O(log(min(m,n)))，空间 O(1)

📈 复杂度分析

时间复杂度 O(log(min(m,n)))

空间复杂度 O(1)

⚠️ 常见坑

❗ 一定在较短数组上二分，否则 j 可能为负越界。

❗ 切分越界处用 ±∞ 兜底，避免访问 nums[-1] 或 nums[m]。

❗ total_left 用 (m+n+1)//2，奇偶统一，奇数时中位数落在左半最大值。

🔍 必测边界 Case

Case 1：一个数组为空

nums1 = [], nums2 = [1] → 1.0

Case 2：不重叠

nums1 = [1,2], nums2 = [3,4] → 2.5