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

给定两个大小分别为 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

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

题解：
要找到两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n))，我们可以使用二分查找的方法。具体思路是将问题转化为在两个数组中寻找第 k 小的元素
用markdown格式重新输出一下题目

题解：
要找到两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n))，我们可以使用二分查找的方法。具体思路是将问题转化为在两个数组中寻找第 k 小的元素。

算法思路

1. 中位数的定义：

   • 如果两个数组的总长度是奇数，中位数就是第 (m+n)/2 + 1 小的元素。
   • 如果总长度是偶数，中位数是第 (m+n)/2 小的元素和第 (m+n)/2 + 1 小的元素的平均值。

2. 二分查找：

   • 我们需要在两个数组中找到第 k 小的元素。
   • 每次比较两个数组的第 k/2 个元素，较小的那个数组的前 k/2 个元素不可能是第 k 小的元素，因此可以排除这些元素。
   • 递归地在剩下的部分中寻找第 k - k/2 小的元素。

代码实现

Python

def findMedianSortedArrays(nums1, nums2):
    def findKthElement(k):
        index1, index2 = 0, 0
        while True:
            # 如果 nums1 已经全部排除，直接返回 nums2 中的第 k 小元素
            if index1 == m:
                return nums2[index2 + k - 1]
            # 如果 nums2 已经全部排除，直接返回 nums1 中的第 k 小元素
            if index2 == n:
                return nums1[index1 + k - 1]
            # 如果 k == 1，返回两个数组当前元素中较小的一个
            if k == 1:
                return min(nums1[index1], nums2[index2])

            # 计算新的索引
            new_index1 = min(index1 + k // 2 - 1, m - 1)
            new_index2 = min(index2 + k // 2 - 1, n - 1)
            pivot1, pivot2 = nums1[new_index1], nums2[new_index2]
            # 比较两个数组的第 k/2 个元素
            if pivot1 <= pivot2:
                k -= new_index1 - index1 + 1
                index1 = new_index1 + 1
            else:
                k -= new_index2 - index2 + 1
                index2 = new_index2 + 1

    m, n = len(nums1), len(nums2)
    total_length = m + n
    if total_length % 2 == 1:
        return findKthElement((total_length + 1)