4.寻找两个有序数组的中位数(hard)

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

• show the code:

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        l = len(nums1) + len(nums2)
        return self.findkth(nums1,nums2,l//2) if l%2==1 else (self.findkth(nums1,nums2,l//2-1)+self.findkth(nums1,nums2,l//2))/2.
    def findkth(self,a,b,k):
        if not a:
            return b[k]
        if not b:
            return a[k]
        ia,ib = len(a)//2,len(b)//2
        na,nb = a[ia],b[ib]
        #如果a b长度都为奇数，则会出现ia+ib<k
        if ia+ib < k:
            if na > nb:
                return self.findkth(a,b[ib+1:],k-ib-1)
            else:
                return self.findkth(a[ia+1:],b,k-ia-1)
        else:
            if na > nb:
                return self.findkth(a[:ia],b,k)
            else:
                return self.findkth(a,b[:ib],k)

• 算法的关键是要实现一个函数findkth，他可以从两个排序数组中取出第k个数，
• 这里由于每次都是对长为m和n的数组取半，所以时间复杂度为O(log(m+n))
• 一直没太看懂关于代码中的if判断部分的逻辑，leetcode上这个人解释的还可以：

if ia + ib < k: means the k-th element still exist in some larger part of the array
if na < nb => la < na < nb: solution can't exist in la
if na > nb => lb < nb < na: solution can't exist in lb
since we are deleted some smaller part, original we are seeking for the k-th, now we are seeking for the k - (len(smaller part)) th in the remaining two array
if ia + ib > k: means the k-th element still exist in some smaller part of the array
if na < nb => na < nb < rb: solution can't exist in rb
if na > nb => nb < na < ra: solution can't exist in ra
since we are deleted some larger part, we are still finding the k-th element in the array

• 其实ia + ib < k的情况就是k比较大，说明第k个数肯定在两个数组后半部分，相反，k比较小的情况就是在前半部分。
• 在判断了k应该在left部分还是right部分后，进一步比较两个数组中位数的大小，来决定是否抛弃某一部分：抛弃有四种情况—aleft,bleft,aright,bright。

这个题算是比较难的题了，主要是要求复杂度为O(log(m+n))，不然用普通方法是可以做出O(m+n)的，看到log要马上想到二分法，除以半就完事了！