题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。

题解

由于时间复杂度要求，所以要用二分查找（看到log与有序数组，所以必然是二分）、且不要考虑合并两个有序数组为一个数组（只要合并了，复杂度至少是O(m+n)）。

一个直观的思路是，将该问题转换为求第k大的数的问题。但由于这儿有两个有序数组A与B，因此我们首先比较A[k/2]与B[k - k/2 - 1]这两个元素的大小，较小者及其同一数组内之前的元素中一定不会存在目标元素，可以直接去掉——我们的“二分”就体现在这里。相较于“每次保留一半”，我们这里的做法是“每次排除一半”。

为什么下标pos1 = k/2对应下标pos2 = k - k/2 - 1呢？这是因为，如果A[pos1] < B[pos2]，那么A[l1 … pos1]中必然不存在第k大的数字！

需要注意的细节有：

如果所有元素为偶数个，需要找两个位置之后求平均值。
如果一个数组内没有那么多元素，此时直接将该数组内最后一个元素与另一数组内的对应位置（第一个数组内的位置i对应第二个数组内的位置k-i-1，这两个位置的元素如果相等，那它们刚好是目标位置）元素比较。
k到底指的是第k个、还是下标为k，需要想清楚。我在代码里的k指的下标为k。
k是绝对位置还是相对位置，需要想清楚。我在代码里的k为相对位置，需要加上l之后才表示真实位置。

边界条件为：

k为1时，仅需比较一次之后返回较小者即可。
当其中一个数组为空时，只需要在另一数组中返回位置k的元素即可。

代码（Python）

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        return (self.binary_find(nums1, 0, m-1, nums2, 0, n-1, (m+n)//2 - 1) +
                self.binary_find(nums1, 0, m-1, nums2, 0, n-1, (m+n)//2)) / 2 if (m+n) % 2 == 0 \
            else self.binary_find(nums1, 0, m-1, nums2, 0, n-1, (m+n)//2)

    def binary_find(self, nums1, l1, r1, nums2, l2, r2, k) -> float:
        if l1 > r1:
            return nums2[l2 + k]
        elif l2 > r2:
            return nums1[l1 + k]
        if k == 0:
            return min(nums1[l1], nums2[l2])
        if (r1 - l1) < (r2 - l2):
            pos1 = k//2 if l1+k//2 <= r1 else r1-l1
            pos2 = k - pos1 - 1
        else:
            pos2 = k//2 if l2+k//2 <= r2 else r2-l2
            pos1 = k - pos2 - 1
        if nums1[l1 + pos1] == nums2[l2 + pos2]:
            return nums1[l1 + pos1]
        elif nums1[l1 + pos1] < nums2[l2 + pos2]:
            return self.binary_find(nums1, l1 + pos1 + 1, r1, nums2, l2, r2, k - (pos1 + 1))
        else:
            return self.binary_find(nums1, l1, r1, nums2, l2 + pos2 + 1, r2, k - (pos2 + 1))