4.-median-of-two-sorted-arrays.md

4. Median of Two Sorted Arrays

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        ## 这题真的很难...
        m = len(nums1)
        n = len(nums2)
        if m == 0 and n == 0:
            return 
        
        if m > n:
            ## 更换顺序
            return self.findMedianSortedArrays(nums2, nums1)
        if m == 0:
            return (nums2[n//2] + nums2[(n-1)//2])/2
        
        l, r = 0, m
        while l < r:
            mid1 = (l + r)//2
            mid2 = (m + n + 1)//2 - mid1
            ## 采用左闭右开, 2 的左边最大值大于1 的右边最小 
            if mid1 < m and nums2[mid2-1] > nums1[mid1]:
                l = mid1 + 1
                
            else:
                r = mid1 
                
        ## 永远选取左边, 终止条件是r == l, 但是mid 没有修改        
        mid1 = (l + r)//2
        mid2 = (m + n + 1)//2 - mid1
        ## 数组 1 的左边的边界值
        left1_max = -float('inf') if mid1 == 0 else nums1[mid1-1] # 防止越界
        right1_min =  float('inf') if mid1 == m else nums1[mid1]
        left2_max = -float('inf') if mid2 == 0 else nums2[mid2-1]
        right2_min = float('inf') if mid2 == n else nums2[mid2]
        # print(mid1,nums1,mid2,nums2,r,l)
        # print(left1_max,right1_min,left2_max,right2_min)
                
        if (m + n)%2 == 1:
            return max(left1_max,left2_max)
        else:
            return (max(left1_max,left2_max)+ min(right1_min,right2_min))/2