algorithms►leetcode

025-寻找两个正序数组的中位数（二分查找）

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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

在不要求算法复杂度的情况下，个人认为先和并后排序的方法更简单易懂， 有手就行。

1
2
3
4
5
6
7
8
9
10
11
var findMedianSortedArrays = function(nums1, nums2) {
    const combined = nums1.concat(nums2);
    const sortedCombined = combined.sort((a, b) => a - b); // 修正：按数值排序
    
    const length = sortedCombined.length;
    if (length % 2 === 1) {
        return sortedCombined[Math.floor(length / 2)];
    } else {
        return (sortedCombined[(length / 2) - 1] + sortedCombined[length / 2]) / 2;
    }
};

下面是二分法的详细解析， O(log(min(m,n))

终极解答方案：二分查找法求两个有序数组的中位数

1. 核心思想

  • 二分查找短数组：在较短的数组上执行二分查找，确定分割点 partitionX。
  • 自动计算长数组分割点：partitionY = (m + n + 1) / 2 - partitionX。
  • 验证分割有效性：检查左半部分的最大值是否 ≤ 右半部分的最小值。

2. 完整代码

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
var findMedianSortedArrays = function(nums1, nums2) {
    // 确保 nums1 是较短的数组
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }
    const m = nums1.length, n = nums2.length;
    const k = Math.floor((m + n + 1) / 2); // 中位数位置
    
    // 初始化二分查找边界
    let low = 0, high = m;
    
    while (low <= high) {
        // 在 nums1 中尝试分割点 partitionX
        const partitionX = Math.floor((low + high) / 2);
        const partitionY = k - partitionX; // nums2 的分割点
        
        // 处理边界情况（分割点在数组两端）
        const maxLeftX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1];
        const minRightX = (partitionX === m) ? Infinity : nums1[partitionX];
        const maxLeftY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1];
        const minRightY = (partitionY === n) ? Infinity : nums2[partitionY];
        
        // 检查分割是否有效
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            // 计算中位数
            if ((m + n) % 2 === 1) {
                return Math.max(maxLeftX, maxLeftY); // 奇数长度
            } else {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2; // 偶数长度
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1; // 左移分割点
        } else {
            low = partitionX + 1;  // 右移分割点
        }
    }
};

3. 分步图解（示例数组 [1,3,5,7] 和 [2,4,5,6]）

Step 1：初始化
  • nums1 = [1,3,5,7]（m=4），nums2 = [2,4,5,6]（n=4）
  • k = (4+4+1)/2 = 4（中位数位置）
  • low = 0，high = 4
Step 2：第一次迭代（partitionX=2）
nums1分割: [1,3 | 5,7]  (partitionX=2)
nums2分割: [2,4 | 5,6]  (partitionY=4-2=2)

关键值:
- maxLeftX = 3, minRightX = 5
- maxLeftY = 4, minRightY = 5

检查:
3 ≤ 5 (True) 且 4 ≤ 5 (True) → 分割有效！
Step 3：计算中位数
  • 总长度 m+n=8（偶数）：
    • 中位数 = (max(3,4) + min(5,5)) / 2 = (4 + 5) / 2 = 4.5

4. 关键步骤图示

nums1: [1, 3 | 5, 7]
          ↑ partitionX=2
nums2: [2, 4 | 5, 6]
          ↑ partitionY=2

合并后的虚拟数组:
左半部分: [1,3,2,4] → 最大=max(3,4)=4
右半部分: [5,7,5,6] → 最小=min(5,5)=5
中位数 = (4 + 5)/2 = 4.5

5. 复杂度分析

  • 时间复杂度：O(log(min(m,n)))
    仅在短数组上执行二分查找。
  • 空间复杂度：O(1)
    仅使用常数空间。

6. 边界情况处理

情况 处理方式 示例
分割点在 nums1 左端 maxLeftX = -Infinity partitionX=0
分割点在 nums1 右端 minRightX = Infinity partitionX=m
数组为空 直接返回另一数组的中位数 nums1=[], nums2=[1,2]

7. 为什么这样高效？

  • 短数组二分：减少搜索范围。
  • 数学约束：partitionX + partitionY = k 保证左右部分长度平衡。
  • 边界保护：-Infinity 和 Infinity 避免复杂条件判断。

总结

  1. 交换数组：确保 nums1 是较短的数组。
  2. 二分查找：在 nums1 上尝试分割点 partitionX。
  3. 验证分割：检查 maxLeft ≤ minRight。
  4. 调整方向：根据比较结果移动 low 或 high。
  5. 计算中位数：根据奇偶长度返回结果。