本文概览：本文讲解寻找两个正序数组的中位数的核心思路：不需要合并数组，只需要在较短数组上二分切割，保证左边元素都小于右边元素

一、题目

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

二、题目分析

1. 题目要求

题目给定两个正序数组 nums1 和 nums2，要求找到这两个数组的中位数，时间复杂度 O(log(m+n))。

中位数的定义：

  • 如果数组长度是奇数，中位数是中间那个数
  • 如果数组长度是偶数，中位数是中间两个数的平均值

比如 [1, 2, 3, 4, 5] 的中位数是 3，[1, 2, 3, 4] 的中位数是 (2+3)/2 = 2.5。

2. 普通做法：双指针合并

最直观的思路：把两个数组合并成一个有序数组，然后直接找中位数。

怎么合并？用双指针，一个指针指向 nums1，一个指向 nums2，每次比较两个指针指向的元素，谁小谁就往后移，直到遍历到中间位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
nums1 = [1, 3, 5, 7]
nums2 = [2, 4, 6]

合并过程：
1 < 2 → 取 1，nums1 指针后移
3 > 2 → 取 2，nums2 指针后移
3 < 4 → 取 3，nums1 指针后移
5 > 4 → 取 4，nums2 指针后移
5 < 6 → 取 5，nums1 指针后移
7 > 6 → 取 6，nums2 指针后移
取 7

合并结果：[1, 2, 3, 4, 5, 6, 7]
中位数：第 4 个元素 = 4

时间复杂度：O(m+n)，因为需要遍历到中间位置。

问题：不符合题目要求的 O(log(m+n))。

3. 优化思路：从 O(m+n) 到 O(log(m+n))

看到 O(log n) 的时间复杂度，第一反应就是二分查找。

但怎么二分？两个数组，好像找不到切入点。

关键观察：我们不需要排序数组，只需要找到符合要求的前 mid 项元素。

比如 nums1 = [1, 3, 5, 7] 和 nums2 = [2, 4, 6]，合并后是 [1, 2, 3, 4, 5, 6, 7]，总长度 7，mid = (7+1)/2 = 4。

我们不需要完全合并，只需要从两个数组中各取一部分，组成前 mid 项元素：

  • 从 nums1 取前 2 个元素 [1, 3]
  • 从 nums2 取前 2 个元素 [2, 4]
  • 组成前 mid 项：[1, 2, 3, 4]

奇数情况：前 mid 项的最大值就是中位数，即 max(1, 2, 3, 4) = 4。

偶数情况：前 mid 项的最大值 + 后 (n+m-mid) 项的最小值，相加除以 2。

核心思路：找到正确的切割位置，让前 mid 项元素符合要求（即前 mid 项的所有元素都小于后 (n+m-mid) 项的所有元素）。

4. 切割的概念

在数组 nums1 上切一刀（位置 cut1），把 nums1 分成左右两部分。在 nums2 上也切一刀（位置 cut2），保证左边总共有 mid 个元素，即 cut1 + cut2 = mid。

1
2
3
4
5
6
7
8
nums1: [1, 3 | 5, 7]
         左  | 右

nums2: [2, 4 | 6]
         左  | 右

左半部分：[1, 3] + [2, 4] = [1, 2, 3, 4]
右半部分：[5, 7] + [6] = [5, 6, 7]

5. 怎么判断切割正确？

切割后，左半部分包含 nums1 的前 cut1 个和 nums2 的前 cut2 个，右半部分包含 nums1 的后 m-cut1 个和 nums2 的后 n-cut2 个。

要保证左半部分所有元素都小于右半部分，只需要：

  • nums1 左边最大值 <= nums2 右边最小值（nums1[cut1-1] <= nums2[cut2]）
  • nums2 左边最大值 <= nums1 右边最小值（nums2[cut2-1] <= nums1[cut1]）

因为 nums1 左边本身是递增的，nums2 左边也是递增的，所以只需要判断边界。

6. 怎么找到正确的切割位置？

对切割位置 cut1 使用二分查找！这就是 O(log n) 的来源。

在 nums1 上二分切割位置 cut1，对于每个 cut1，计算 cut2 = mid - cut1，然后判断切割是否正确。如果不正确，根据判断结果调整 cut1 的位置。

思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    // 确保nums1的长度小于等于nums2的长度
    if (m > n) {
        return findMedianSortedArrays(nums2, nums1);
    }

    // 计算中间位
    int mid = (m + n + 1) / 2;
    // 初始化左右指针,切割线范围为0-m
    int left = 0;
    int right = m;
    while (left <= right) {
        // 短数组的切割线位置
        int cut1 = left + (right - left) / 2;
        // 长数组的切割线位置
        int cut2 = mid - cut1;
        // A数组左部分最大值
        int aLeft = cut1 == 0 ? Integer.MIN_VALUE : nums1[cut1 - 1];
        // A数组右部分最小值
        int aRight = cut1 == m ? Integer.MAX_VALUE : nums1[cut1];
        // B数组左部分最大值
        int bLeft = cut2 == 0 ? Integer.MIN_VALUE : nums2[cut2 - 1];
        // B数组右部分最小值
        int bRight = cut2 == n ? Integer.MAX_VALUE : nums2[cut2];
        if (aLeft <= bRight && bLeft <= aRight) {
            // 如果切割线位置正确,则返回中位数
            if ((m + n) % 2 == 1) {
                // 奇数：中位数 = 左半部分最大值
                return Math.max(aLeft, bLeft);
            }else {
                // 偶数：中位数 = (左半部分最大值 + 右半部分最小值) / 2
                return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
            }
        }else if(aLeft > bRight) {
            // A数组切割线位置偏大,需要向左移动
            right = cut1 - 1;
        }else {
            // B数组切割线位置偏大,则A数组切割线位置偏小,需要向右移动
            left = cut1 + 1;
        }
    }
    return 0;
}

