一、文章标题

LeetCode 004. 寻找两个正序数组的中位数 - 二分切分与分治详解

二、文章内容

1. 题目概述

题目描述：给定两个已按非降序排列的整数数组 nums1、nums2，设它们长度分别为 m 和 n，要求返回这两个数组合并后有序序列的中位数。整体期望时间复杂度为 O(log(m+n))。当总长度为偶数时，中位数为中间两个数的平均值（返回 double）。数组可能为空，但不会同时为空（若实现中遇到同时为空需返回默认值）。
原题链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/
难度等级：Hard
相关标签：数组、二分查找、分治、双指针

2. 文章目录

问题分析：
- 输入：两个已排序的整型数组 nums1、nums2。
- 输出：合并后序列的中位数（double）。
- 中位数定义：
  - 若 m+n 为奇数，中位数为第 (m+n)/2（0 基）处的元素。
  - 若 m+n 为偶数，中位数为第 (m+n)/2 - 1 与 (m+n)/2 两个元素均值。
核心难点：
- 在不真正合并数组的前提下，以 O(log(m+n)) 时间找到中位数。
- 复杂边界处理：空数组、分割端点在数组两侧、奇偶长度处理、整型转 double。
解题方向：
1. 线性合并/扫描到中位数位置（O(m+n)，实现直观，作为兜底）。
2. 分治/找第 k 小（每轮丢弃 k/2 个元素，O(log(m+n))）。
3. 二分切分（只对较短数组二分，构造左右两半满足有序关系，O(log(min(m,n)))，最优）。

4. 算法详解

解法一：双指针线性扫描到中位数

算法原理

核心思想：像归并排序的合并过程一样，用两根指针从头扫描两个有序数组，不必真的合并，只需走到中位数所在下标就停止。
适用场景：当不强求 O(log(m+n))、或用作对拍与兜底实现时非常好用。

具体实现

步骤1：准备两个指针 i、j 指向 nums1、nums2 开始位置，准备计数 idx 表示当前合并到的下标。
步骤2：每次取两个指针中较小的元素作为“当前值”，并向前推进对应指针，直到走到右侧中位数下标 mid2。
步骤3：根据总长度奇偶，返回 curr 或 (prev+curr)/2.0。

复杂度分析

时间复杂度：O(m+n)，最坏需要扫描完所有元素。
空间复杂度：O(1)，只用到常数额外变量。

Java代码实现

class Solution {/*** 线性扫描到中位数位置的解法（O(m+n)）。* 注意：为讲解清晰，方法名与最优解区分；在 LeetCode 提交时可将最优解方法名改为题目要求的方法名。*/public double findMedianSortedArraysLinear(int[] nums1, int[] nums2) {// 将 null 视作空数组，避免空指针if (nums1 == null) nums1 = new int[0];if (nums2 == null) nums2 = new int[0];int m = nums1.length, n = nums2.length;int total = m + n;// 题目一般保证不会同时为空；为健壮性，这里返回默认值 0.0if (total == 0) {return 0.0;}// 左、右中位数的目标下标（0 基）int mid1 = (total - 1) / 2; // 左中位数int mid2 = total / 2;       // 右中位数int i = 0, j = 0;  // 两个数组的扫描指针int idx = -1;      // 已经“取出”的元素个数 - 1int prev = 0;      // 上一个取出的值（用于偶数总长度）int curr = 0;      // 当前取出的值// 扫描直到到达右中位数位置while (idx < mid2) {prev = curr; // 记录上一个值// 取较小值推进（当某一数组用尽时，取另一数组）if (i < m && (j >= n || nums1[i] <= nums2[j])) {curr = nums1[i++];} else if (j < n) {curr = nums2[j++];}idx++;}// 奇偶分别处理if ((total & 1) == 1) {return curr; // 奇数长度，中位数就是当前值} else {return (prev + curr) / 2.0; // 偶数长度，取均值}}
}

解法二：二分切分（最优）

算法原理

基本思想：只对较短的数组进行二分，在两个数组上找到一个“切分点对” (i, j)，使得：
- 左半部分长度等于右半部分长度（或只多 1），即 i + j = (m + n + 1) / 2；
- 左半最大值 ≤ 右半最小值，即 max(A[i-1], B[j-1]) ≤ min(A[i], B[j])。
一旦上述条件成立：
- 若总长度为奇数，中位数是左半最大值；
- 若为偶数，中位数是左半最大值与右半最小值的平均。
适用场景：追求最优时间复杂度，面试高频且边界清晰的标准解。

具体实现

步骤1：确保对更短的数组二分，令 A 为短数组，B 为长数组。
步骤2：在 A 的 [0…m] 区间二分 i，令 j = (m+n+1)/2 - i。
步骤3：检查是否满足分割条件；若 A[i-1] > B[j]，说明 i 偏大，收缩右边；若 B[j-1] > A[i]，说明 i 偏小，收缩左边；否则命中答案。

复杂度分析

时间复杂度：O(log(min(m,n)))，只在短数组长度范围内二分。
空间复杂度：O(1)，常数额外空间。

Java代码实现

class Solution {/*** 最优解：二分切分，时间复杂度 O(log(min(m,n)))，空间 O(1)。* 若两个数组都为空则返回 0.0 作为默认值，避免抛异常。*/public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 将 null 视作空数组，避免空指针if (nums1 == null) nums1 = new int[0];if (nums2 == null) nums2 = new int[0];// 始终让 A 为较短数组，B 为较长数组int[] A = nums1.length <= nums2.length ? nums1 : nums2;int[] B = (A == nums1) ? nums2 : nums1;int m = A.length, n = B.length;// 边界：两个都为空，返回默认值if (m + n == 0) {return 0.0;}int left = 0, right = m; // 在 A 的切分位置范围 [0..m] 上二分int half = (m + n + 1) / 2; // 左半部分应包含的元素个数while (left <= right) {int i = left + (right - left) / 2; // A 的切分点int j = half - i;                  // B 的切分点，使得左半长度满足要求// 处理边界元素，越界时使用极小/极大的“哨兵”思想（用比较逻辑避免实际越界）int Aleft  = (i == 0) ? Integer.MIN_VALUE : A[i - 1];int Aright = (i == m) ? Integer.MAX_VALUE : A[i];int Bleft  = (j == 0) ? Integer.MIN_VALUE : B[j - 1];int Bright = (j == n) ? Integer.MAX_VALUE : B[j];// 检查是否满足切分正确：左边最大 <= 右边最小if (Aleft <= Bright && Bleft <= Aright) {// 命中：根据奇偶直接计算中位数if (((m + n) & 1) == 1) {// 奇数：中位数是左边最大值int leftMax = Math.max(Aleft, Bleft);return (double) leftMax;} else {// 偶数：中位数是 左边最大 与 右边最小 的均值int leftMax = Math.max(Aleft, Bleft);int rightMin = Math.min(Aright, Bright);return (leftMax + rightMin) / 2.0;}} else if (Aleft > Bright) {// A 的左边太大，i 需要左移right = i - 1;} else {// Bleft > Aright，i 需要右移left = i + 1;}}// 理论上一定能在循环内返回；为健壮性返回默认值return 0.0;}
}

5. 解法对比与总结

解法	时间复杂度	空间复杂度	优点	缺点	适用场景
双指针线性扫描到中位数	O(m+n)	O(1)	实现直观、边界简单、易调试	不满足题目要求的对数级时间	数据量不大、或作为兜底与对拍
二分切分（最优）	O(log(min(m,n)))	O(1)	满足最优时间、无需额外空间、思路标准	边界处理细节较多，上手需练习	面试高频、追求最优性能