4. Median of Two Sorted Arrays

中位数的定义：如果某个有序数组长度是奇数，那么中位数就是最中间的那个数；如果是偶数，那么中位数就是最中间两个数字的平均值。

拓展到两个有序数组的中位数：假设两个有序数组的长度分别为m和n，由于两个数组长度之和m+n的奇偶性不定，因此需要分情况来讨论。对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。

解这道题的关键并不是高超的算法，而是心中要有一副这样的图：
（参考：https://juejin.im/post/5c8c9ec16fb9a049af6e2a0d）

              left side       |  right side 
nums1:   A(0),A(1),...,A(i-1) | A(i),...,A(m-1)
nums2:   B(0),B(1),...,B(j-1) | B(j),...,B(n-1)

我们把两个数组看成一个整体，有一根竖线将其中的元素从中间分开，且左边的部分和右边部分的元素相同（总数为奇数情况下，左边比右边多 1 个元素），那么当 为偶数时，中位数为

当 为奇数时，中位数为

我们都知道，左边的元素为 个，而左右两边元素相同，则

我们可以用 来表示 ，则

所以，该题就变成了，在数组 A 中寻找一个 ，使得 ，且 成立，这两个不等式的含义是，竖线右边最小的数一定不比左边最大的数小，满足该条件，我们就可以说找到了这个竖线。

我们在找 的过程中，难免会碰到 的时候，此时我们需要将 向右移，使 增大，当 右移， 增大的同时， 会减少，即 的值会变小，这样操作 之后，会让我们更接近目标；同理，当 时，我们需要将 向左移。

通过上面的分析，我们最终可以使用二分查找法来寻找这个 值，又由于二分查找的时间复杂度为 ，这种方法可以满足题目的要求。

代码：（参考： https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2567/Python-O(log(min(mn))-solution ）

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1) + len(nums2)
        return self.findKth(nums1, nums2, length//2) if length%2==1 else \
              (self.findKth(nums1, nums2, length//2-1)+self.findKth(nums1, nums2, length//2))/2.0
    
    def findKth(self, A, B, k):
        if len(A) > len(B):
            A, B = B, A
        if not A:
            return B[k]
        if k == len(A) + len(B) - 1:
            return max(A[-1], B[-1])
        i = len(A) // 2
        j = k - i
        if A[i] > B[j]:
            return self.findKth(A[:i], B[j:], i)
        else:
            return self.findKth(A[i:], B[:j], j)

这里要注意的是，在C++中切片操作如 A[i:] 的时间复杂度是 ，但是在Python中这样做的时间复杂度是 。因此上述代码的时间复杂度应为 。