寻找两个正序数组的中位数：从暴力到二分查找最优解

做算法题最怕的就是那种“一看答案就懂，一上手就废”的题。LeetCode热题100里的寻找两个正序数组的中位数，就是非常典型的一道。表面上是求中位数，实际上考察的是二分查找的边界控制能力、递归设计能力，以及对时间复杂度的敏感度。你要是去面试后端岗位，尤其是Java岗位，这题被问到的概率相当高，而且面试官通常会让你从暴力解法开始，一步步追问到最优解。

我最早刷这道题的时候，第一反应是合并数组排序，然后直接取中间值，简单省事。但题目要求在O(log (m+n))的时间复杂度内完成，这就直接把暴力方案否决了。如果你正在准备面试，或者刷题卡在这道题上很久，这篇内容会很有帮助。我会从最直观的暴力解法讲起，逐步过渡到双指针、二分排除法，再到真正的O(log(min(m,n)))最优解，代码全部用Java写，注释尽量详细，读完你不仅能AC这道题，还能把这一类“第K小元素”的题目打通。

1. 内容整体设计与思路拆解

1.1 这道题到底在考什么

先看题面：给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2，要求找出并返回这两个正序数组的中位数。这里有个细节，题目并没有说两个数组长度相同，也没说哪个更长，所以你的解法必须同时处理奇数长度和偶数长度的情况。

很多人在这一步就犯迷糊了：为什么要单独讨论奇偶？因为中位数的定义有两个分支——如果合并后数组长度为奇数，中位数就是最中间那个数；如果是偶数，中位数就是中间两个数的平均值。

直接合并数组的做法，时间复杂度是O(m+n)，虽然能过一些测试用例，但遇到大数据量会超时。最优解要求O(log(min(m+n)))。看到log就应该条件反射想到二分查找，这是解题方向的核心线索。

1.2 方案选型的思考路径

从暴力到最优解，其实就是一个逐步优化的过程，每一层优化背后都有明确的动机：

第一层是暴力合并，它的优点是直觉、好写、不容易出错，适合用来验证思路；缺点是时间复杂度和空间复杂度都比较高。第二层是双指针归并，它不需要额外开辟新数组，节省了空间，但时间复杂度仍然是O(m+n)。第三层是二分排除法，不需要真正归并数组，而是通过不断排除不可能是答案的元素来逼近目标，时间复杂度降到了O(log(m+n))，已经满足题目要求了，但代码还有优化空间。第四层是分割法，这是最优解，时间复杂度进一步降到O(log(min(m+n)))，核心思路是利用较短数组做二分切割，通过比较切割点两侧的值来确定正确分割位置。

我自己刷题的习惯是：先把暴力解写出来，跑通之后再去想优化。不要一上来就奔着最优解去，因为你对问题本身还没有足够的感知，直接看最优解容易看得懂却记不住，下次遇到还是不会。

2. 基础解法：暴力合并与双指针归并

2.1 暴力合并：最直观的解法

暴力合并的思路很简单：把两个数组合并成一个新的数组，然后根据新数组的长度奇偶求中位数。代码写起来也不难。

public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[] merged = new int[m + n]; int i = 0, j = 0, k = 0; while (i < m && j < n) { if (nums1[i] <= nums2[j]) { merged[k++] = nums1[i++]; } else { merged[k++] = nums2[j++]; } } while (i < m) { merged[k++] = nums1[i++]; } while (j < n) { merged[k++] = nums2[j++]; } int total = m + n; if (total % 2 == 1) { return merged[total / 2]; } else { return (merged[total / 2 - 1] + merged[total / 2]) / 2.0; } }

这段代码就是把归并排序里的merge操作单独拎出来用。时间复杂度O(m+n)，空间复杂度O(m+n)，因为开了新数组。

这个方案能不能用？能用，而且你做笔试的时候，如果时间紧迫，这个方案能保证你拿一部分分数。但它的缺点也很明显：空间浪费。其实我们根本不需要完整的合并数组，只需要知道中间位置的那个值就够了，所以可以优化成只存储值，不存储全部数据。

2.2 双指针归并：省掉额外数组的开销

暴力合并浪费了额外的数组空间，那能不能边比较边计数，等到走到中位数的位置直接返回？当然可以。这就是双指针归并法。

public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int total = m + n; int i = 0, j = 0; int prev = 0, curr = 0; 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 == 1) { return curr; } else { return (prev + curr) / 2.0; } }

核心思想：用两个指针分别指向两个数组的头部，每次比较两个指针指向的元素，把较小的那个“取走”，然后指针后移。这样的话就不需要真正合并完所有元素，只要走到中位数所在的位置就可以停了。

