【LeetCode】0004寻找两个有序数组的中位数

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

代码：

# -*- coding:utf-8 -*-
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """

        def findKthElement(arr1, arr2, k):
            """
            寻找第k个元素
            :param nums1:
            :param nums2:
            :param k:
            :return:
            """
            l1, l2 = len(arr1), len(arr2)
            if l1 > l2:
                return findKthElement(arr2, arr1, k)
            if not arr1:
                return arr2[k - 1]
            if k == 1:
                return min(arr1[0], arr2[0])
            value1 = min(k // 2, l1) - 1
            value2 = min(k // 2, l2) - 1
            if arr1[value1] > arr2[value2]:
                return findKthElement(arr1, arr2[value2 + 1:], k - value2 - 1)
            else:
                return findKthElement(arr1[value1 + 1:], arr2, k - value1 - 1)

        ll1, ll2 = len(nums1), len(nums2)
        left, right = (ll1 + ll2 + 1) // 2, (ll1 + ll2 + 2) // 2
        return (findKthElement(nums1, nums2, left) + findKthElement(nums1, nums2, right)) / 2.0


if __name__ == '__main__':
    nums1 = [1, 3]
    nums2 = [2]
    print(Solution().findMedianSortedArrays(nums1, nums2))

思路：一般这种题做法还是比较简单的，依次遍历两个列表就可以找到中位数，复杂度在O(m+n)，但是这道题限制在log（m+n）的时间内完成，所以需要使用二分查找。我们对每个列表检查第k/2位（k为中位数下标），对于较小的那个列表，我们可以确定前k/2个数都不会是中位数，因此可以将前k/2个数整体删掉继续递归。

边界条件就是其中一个列表被删完了或者需要取最小的元素，只须比较一下两个列表的0号元素输出即可。