LC 0004 [H] Median of Two Sorted Arrays - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=q6IEA26hvXc&ab_channel=NeetCode

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2
        
        # O( log(min(n, m)) )
        # A should be smaller
        if len(B) < len(A):
            A, B = B, A
            
        l, r = 0, len(A) - 1
        
        while True:
            i = (l + r) // 2 # A
            j = half - i - 2 # B, -2 for the 2 infinity sides
            
            Aleft = A[i] if i >= 0 else float('-inf')
            Aright = A[i+1] if (i+1) < len(A) else float('inf')
            Bleft = B[j] if j >= 0 else float('-inf')
            Bright = B[j+1] if (j+1) < len(B) else float('inf')
            
            # partition is correct
            if Aleft <= Bright and Bleft <= Aright:
                # odd
                if total % 2:
                    return min(Aright, Bright)
                # even
                else:
                    return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            elif Aleft < Bright:
                l = i + 1
            elif Aleft > Bright:
                r = i - 1