两个排序数组的中位数

看时间复杂度的要求，首先想到的就是二分法，但是如何在两个数组上进行二分呢？我们把这个问题分解一下，先求解在两个有序数组中查找整体第k大的数，如果m+n是偶数，则调用两次子过程求平均，如果是奇数，调用一次。我们这样来找第k大的数：

假设m和n都大于k/2，则比较nums1[k/2 - 1]和nums2[k - k/2 - 1]
如果前者比较大，则可以扔掉nums2[k - k/2 - 1]之前的k/2个数
如果后者比较大，则可以扔掉nums1[k/2 - 1]之前的k/2个数
如果相等，说明第k个数已经找到
如果m和n中有一个小于k/2呢？假设n比m小，那么就取min(k/2, n)和k - min(k/2, n)作为比较的下标值。
时间复杂度是O(log(k))。在写代码的过程中，边界判断是非常容易出错的，要反复练习。

def findMedianSortedArrays(self, A, B):
        n = len(A) + len(B)
        if n % 2 == 1:
            return self.findKth(A, B, n / 2 + 1)
        else:
            smaller = self.findKth(A, B, n / 2)
            bigger = self.findKth(A, B, n / 2 + 1)
            return (smaller + bigger) / 2.0

    def findKth(self, A, B, k):
        if len(A) == 0:
            return B[k - 1]
        if len(B) == 0:
            return A[k - 1]
        if k == 1:
            return min(A[0], B[0])
        
        a = A[k / 2 - 1] if len(A) >= k / 2 else None
        b = B[k / 2 - 1] if len(B) >= k / 2 else None
        
        if b is None or (a is not None and a < b):
            return self.findKth(A[k / 2:], B, k - k / 2)
        return self.findKth(A, B[k / 2:], k - k / 2)