给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1：

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

则中位数是 2.0

示例 2：

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

则中位数是 (2 + 3)/2 = 2.5

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        # 使 num1 为更短的列表，搜索更快
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        
        left_total = (m+n+1)//2    # 左边总共需要的元素个数
        
        # 二分查找 nums1 的划分边界 i
        left, right = 0, m
        while left < right:
            i = (left+right)//2     # 确定nums1左序列个数
            j = left_total-i        # 则可确定nums2左序列个数  
            
            # 若nums2左序列的最大值大于nums1右序列的最小值，则往右区域查找，否则往左区域查找
            if nums2[j-1] > nums1[i]:
                left = i+1
            else:
                right = i
        i, j = left, left_total-left  # 确定划分边界 i，j
        
        # 边界控制
        nums1_left_max = float('-inf') if i==0 else nums1[i-1]
        nums2_left_max = float('-inf') if j==0 else nums2[j-1]
        nums1_right_min = float('inf') if i==m else nums1[i]
        nums2_right_min = float('inf') if j==n else nums2[j]
        
        if (m+n)%2 == 0:
            return (max(nums1_left_max, nums2_left_max)+min(nums1_right_min,nums2_right_min))/2
        else:
            return max(nums1_left_max, nums2_left_max)

test = Solution()
nums1_li = [[1, 3], [1, 2], [0,0]]
nums2_li = [[2], [3, 4], [0,0]]
for nums1, nums2 in zip(nums1_li, nums2_li):
    print(test.findMedianSortedArrays(nums1, nums2))

2
2.5
0.0