困难

中频

二分查找

寻找两个正序数组的中位数

这是一道围绕数组展开的高频练习。建议先掌握「二分查找」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

数组

原题练习

题目分析

给你两个已经排好序的数组，要求找到把它们合起来之后的中位数。

题目还要求时间复杂度达到对数级。

一句话概括：

不用真的合并两个数组，而是通过二分找到一个合适的切分位置，让左右两边数量和大小关系都满足中位数条件。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：在较短数组上二分切分点，让左右两部分总长度平衡，且左半最大值不大于右半最小值。

推荐代码

推荐解法：二分查找

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

空间复杂度： O(1)

核心思路：在较短数组上二分切分点，让左右两部分总长度平衡，且左半最大值不大于右半最小值。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保nums1是较短的数组，以减少二分查找的次数
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.length;
        int n = nums2.length;
        int low = 0;
        int high = m;
        
        while (low <= high) {
            // 在nums1中进行二分查找
            int i = (low + high) / 2;
            // 计算nums2中的分割点
            int j = (m + n + 1) / 2 - i;
            
            // 边界值处理
            int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            
            int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
            
            // 检查是否找到正确的分割点
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // 计算中位数
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
                } else {
                    return Math.max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                // 分割点太靠右，向左移动
                high = i - 1;
            } else {
                // 分割点太靠左，向右移动
                low = i + 1;
            }
        }
        
        // 如果输入不合法，返回0
        return 0.0;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会在较短数组上二分切分点，而不是先合并两个数组。

核心过程

先保证在较短数组上二分，设它的切分点是 i。
根据总长度一半，算出另一个数组的切分点 j。
检查切分后左半最大值和右半最小值的关系是否满足全局有序。
一旦合法，根据总长度奇偶直接从边界元素里读出中位数。

复杂度总结

时间复杂度 O(log(min(m,n)))，空间复杂度 O(1)。

面试补一句：这题最核心的转折，是把“找中位数”改写成“找合法切分”。

核心思路

这题不是合并数组，而是在两个有序数组上同时找一个合法切分。只要切分后左边所有数都不大于右边所有数，中位数就能直接从边界元素读出来。

步骤讲解

先确保在较短数组上二分

总是在较短数组上搜索切分点，避免越界并保证复杂度最优。

为什么这样做：切分点范围更小，边界处理也更容易统一。

对应代码提示：if (m > n) return findMedianSortedArrays(nums2, nums1);

通过切分点平衡左右两半长度

设 i 是短数组切分点，则长数组切分点 j 由总长度一半推导出来。

为什么这样做：中位数定义要求左右两半元素个数平衡。

对应代码提示：int j = (m + n + 1) / 2 - i;

检查切分是否合法并调整方向

若左半最大值不大于右半最小值，切分合法；否则根据越界方向移动二分区间。

为什么这样做：合法切分一旦找到，中位数只取决于切分边界四个值。

对应代码提示：if (maxLeftA <= minRightB && maxLeftB <= minRightA) { ... }

易错点

试图先合并数组再找中位数

虽然能做，但复杂度是 O(m+n)，没达到题目要求。

正确理解：题目重点就是利用双数组有序性做切分二分。

切分点只保证长度平衡，不保证大小关系

长度平衡只是前提，还必须满足左半所有值都不大于右半所有值。

正确理解：同时检查两个跨数组边界关系。

边界值处理混乱

当切分点在数组首尾时，容易访问越界。

正确理解：把缺失边界视作 -∞ 或 +∞ 来统一比较。

复杂度与适用判断

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

空间复杂度：O(1)

比其他方案更好在哪里：比线性合并更符合题目要求，也是这道经典难题的标准最优解。

适用判断：两个有序数组同时参与中位数或第 k 小查找时，优先考虑切分二分。

额外提醒

长度平衡和大小关系同时满足，切分才算真正合法。

动画演示

如果你还没完全看懂，可以展开动画演示。

二分查找动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

两个有序数组

数组1

数组2

分割点

数组1分割点: 0

数组2分割点: 0

中位数结果

操作日志

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。