题目:寻找两个正序数组的中位数

给定两个大小分别为 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. 计算中位数：当找到合适的分割点后，根据合并后数组的长度是奇数还是偶数来计算中位数。

三、Python 代码实现

下面是实现寻找两个正序数组中位数功能的代码：

def find_median_sorted_arrays(nums1, nums2):
    # 确保 nums1 是较短的数组，这样可以减少二分查找的范围
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    # 二分查找的左右边界
    left, right = 0, m
    half_len = (m + n + 1) // 2

    while left <= right:
        # 计算 nums1 的分割点
        partition1 = (left + right) // 2
        # 计算 nums2 的分割点
        partition2 = half_len - partition1

        # 计算 nums1 左边部分的最大值
        max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        # 计算 nums1 右边部分的最小值
        min_right1 = float('inf') if partition1 == m else nums1[partition1]

        # 计算 nums2 左边部分的最大值
        max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        # 计算 nums2 右边部分的最小值
        min_right2 = float('inf') if partition2 == n else nums2[partition2]

        # 检查分割点是否满足条件
        if max_left1 <= min_right2 and max_left2 <= min_right1:
            # 如果合并后数组的长度是奇数，中位数就是左边部分的最大值
            if (m + n) % 2 == 1:
                return max(max_left1, max_left2)
            # 如果合并后数组的长度是偶数，中位数是左边部分的最大值和右边部分的最小值的平均值
            else:
                return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
        # 如果分割点不满足条件，调整二分查找的范围
        elif max_left1 > min_right2:
            right = partition1 - 1
        else:
            left = partition1 + 1

    # 如果代码执行到这里，说明输入的数组不是有序的，抛出异常
    raise ValueError("Input arrays are not sorted.")


# 测试示例
nums1 = [1, 3]
nums2 = [2]
print(find_median_sorted_arrays(nums1, nums2))  # 输出: 2.0

nums1 = [1, 2]
nums2 = [3, 4]
print(find_median_sorted_arrays(nums1, nums2))  # 输出: 2.5

四、复杂度分析

• 时间复杂度：由于使用了二分查找，且每次查找都会将搜索范围缩小一半，所以时间复杂度为 ，满足 的要求。
• 空间复杂度：只使用了常数级的额外空间，因此空间复杂度为 。

通过上述分析和代码实现，我们可以高效地找出两个正序数组的中位数。