当前位置：首页 > article >正文

寻找两个正序数组的中位数：分治法与二分查找的结合

article 2025/1/30 13:20:12

寻找两个正序数组的中位数：分治法与二分查找的结合

在算法领域，“寻找两个正序数组的中位数” 是一道经典的高频面试题（LeetCode 第 4 题）。它不仅考察基本的数组操作，还涉及二分查找与分治思想的结合。今天，我们就来深入剖析这道题，并用详细代码讲解其高效解法。

1. 题目分析

给定两个大小分别为 m 和 n 的有序数组 nums1 和 nums2，要求找出它们合并后的中位数。要求算法的时间复杂度为 O(log(m + n))。

1.1 示例

输入：

nums1 = [1, 3]
nums2 = [2]

输出：

2.0

输入：

nums1 = [1, 2]
nums2 = [3, 4]

输出：

2.5

2. 朴素解法：归并再求中位数（O(m + n)）

最直观的方法是将两个有序数组合并，然后直接找到中位数。但由于合并过程需要 O(m + n) 时间，不满足 O(log(m + n)) 的要求，所以我们需要更优的方法。

3. 高效解法：二分查找 + 分治思想

我们可以利用二分查找来优化，核心思路如下：

设 nums1 和 nums2 的总长度为 m + n。
我们的目标是找到第 (m+n)/2 小的数，而不是直接合并数组。
通过二分查找，在 nums1 和 nums2 之间动态调整搜索范围，逐步逼近答案。

4. 代码实现（Python）

def findMedianSortedArrays(nums1, nums2):
    # 确保 nums1 的长度不大于 nums2
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    left, right = 0, m
    median_pos = (m + n + 1) // 2  # 找到中位数的位置
    
    while left <= right:
        partition1 = (left + right) // 2  # 切割 nums1
        partition2 = median_pos - partition1  # 确保左半部分的总元素个数
        
        # 获取切割后的左右元素
        maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        minRight1 = float('inf') if partition1 == m else nums1[partition1]
        
        maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        minRight2 = float('inf') if partition2 == n else nums2[partition2]
        
        # 检查是否找到合适的划分
        if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
            # 如果元素总数是奇数，返回左侧最大值
            if (m + n) % 2 == 1:
                return max(maxLeft1, maxLeft2)
            # 否则返回两个中间值的均值
            return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
        
        # 调整二分查找范围
        elif maxLeft1 > minRight2:
            right = partition1 - 1  # 左移
        else:
            left = partition1 + 1  # 右移

5. 代码解析

核心思想：

通过二分查找，我们试图在 nums1 和 nums2 中找到一个合适的切割，使得两部分满足条件：
- 左半部分的最大值 ≤ 右半部分的最小值
我们使用 partition1 和 partition2 来划分 nums1 和 nums2。
通过调整 partition1 的位置，动态缩小范围，最终找到中位数。