力扣Leetcode：4. 寻找两个正序数组的中位数（Python）
题目描述
给定两个大小分别为 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))