给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""
二分查找长度较短数组的切分点。
假设：Lmax1,cut1,Rmin1; Lmax2,cut2,Rmin2
性质：max(Lmax1, Lmax2) < min(Rmin1, Rmin2)
如果 Lmax1 > Rmin2 则在左边区域查找
如果 Lmax2 > Rmin1 则在右边区域查找
"""
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
l1, l2 = len(nums1), len(nums2)
Lmax1 = Rmin1 = Lmax2 = Rmin1 = 0
cut1 = cut2 = 0
"""
l1可能为奇数，此时中位数就是最中间的数，也可能偶数，此时中位数为最中间的两个数的平价数，
为了便于处理，将nums1进行扩充，例如：
[3,5,9,10] -> [3,3,5,5,9,9,10,10,#] ,len=9 此时中位数是num1[4//2]=5和num1[5//2]=9的平均数
[3,5,9] -> [3,3,5,5,9,9,#] ,len=7 此时中位数是num1[3//2]=5和num1[2//2]=5的平均数
即经过扩充处理以后，无论是奇数数组还是偶数数组，计算中位数的方法都是一致的了。
"""
start = 0
end = 2*l1
while start <= end:
cut1 = (start + end)//2
cut2 = l1 + l2 - cut1
Lmax1 = nums1[(cut1 - 1)//2] if cut1!=0 else -float('inf')
Rmin1 = nums1[cut1//2] if cut1!=2*l1 else float('inf')
Lmax2 = nums2[(cut2 - 1)//2] if cut2!=0 else -float('inf')
Rmin2 = nums2[cut2//2] if cut2!=2*l2 else float('inf')
if Lmax1 > Rmin2:
end = cut1 - 1 # LMax1>RMin2，所以cut1要往左移1位，在左半区找，更新上限end=cut1-1
elif Lmax2 > Rmin1:
start = cut1 + 1
else:
break
return (max(Lmax1, Lmax2) + min(Rmin1, Rmin2))/2