跳至主要內容

寻找两个正序数组的中位数：O(log(m+n)) 完整推导

老张2026/4/30大约 8 分钟

寻找两个正序数组的中位数：O(log(m+n)) 完整推导

适读人群：Java 后端工程师、算法高阶学习者 | 阅读时长：约 22 分钟 | 难度：⭐⭐⭐⭐⭐

开篇故事

LeetCode 4，全站难度 Hard，但它的难不在于数据结构有多复杂，而在于那个 O(log(m+n)) 的要求。

很多人能想到 O((m+n)log(m+n)) 的排序合并，也能想到 O(m+n) 的双指针归并，但 O(log(m+n)) 卡住了绝大多数人。

我第一次做这道题时，花了将近三个小时。不是不会二分，而是一直想不清楚"在哪个空间上二分"。直到我换了一个角度——不是在数组里找中位数，而是在划分方式上二分：把两个数组各自划分成左右两半，让左半部分的所有元素都 <= 右半部分的所有元素，然后中位数就从这个划分的边界处取得。

这个思路一旦想通，代码就呼之欲出了。下面我来完整地推导这个过程。

一、题目解析

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

示例：

  • nums1 = [1,3], nums2 = [2] → 中位数 2.0
  • nums1 = [1,2], nums2 = [3,4] → 中位数 2.5

二、解法一：合并排序（O((m+n)log(m+n))）

思路分析

最朴素的方法：合并两个数组后排序，取中间元素。

完整代码

public class Solution1 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];
        System.arraycopy(nums1, 0, merged, 0, m);
        System.arraycopy(nums2, 0, merged, m, n);
        Arrays.sort(merged);

        int total = merged.length;
        if (total % 2 == 0) {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        } else {
            return merged[total / 2];
        }
    }
}

复杂度分析

  • 时间复杂度：O((m+n)log(m+n))。排序的代价。
  • 空间复杂度：O(m+n)。合并数组的空间。

三、解法二：双指针归并（O(m+n)）

思路分析

用双指针归并，只取前 (m+n)/2 个元素，就能确定中位数，无需完整归并。

public class Solution2 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int i = 0, j = 0;

        int prev = 0, curr = 0;  // 记录第 k-1 和第 k 个元素
        for (int k = 0; k <= total / 2; k++) {
            prev = curr;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                curr = nums1[i++];
            } else {
                curr = nums2[j++];
            }
        }

        if (total % 2 == 0) {
            return (prev + curr) / 2.0;
        } else {
            return curr;
        }
    }

    public static void main(String[] args) {
        Solution2 sol = new Solution2();
        System.out.println(sol.findMedianSortedArrays(new int[]{1, 3}, new int[]{2})); // 2.0
        System.out.println(sol.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4})); // 2.5
    }
}

复杂度分析

  • 时间复杂度：O(m+n)。
  • 空间复杂度：O(1)。

四、解法三最优：二分 + 划分（O(log(min(m,n)))）

核心思路推导

划分的定义：

设 m + n = total，中位数将合并后的数组分成相等（或相差一）的两部分：

  • 左半部分大小 = (total + 1) / 2（奇数时多一个，偶数时相等）
  • 右半部分大小 = total / 2

对 nums1 取前 i 个，对 nums2 取前 j 个，使得 i + j = (total + 1) / 2。

这样左半部分由 nums1[0..i-1] 和 nums2[0..j-1] 组成，右半部分由 nums1[i..m-1] 和 nums2[j..n-1] 组成。

合法划分的条件：

要使这个划分有意义（左半 <= 右半），需要满足：

  1. nums1[i-1] <= nums2[j]（nums1 左边的最大值 <= nums2 右边的最小值）
  2. nums2[j-1] <= nums1[i]（nums2 左边的最大值 <= nums1 右边的最小值）

在 i 上二分：

因为 j = (total + 1) / 2 - i，确定了 i 就确定了 j。在 i 上二分：

  • 若 nums1[i-1] > nums2[j]：i 太大，令 right = i - 1。
  • 若 nums2[j-1] > nums1[i]：i 太小，令 left = i + 1。

找到合法划分后：

  • 左半最大值 = max(nums1[i-1], nums2[j-1])
  • 右半最小值 = min(nums1[i], nums2[j])
  • 奇数总长：中位数 = 左半最大值
  • 偶数总长：中位数 = (左半最大值 + 右半最小值) / 2.0

边界处理：

  • i = 0：nums1 左半为空，nums1Left = Integer.MIN_VALUE
  • i = m：nums1 右半为空，nums1Right = Integer.MAX_VALUE
  • j = 0：nums2 左半为空，nums2Left = Integer.MIN_VALUE
  • j = n：nums2 右半为空，nums2Right = Integer.MAX_VALUE

Mermaid 图：二分划分过程

完整代码