思路简要说明：

  1. 保证 nums1 是较短数组：这样在 nums1 上二分，避免 nums2 切割位置越界
  2. 切割位置：在 nums1 上切 cut1 刀，在 nums2 上切 cut2 = mid - cut1 刀，保证左边总共有 half 个元素
  3. 判断条件：aLeft <= bRight 且 bLeft <= aRight
  4. 二分调整：如果 aLeft > bRight，说明 A 数组切割线位置偏大，左移；否则右移

三、思路详解

第一步：为什么不需要合并数组

以 A = [1, 3, 5, 7] 和 B = [2, 4, 6] 为例：

合并后：[1, 2, 3, 4, 5, 6, 7]，中位数是第 4 个元素 4。

但我们只需要从 A 取前 2 个 [1, 3]，从 B 取前 2 个 [2, 4]，组成左半部分 [1, 2, 3, 4]，最大值就是 4。

关键：不需要完全合并，只需要找到正确的切割位置，让左半部分包含 mid 个元素，且左半部分的所有元素都小于右半部分。

第二步：切割的概念

在数组 A 上切一刀，位置 cut1 表示 A 的前 cut1 个元素属于左半部分，剩下的属于右半部分。

比如 A = [1, 3, 5, 7]，cut1 = 2 表示：

  • 左半部分：[1, 3]
  • 右半部分：[5, 7]

同理，在 B 上切 cut2 = mid - cut1 刀。

第三步：为什么要在较短数组上切

假设 A 长度 4，B 长度 3，mid = (4+3+1)/2 = 4。

如果在 A 上切 cut1 = 0，那么 B 需要切 cut2 = 4，但 B 长度只有 3，越界了。

所以要在较短数组上切，保证 cut2 不会越界。

第四步：判断切割是否正确

切割后，左半部分包含：

  • A 的前 cut1 个元素：A[0...cut1-1]
  • B 的前 cut2 个元素：B[0...cut2-1]

右半部分包含：

  • A 的后 m-cut1 个元素：A[cut1...m-1]
  • B 的后 n-cut2 个元素：B[cut2...n-1]

要保证左半部分所有元素都小于右半部分，只需要：

  • A[cut1-1] <= B[cut2]（A 左边最大值 <= B 右边最小值）
  • B[cut2-1] <= A[cut1]（B 左边最大值 <= A 右边最小值）

因为 A 左边本身是递增的，B 左边也是递增的，所以只需要判断边界。

第五步：二分调整

如果 A[cut1-1] > B[cut2]，说明 A 左边太大，需要左移切割位置（减小 cut1）。

否则，需要右移切割位置（增大 cut1）。

完整执行过程（图解）

以 A = [1, 3, 5, 7] 和 B = [2, 4, 6] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
m = 4, n = 3, mid = (4+3+1)/2 = 4

初始：left = 0, right = 4

第 1 轮：
  cut1 = 2, cut2 = 2
  
  A: [1, 3 | 5, 7]
      左  | 右
  
  B: [2, 4 | 6]
      左  | 右
  
  A 左边最大值 = 3, A 右边最小值 = 5
  B 左边最大值 = 4, B 右边最小值 = 6
  
  判断：3 <= 6 ✓ 且 4 <= 5 ✓
  找到正确的切割位置！
  
  总元素个数 7 是奇数，中位数 = max(3, 4) = 4 ✓

再举一个偶数个元素的例子，A = [1, 2] 和 B = [3, 4]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
m = 2, n = 2, mid = (2+2+1)/2 = 2

初始：left = 0, right = 2

第 1 轮：
  cut1 = 1, cut2 = 1
  
  A: [1 | 2]
     左 | 右
  
  B: [3 | 4]
     左 | 右
  
  A 左边最大值 = 1, A 右边最小值 = 2
  B 左边最大值 = 3, B 右边最小值 = 4
  
  判断：1 <= 4 ✓ 但 3 <= 2 ✗
  B 左边太大，需要右移 cut1
  
  left = cut1 + 1 = 2

第 2 轮：
  cut1 = 2, cut2 = 0
  
  A: [1, 2 |]
       左  |
  
  B: [| 3, 4]
         | 右
  
  A 左边最大值 = 2, A 右边最小值 = ∞
  B 左边最大值 = -∞, B 右边最小值 = 3
  
  判断：2 <= 3 ✓ 且 -∞ <= ∞ ✓
  找到正确的切割位置！
  
  总元素个数 4 是偶数，中位数 = (max(2, -∞) + min(∞, 3)) / 2 = (2 + 3) / 2 = 2.5 ✓

四、总结

寻找两个正序数组的中位数的核心思路：

  1. 不需要合并数组：只需要找到正确的切割位置
  2. 在较短数组上二分：避免越界
  3. 切割位置 cut1 和 cut2：保证左边总共有 mid 个元素
  4. 判断条件：A[cut1-1] <= B[cut2] 且 B[cut2-1] <= A[cut1]
  5. 二分调整：根据判断结果左移或右移

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