A Hard binary search problem

4. Median of Two Sorted Arrays

Python Solution

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        if m > n:return self.findMedianSortedArrays(nums2, nums1)
        l, r = 0, m
        half = (n + m)//2
        while l <= r:
            i = (l + r) // 2
            j = half - i
            # magic to conquer the edge cases
            max_left1 = -float('inf') if i == 0 else nums1[i - 1]
            min_right1 = float('inf') if i == m else nums1[i]
            max_left2 = -float('inf') if j == 0 else nums2[j - 1]
            min_right2 = float('inf') if j == n else nums2[j]
            if max_left1 > min_right2:
                # i is too large
                r = i - 1
                continue
            elif  max_left2 > min_right1:
                # i is too small
                l = i + 1
                continue
            else:
                # i is perfect
                if (n + m) % 2 == 0:
                    return (max(max_left1, max_left2) + min(min_right1, min_right2))/2
                else:
                    return min(min_right1, min_right2)

Thanks for reading.