4. Median of Two Sorted Arrays

思路见:https://leetcode.com/articles/median-of-two-sorted-arrays/

class Solution:  
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums2) < len(nums1):
            tmp = nums1
            nums1 = nums2
            nums2 = tmp

        m = len(nums1)
        n = len(nums2)

        imax = m
        imin = 0

        while imin <= imax:
            i = (imax + imin) // 2
            j = (m + n + 1) // 2 - i

            if i > imin and nums1[i-1] > nums2[j]:
                imax = i - 1
            elif i < imax and nums1[i] < nums2[j-1]:
                imin = i + 1
            else:
                if i == 0:
                    leftmax = nums2[j-1]
                elif j == 0:
                    leftmax = nums1[i-1]
                else:
                    leftmax = max(nums1[i-1], nums2[j-1])

                if (m + n) % 2:
                    return leftmax

                if i == m:
                    rightmin = nums2[j]
                elif j == n:
                    rightmin = nums1[i]
                else:
                    rightmin = min(nums1[i], nums2[j])

                return (leftmax + rightmin ) / 2.0