public class Solution3 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 保证 nums1 是较短的数组（在较短数组上二分，效率更高）
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length, n = nums2.length;
        int half = (m + n + 1) / 2;  // 左半部分的总元素数

        // 二分 i：nums1 中划入左半部分的元素个数，范围 [0, m]
        int left = 0, right = m;

        while (left <= right) {
            int i = left + (right - left) / 2;  // nums1 划分点
            int j = half - i;                    // nums2 划分点

            // 获取划分边界的四个值（处理边界越界）
            int nums1Left  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1Right = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int nums2Left  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int nums2Right = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (nums1Left > nums2Right) {
                // nums1 划分点太靠右，左移
                right = i - 1;
            } else if (nums2Left > nums1Right) {
                // nums1 划分点太靠左，右移
                left = i + 1;
            } else {
                // 找到合法划分
                int maxLeft = Math.max(nums1Left, nums2Left);
                int minRight = Math.min(nums1Right, nums2Right);

                if ((m + n) % 2 == 1) {
                    return maxLeft;            // 奇数总长，中位数是左半最大值
                } else {
                    return (maxLeft + minRight) / 2.0;  // 偶数总长
                }
            }
        }

        // 理论上不会到达这里（输入保证合法）
        throw new IllegalArgumentException("Input arrays are not sorted.");
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();

        // 基本测试
        System.out.println(sol.findMedianSortedArrays(
                new int[]{1, 3}, new int[]{2}));          // 2.0
        System.out.println(sol.findMedianSortedArrays(
                new int[]{1, 2}, new int[]{3, 4}));       // 2.5
        System.out.println(sol.findMedianSortedArrays(
                new int[]{0, 0}, new int[]{0, 0}));       // 0.0
        System.out.println(sol.findMedianSortedArrays(
                new int[]{}, new int[]{1}));               // 1.0
        System.out.println(sol.findMedianSortedArrays(
                new int[]{2}, new int[]{}));               // 2.0

        // 边界测试
        System.out.println(sol.findMedianSortedArrays(
                new int[]{1, 2, 3, 4, 5}, new int[]{6, 7, 8, 9, 10})); // 5.5
        System.out.println(sol.findMedianSortedArrays(
                new int[]{1}, new int[]{2, 3, 4, 5, 6})); // 3.5
    }
}

复杂度分析

  • 时间复杂度：O(log(min(m,n)))。在较短数组上二分，每次减半，最多 log₂(min(m,n)) 次。
  • 空间复杂度：O(1)。只用了常数个变量。

注意：题目要求 O(log(m+n))，而这里实现了更优的 O(log(min(m,n)))，完全满足要求。

五、举一反三：同类题与模板应用

题号题目关联点
215数组中的第 K 个最大元素分治找第 k 小，类似二分划分思想
378有序矩阵中第K小的元素在答案空间二分 + 计数验证
373查找和最小的 K 对数字多路归并思想
295数据流的中位数动态维护中位数，双堆方法

关键技巧总结：

// 处理边界的标准写法
int nums1Left  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1Right = (i == m) ? Integer.MAX_VALUE : nums1[i];
int nums2Left  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2Right = (j == n) ? Integer.MAX_VALUE : nums2[j];

// half 的计算（保证奇偶都正确）
int half = (m + n + 1) / 2;
// 当 m+n 为奇数时，left half 有 half = (m+n+1)/2 个元素，多一个
// 当 m+n 为偶数时，left half 和 right half 各有 half = (m+n)/2 个元素

六、踩坑实录

坑一：忘记让 nums1 是较短数组

二分是在 nums1 上进行的，范围是 [0, m]，所以时间复杂度是 O(log m)。如果 m > n，那么时间复杂度就是 O(log m) 而不是 O(log(min(m,n)))。通过先交换让 nums1 始终是较短数组，才能保证最优复杂度，同时也能简化对 j 的越界检查（因为 j 的范围由 m 和 n 共同决定，m 小则 j 的范围更稳定）。

坑二：half = (m + n + 1) / 2 而不是 (m + n) / 2

如果用 (m + n) / 2，当总长为奇数时，中位数应该是第 (m+n+1)/2 个元素（从1开始），但 (m+n)/2 计算出的 half 比实际少1，导致划分点偏左，取出的中位数错误。我在这里栽过一次，调试了很久。

坑三：Integer.MIN_VALUE 和 Integer.MAX_VALUE 在计算时可能溢出

当 (maxLeft + minRight) / 2.0 中，maxLeft 是 Integer.MIN_VALUE，minRight 是某个正数时，maxLeft + minRight 在 int 运算下可能溢出。解决方案：把计算改为 maxLeft / 2.0 + minRight / 2.0，或者先转成 long。不过在实际测试中，因为我用了 Integer.MIN_VALUE 只作为哨兵值（表示数组边界为空），正常数据不会触发这个边界，但保险起见还是要注意。

坑四：循环条件用 < 还是 <=

这里用 while (left <= right)，因为 i 的搜索范围是 [0, m]，包含两个端点，是闭区间。当 left == right 时还有一个值需要检查。如果用 <，最后一个合法的 i 值可能被漏掉。

坑五：没有验证空数组的情况

当 nums1 为空时，i 只能取 0，二分立即结束，j = half = (n+1)/2，直接取 nums2 的中位数。这种情况应该被通用逻辑覆盖，不需要特判，但要确认你的代码确实覆盖了这种情况。

七、总结

LeetCode 4 是 LeetCode 全站公认最难的 Hard 之一。O(log(m+n)) 解法的关键在于：

  1. 将"找中位数"问题转化为"找合法划分"问题。
  2. 用二分在较短数组上枚举划分点 i，从而 O(1) 确定 j。
  3. 通过检验划分合法性（左半最大 <= 右半最小）来决定 i 的移动方向。

这道题综合考察了二分查找、边界处理、数学推导三个方面，是最好的二分进阶练习题。一旦做透了这道题，你会发现二分查找在思维层面上已经没有太大挑战了。

编辑此页
最近更新:
贡献者: xiaozhangge