题目
给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log(m+n))。
示例：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
Python
思路：如果题目没有限定时间复杂度为O(log(m+n))，则可以使用O(m+n)的算法解决，用两个指针分别指向两个数组，比较指针元素大小（类似与归并排序），左边长度为（m+n+1）/2次，则为中位数。但是由于这种情况边界条件太多太多，自己写的代码缝缝补补，并不优雅。
中位数：分数组长度为奇数和偶数讨论。
由于时间复杂度的限制和中位数的定义，应该采用二分法。
如图，我们可以了解到1、红线左边和右边的元素个数相等（长度和为偶数），或者左边元素的个数比右边元素的个数多1个。2、红线左边的所有元素的数值<=红线右边的所有元素的数值。
需要确定nums1数组取m1个数的左半边，取nums2数组 m2 =(m+n+1)/2 – m1个数的左半边，即需要找到合适的m1(红色划线)，遂用二分法找m1。
当长度和为偶数时，我们需要找到红色分割线左边的最大值和红丝线右边的最小值即可。
当长度为奇数时，我们只需要找到红色分割线左边最大的值，此值即为中位数。
由于整数除法向下取整，无论长度为奇数还是偶数，都可以写为：m1 + m2 = (m + n + 1) / 2。
①左 边的最大值应该小于右边的最小值。
②在不同数组间，nums1左半边的最大值小于nums2右半边的最小值，同理，nums2左半边的最大值小于nums1右半边的最小值，满足条件则找到了m1，也找到了中位数。
特殊情况：
①
②
Python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1 = len(nums1)
n2 = len(nums2)
if n1 > n2:
return self.findMedianSortedArrays(nums2,nums1) # 使得nums1永远为长度较小的数组
k = (n1 + n2 + 1)//2
left = 0
right = n1
while left < right :
m1 = left +(right - left)//2
m2 = k - m1
if nums1[m1] < nums2[m2-1]: # 如果nums2在分割线左边的数值大于nums1在分割线右边的数值，则说明nums1的分割线小了，应该往右移动。
left = m1 + 1 # 下一轮搜索区间为[m1 + 1, right ]
else:
right = m1 # 下一轮搜索区间为[left, m1]
m1 = left
m2 = k - m1
c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf")) # 分割线左边取最大
if (n1 + n2) % 2 == 1:
return c1
c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf")) # 分割线右边取最小
return (c1 + c2) / 2