Description:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Notes:

1.调换顺序让nums1尺寸小于nums2
2.考虑nums1为空

3.binary search，设定l和r
4.nums1里设定了搜索点k1 = l+(r-l)//2，那么k2 = total_num//2 - k1
5.对比nums1[k1-1]、nums1[k1]、nums2[k2]、nums2[k2-1]，左边超出边界设定为-∞，右边设定超出边界为+无穷大

6.maxLeftX > minRightY情况下，r = min(k1,r-1)。没有r-1的话可能会因为k1==r而无限循环。同理maxLeftY > minRightX情况下，l = max(k1,l+1)。
6.上面错了，应该写
如果右边界太大，则r = k1-1
如果左边界太小，则 l = k1+1

7.循环出去的条件是 l<=r，而不是l<r。否则过不了
print(s.findMedianSortedArrays([1],[2,3]))

8.binary search取中位数细节：

    def median(self,nums):
        if len(nums)%2 == 1:
            return nums[len(nums)//2]
        else:
            return (nums[len(nums)//2] + nums[len(nums)//2 - 1])/2

Finally Solution:

import math
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2,nums1)
        if len(nums1) == 0:
            return self.median(nums2)
            
        total_num = len(nums1) + len(nums2)
        split_point = total_num//2
        
        l,r = 0,len(nums1)
        
        while (l <= r):
            k1 = l+(r-l)//2
            k2 = split_point - k1
            
            maxLeftX = nums1[k1-1] if k1 > 0 else -math.inf
            minRightX = nums1[k1] if k1 < len(nums1) else math.inf
            maxLeftY = nums2[k2-1] if k2 > 0 else -math.inf
            minRightY = nums2[k2] if k2 < len(nums2) else math.inf
            
            if maxLeftX > minRightY:
                r = k1-1
            elif maxLeftY > minRightX:
                l = k1+1
            else:
                break
        
        if total_num%2 == 1:
            return min(minRightY,minRightX)
        else:
            return (max(maxLeftX,maxLeftY) + min(minRightY,minRightX))/2
        
    def median(self,nums):
        if len(nums)%2 == 1:
            return nums[len(nums)//2]
        else:
            return (nums[len(nums)//2] + nums[len(nums)//2 - 1])/2