004_median2array.py

#it didnt satisfy the time complexity log(m+n)
class Solution:
    def findMedianSortedArrays_myway(self, nums1, nums2):
        merge_num = sorted(nums1 + nums2)
        n = len(merge_num)
        if n % 2 != 0:
            return merge_num[n//2]
        else:
            return sum(merge_num[n // 2 - 1 : n // 2 + 1])/2.0

    def findMedianSortedArrays(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m
        if n == 0:
            raise ValueError
        
        imin, imax, half_len = 0, m, (m + n + 1) // 2
        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i
            if i < m and nums2[j - 1] > nums1[i]:
                imin = i + 1
            elif i > 0 and nums1[i - 1] > nums2[j]:
                imax = i - 1
            else:
                if i == 0: max_of_left = nums2[j - 1]
                elif j == 0: max_of_left = nums1[i - 1]
                else: max_of_left = max(nums1[i - 1], nums2[j - 1])

                if (m + n) % 2 == 1:
                    return max_of_left
                
                if  i == m: min_of_right = nums2[j]
                elif j == n: min_of_right = nums1[i]
                else: min_of_right = min(nums1[i], nums2[j])

                return (max_of_left + min_of_right) / 2.0

        


print(Solution().findMedianSortedArrays(nums1 = [1,3], nums2 = [2]))
print(Solution().findMedianSortedArrays(nums1 = [0,0], nums2 = [0,0]))
print(Solution().findMedianSortedArrays(nums1 = [1,2], nums2 = [3,4]))
print(Solution().findMedianSortedArrays(nums1 = [], nums2 = [1]))
print(Solution().findMedianSortedArrays(nums1 = [2], nums2 = []))