给定两个大小分别为 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

思路： 有序序列寻找k大值，二分

  1. class Solution:
  2.     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
  3.         """
  4.         可以理解为是寻找第k大的数，
  5.         当总个数是奇数时中位数位置是第n//2+1，偶数时中位数是(n//2+n//2+1)//2
  6.         要实现log时间复杂度，考虑使用二分查找，每次排除不是中位数的一部分
  7.         要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
  8.         """
  9.         def getKthelem(k):
  10.             # 两个数组都从0开始向后索引
  11.             idx1,idx2=0,0
  12.             while True:
  13.                 # 边界条件
  14.                 if idx1==m: # 第一个数组遍历完毕
  15.                     return nums2[idx2+k-1] # 直接返回第二个数组当前的k位置
  16.                 if idx2==n: # 第二个数组遍历完毕
  17.                     return nums1[idx1+k-1] # 直接返回第一个数组当前的k位置
  18.                 if k==1:   # k变为1 说明已经找到第个数，取两个数组中的当前位置较小值
  19.                     return min(nums1[idx1],nums2[idx2])
  20.                 # 一般情况
  21.                 newIdx1=min(idx1+k//2-1,m-1) # 每次往后走k//2-1,注意和边界比较
  22.                 newIdx2=min(idx2+k//2-1,n-1)
  23.                 pivot1,pivot2=nums1[newIdx1],nums2[newIdx2] 
  24.                 if pivot1<=pivot2:  # pivot1和左边的数不满足条件，跳过
  25.                     k-=newIdx1-idx1+1  # k=k-k//2
  26.                     idx1=newIdx1+1
  27.                 else:
  28.                     k-=newIdx2-idx2+1  # k=k-k//2
  29.                     idx2=newIdx2+1
  31.                     m,n=len(nums1),len(nums2)
  32.                     total=m+n
  33.                     if total%2:
  34.                         return getKthelem((total+1)//2)
  35.                     else:
  36.             return (getKthelem(total//2)+getKthelem(total//2+1))/2