但这里要注意几个边界情况。第一个是某个数组已经走完了，比如i >= m，那说明nums1已经全部被取走，剩下的都从nums2取。第二个是j >= n同理。第三个是循环次数要保证走到中间位置，偶数长度时还需要保留前一个值prev，方便算平均值。

这个解法的空间复杂度降到了O(1)，但时间复杂度还是O(m+n)。为什么？因为最坏情况下你还是可能要遍历一半以上的元素。比如m=n=10000，你要遍历到第10000或者10001个位置才能拿到中位数。还是不够快，下一步就必须上二分。

3. 二分排除法：把时间复杂度降到对数级

3.1 第K小元素的视角

既然要找中位数，那我们可以换一个角度来看：在两个有序数组中找中位数，本质上就是找第K小的元素。如果合并后的总长度total是奇数，中位数就是第total/2+1小的元素；如果total是偶数，中位数就是第total/2小和第total/2+1小两个元素的平均值。

这样问题就转化成了——如何快速地在两个有序数组中找到第K小的元素？

如果还是通过归并的方式一个一个数，那就是O(K)的时间复杂度。K的范围最坏情况下接近(m+n)/2，还是一个大数。所以我们需要一种跳跃式的搜索方法，每一步排除掉尽可能多的元素。

3.2 二分排除法的核心策略

思想其实很朴素：每次比较两个数组中第k/2个元素，较小的那个，它前面的所有元素都不可能是第K小元素，可以直接排除掉。

为什么这么说？假如数组A的长度足够长，B的长度也足够长，我们比较A[k/2-1]和B[k/2-1]。假设A[k/2-1]更小，那A中前k/2个元素都小于等于A[k/2-1]，而B中前k/2-1个元素都小于B[k/2-1]，加起来最多k-1个元素比A[k/2-1]小。所以A[k/2-1]最多只是第K-1小的元素，它绝对不可能是第K小元素，A的前k/2个元素全部可以排除。

排除之后，K需要减去被排除的元素个数，然后继续在剩下的数组中找新的第K小元素。这样每一轮都大约排除k/2个元素，整体复杂度就是O(log(m+n))。

3.3 Java实现与边界控制

实现了这个思路，代码难点反而在边界处理上。尤其是当某个数组长度不足k/2时，我们只能取它的全部长度来比较。

