LC：4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

from typing import List
class Solution:
    def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
        m, n = len(A), len(B)
        if m > n:#A是较短的数组
            A, B, m, n = B, A, n, m
        if n == 0:
            raise ValueError

        imin, imax, half_len = 0, m, (m + n + 1) / 2
        while imin <= imax:
            i = int((imin + imax) / 2)#i是A的分割处
            j = int(half_len - i)#j是B的分割处
            print(i)
            print(j)
            print('='*5)
            if i < m and B[j-1] > A[i]:
                # i is too small, must increase it
                imin = i + 1
            elif i > 0 and A[i-1] > B[j]:
                # i is too big, must decrease it
                imax = i - 1
            else:
                # i is perfect#已经确认了边界

                if i == 0: max_of_left = B[j-1]#A全分在了右边
                elif j == 0: max_of_left = A[i-1]#B全分在了右边
                else: max_of_left = max(A[i-1], B[j-1])

                if (m + n) % 2 == 1:#说明当总数是奇数时，左边多分了一个。
                    return max_of_left*1.0

                if i == m: min_of_right = B[j]
                elif j == n: min_of_right = A[i]
                else: min_of_right = min(A[i], B[j])

                return (max_of_left + min_of_right)*1.0 / 2.0
s=Solution()
#print(s.findMedianSortedArrays([1,2],[3,4,5,6,7,8]))#此时i=2,j=2.此时i=m
#print(s.findMedianSortedArrays([9,10],[3,4,5]))#此时i=0
#print(s.findMedianSortedArrays([1,2],[3,4]))#此时j=0,只有在两者长度相等且A在B左边时，才有j=0
print(s.findMedianSortedArrays([3,4],[1,2]))#此时j=m，只有在两者长度相等且A在B右边时，才有j=m

//这道题确实挺难的。