题目
给定两个大小分别为
m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为
O(log (m+n)) 。示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
106 <= nums1[i], nums2[i] <= 106
解析
这题难点是时间复杂度。根据时间复杂度是
O(log (m+n)) ，采用二分法。class Solution(object): def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ if (len(nums1) + len(nums2)) % 2 == 1: return float(self.findMaxK(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1)) else: return float((self.findMaxK(nums1, nums2, (len(nums1) + len(nums2)) / 2 ) + self.findMaxK(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1)) / 2.0) def findMaxK(self, nums1, nums2, k): if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 if len(nums1) == 0: return nums2[k - 1] if k == 1: if nums1[0] < nums2[0]: return nums1[0] else: return nums2[0] idx = min(k/2 - 1, len(nums1) - 1) if nums1[idx] <= nums2[k - idx - 2]: return self.findMaxK(nums1[idx + 1 :], nums2, k - idx - 1) else: return self.findMaxK(nums1, nums2[k - idx - 1 :], idx + 1)
