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
Note:
---
假设中位数左边有k个数，探析每个数组前k/2的数，剔除较小的那组k/2（所谓剔除便是更新start），接着递归
---
递归运算使问题思路简化：
1. 某个数组为空
2. k=1的情况
3. k不为1的情况：更新start
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def getKth(nums1,start1,end1,nums2,start2,end2,k):
len1 = end1 - start1 + 1
len2 = end2 - start2 + 1
if len1 > len2: return getKth(nums2, start2, end2, nums1, start1, end1, k)
#让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
if len1 == 0: return nums2[start2 + k - 1]
if k == 1: return min(nums1[start1], nums2[start2])
i = start1 + min(len1, k // 2) - 1
j = start2 + min(len2, k // 2) - 1
if nums1[i] > nums2[j]: return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1))
else: return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1))
n = len(nums1)
m = len(nums2)
left = (n + m + 1) // 2
right = (n + m + 2) // 2
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) / 2
#将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k
参考文章：
---
http://windliang.cc/2018/07/18/leetCode-4-Median-of-Two-Sorted-Arrays/