public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total = nums1.length + nums2.length; if (total % 2 == 1) { return getKthElement(nums1, nums2, total / 2 + 1); } else { return (getKthElement(nums1, nums2, total / 2) + getKthElement(nums1, nums2, total / 2 + 1)) / 2.0; } } private int getKthElement(int[] nums1, int[] nums2, int k) { int m = nums1.length; int n = nums2.length; int i = 0, j = 0; while (true) { // 边界情况：有一个数组全部被排除了 if (i == m) { return nums2[j + k - 1]; } if (j == n) { return nums1[i + k - 1]; } // 只找第1小的元素，直接比较两个数组当前的最小值 if (k == 1) { return Math.min(nums1[i], nums2[j]); } // 取 k/2 个元素，但要注意数组剩余长度可能不足 int half = k / 2; int newI = Math.min(i + half, m) - 1; int newJ = Math.min(j + half, n) - 1; if (nums1[newI] <= nums2[newJ]) { // 排除 nums1 前半段 k -= (newI - i + 1); i = newI + 1; } else { // 排除 nums2 前半段 k -= (newJ - j + 1); j = newJ + 1; } } }

我来说几个关键边界点：

当某个数组已经被排除完（i == m），第K小元素一定在另一个数组的剩余部分中，位置是剩余数组起点加上k-1的偏移量。

当k == 1时，说明只要找最小的那个元素，直接比较两个数组当前指针位置的值，取较小的返回，这其实也等价于min(nums1[i], nums2[j])。

取newI的时候一定要用Math.min(i + half, m) - 1，防止数组越界。这是最容易写错的地方，很多人一上来就写i + half，结果在数组长度不够的时候直接越界。

nums1[newI] <= nums2[newJ]这个判断里，小于等于和小于在大部分情况下结果一样，但为了稳定性建议取等号时排除第一个数组的元素，这样可以减少后续比较次数。

这个解法的时间复杂度是O(log(m+n))，空间复杂度是O(1)。到这里，其实已经符合LeetCode对这道题的时间约束了。但还有更优的解法，它利用了两个数组中较短的那个数组做二分，时间复杂度降到了O(log(min(m,n)))。面试的时候，你如果能把这个也讲出来，那基本就是满分答案。

4. 最优解：分割法深入解析

4.1 为什么要用较短数组做二分

上面说的二分排除法虽然已经是对数级复杂度，但它的对数底数是m+n。分割法的思路不一样：我们不做排除，而是直接用二分查找的方式，在较短的数组中寻找一个合适的分割点，使得左右两侧元素数量相等且满足有序性。

为什么选较短的数组？因为二分的次数取决于数组长度，较短的数组长度小，二分次数就少。时间复杂度从O(log(m+n))变成O(log(min(m+n)))，在m和n相差悬殊的时候，差距是相当明显的。比如一个数组长度是100万，另一个长度是10，O(log(1000010))大约是20次迭代，而O(log(10))只有3到4次迭代，性能提升肉眼可见。

4.2 分割法的核心逻辑

先把两个数组分别叫作A和B，长度分别为m和n。假设m <= n，确保A是较短的数组。

我们在A中选取一个分割点i，范围是0到m。分割点i的含义是：A的左边部分有i个元素，A的右边部分有m-i个元素。同理，在B中我们需要一个对应的分割点j，使得左右两侧总数相等，或者说满足以下关系：

当总长度为偶数时，左边元素总数等于总长度的一半，也就是i+j = (m+n)/2；当总长度为奇数时，左边元素总数等于(total+1)/2，也就是i+j = (total+1)/2。

所以可以得到j = (m+n+1)/2 - i。

有了i和j之后，我们就能得到四个关键值：A[i-1]和A[i]，B[j-1]和B[j]。其中A[i-1]是A的左半部分最大值，B[j-1]是B的左半部分最大值，A[i]是A的右半部分最小值，B[j]是B的右半部分最小值。

如果此时满足两个条件：

第一个是A[i-1] <= B[j]，也就是说A的左半部分最大值不超过B的右半部分最小值，那么就不会出现交错的情况。第二个是B[j-1] <= A[i]，同理，B的左半部分最大值不超过A的右半部分最小值。

那我们就找到了一个合法的分割点。此时左半部分的最大值就是max(A[i-1], B[j-1])，右半部分的最小值就是min(A[i], B[j])。如果总长度是奇数，中位数就是左半部分的最大值；如果是偶数，中位数就是左半部分最大值和右半部分最小值的平均值。

如果A[i-1] > B[j]，说明A的左半部分太大了，i应该往左移，也就是缩小i。如果B[j-1] > A[i]，说明B的左半部分太大了，j应该往左移，反过来也就是i往右移。这就是二分的依据。

4.3 Java最优解代码实现

这里我直接给出一个完整实现，并且在注释里写清楚每一步的判断逻辑。

public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证 nums1 是较短的数组，方便后续二分 if (nums1.length > nums2.length) { int[] temp = nums1; nums1 = nums2; nums2 = temp; } int m = nums1.length; int n = nums2.length; int totalLeft = (m + n + 1) / 2; // 左半部分需要的元素总数 int left = 0, right = m; while (left < right) { int i = left + (right - left + 1) / 2; // 注意是向上取整 int j = totalLeft - i; if (nums1[i - 1] > nums2[j]) { // i 太大，需要左移 right = i - 1; } else { // i 还可以继续增大 left = i; } } int i = left; int j = totalLeft - i; // 处理边界：i=0 或 i=m 时，对应位置没有值 int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i]; int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j]; if ((m + n) % 2 == 1) { return Math.max(nums1LeftMax, nums2LeftMax); } else { return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0; } }

这段代码是整个题解的关键，也是面试最常考的版本。我建议你理解之后，不要死记硬背，而是把分割条件的推导过程写一遍，这样才能真正变成自己的东西。

4.4 为什么left = mid时要向上取整

这是一个非常细微但极度容易踩坑的点。在二分分割法的循环里，我们用了left + (right - left + 1) / 2而不是left + (right - left) / 2。为什么？

因为当我们判断nums1[i-1] > nums2[j]时，要把右边界收缩到right = i - 1；但判断不成立时，要让left = i。这种情况下，如果mid的计算是向下取整，可能会在某个时刻出现left和right相邻且mid恒等于left的情况，比如left=2, right=3时，向下取整的mid是2，如果此时判断需要执行left = mid，那left还是2，永远无法前进，导致死循环。

而向上取整可以保证在left和right相邻时，mid会等于right，这样left = mid就能前进到right，循环必定会收敛。这是二分查找里非常经典的一个细节，掌握了这个细节，很多二分的变种题都能轻松应对。

5. 时间复杂度的完整对比

把四种解法放在一起对比，思路就非常清晰了。

我曾经在一次代码评审里看到有人把暴力合并的方案提交上去，理由是“功能正确”。这确实没错，但算法题也好，工作场景也罢，我们评估代码不能只看“能跑”，还要看它在极限条件下的表现。如果是两个长度接近100万的有序数组，暴力合并就会创建一个长度200万的临时数组，既要花内存又要花时间，这在真实业务里是不可接受的。

6. 常见问题与排查技巧实录

6.1 边界条件总是出错怎么办

边界条件出错，最常见的就是数组为空、i等于0、i等于m这三种情况。

数组为空好处理，函数入口处加一个判断：如果nums1为空，直接去nums2里找中位数；如果nums2为空同理。i等于0意味着A的左半部分没有元素，那么A[i-1]不存在，我们需要把它定义为负无穷，也就是Integer.MIN_VALUE，这样才能保证在取左半部分最大值时不会干扰B[j-1]。i等于m同理，A的右半部分没有元素，A[i]要定义为正无穷，即Integer.MAX_VALUE。

我自己的排查经验是：在代码里加上这些边界判断之后，再拿几个典型用例跑一下，比如nums1为空、nums2只有一个元素、两个数组长度相同、两个数组完全不同区间等情况。这些用例覆盖了绝大部分容易出错的分支。

6.2 死循环问题如何定位

分割法里如果使用向下取整的mid计算方式，很容易出现死循环。这个问题的症状是：程序卡住不退出，或者线程迟迟不结束。排查的方式就是在while循环里临时打印left、right、i、j的值，观察循环是否在某个状态反复横跳。

我见过不少人在面试时写这道题，当场就卡在死循环里，越紧张越找不到问题。这里直接给一个固定套路：只要你的二分是在“找左边界”且满足条件时执行left = mid，mid就一定要向上取整。只要你的二分是标准写法，满足条件时执行right = mid，mid就可以向下取整。牢记这个结论，能规避九成以上的二分死循环问题。

6.3 关于数值溢出的隐患

在计算两个整数平均值时，很多新手会直接写(leftMax + rightMin) / 2。如果leftMax和rightMin都是很大的正数，加法可能溢出。虽然这道题里的元素取值范围是正负10的6次方，加起来不会超过int范围，但作为好习惯，刷题时应该直接用(leftMax + rightMin) / 2.0，如果是更大范围的数值，更安全的写法是leftMax / 2.0 + rightMin / 2.0。

同理，计算totalLeft的时候，(m + n + 1) / 2在m和n很大的时候也可能溢出，更稳妥的写法是m / 2 + n / 2 + (m % 2 + n % 2) / 2，不过这道题不会触发这个极限，你心里有数就行。

7. 面试场景下的作答策略

这道题在面试里出现的频率非常高，而且面试官基本都是层层递进式提问，很少让你一口气写最优解。合理的作答节奏是这样的：

先别急着动手，整理思路，然后直接说：“这道题我首先想到的是合并数组后取中位数，时间复杂度O(m+n)，空间复杂度O(m+n)。但这不符合要求，我们可以优化成双指针归并，把空间复杂度降到O(1)，时间还是O(m+n)。再进一步，可以用二分查找的思路，把它转化成找第K小的元素，这样时间复杂度是O(log(m+n))。如果要用更优的解法，可以利用分割法在较短的数组上二分，做到O(log(min(m+n)))。”

说完这层递进，面试官基本就知道你吃透了。接下来你再选择其中一个实现去写。多数情况下，面试官会要求你直接写最优解，所以分割法的代码一定得手写熟练。

另外一个技巧是：代码写完不要直接交，主动走一遍测试用例。比如nums1 = [1,3]，nums2 = [2]，你手动模拟一下i和j的变化过程，既能检查边界，也能让面试官看到你的调试能力。这比你口头说“我觉得没问题”要有说服力得多。

8. 写在最后

分割法本质上是在两个有序数组之间人为构造一个“左侧整体小于右侧整体”的切分线，这条切分线在不同数组里的位置是关联的。理解了这个关联性，你不但能解决这道题，还能迁移到很多类似的场景中，比如求两个有序数组的第K小值、求两个有序数组的交集、合并K个有序链表等。

我个人刷题的经验是：这道题值得反复刷三遍。第一遍只求看懂，第二遍合上答案自己写，第三遍隔一两周再回来写一次，确保不是短期记忆。第三遍的时候，你会发现之前经常出错的边界条件已经变成了肌肉记忆，这就说明你真的掌握了。

刷题最重要的不是你刷了多少道，而是每一道题你有没有把最优解和推导过程吃透。遇到好的题，宁可用三遍的时间去消化，也不要走马观花地刷十道。这只是题海战术里的一个锚点，把这类核心题掌握好，比盲目追求刷题数量要有用得多。