LeetCode算法题：004寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例1：

nums1 = [1, 3]

nums2 = [2]

则中位数是

示例2：

nums1 = [1, 2]

nums2 = [3, 4]

则中位数是 (2 + 3)/2 =

演示动画

分析

寻找两个有序数组的中位数，我们能够很快的联想到使用二分法寻找一个有序数组的中位数，它的时间复杂度就是O（log(n)）。现在是有两个数组，时间复杂度要求的是O(log(m+n))，所以基本可以肯定就是和二分法有关了。

那么对于这个问题该如何使用二分发呢？我们进行进一步的分析。

既然是中位数，那么这个数的位置其实是可以确定的：

• 对于m+n为奇数的情况，中位数就是第（m + n） / 2大的数。
• 对于m+n为偶数的情况，中位数就是第（m + n） / 2大和第（m + n） / 2 + 1大的数的平均数。

所以我们可以把上面的问题转换为寻找两个有序数组中第k大的数，k = (m + n) / 2。

毫无疑问第k大的数有k1个来自于数组nums1，有k2个来自于数组nums2。由于k是确定的数，所以当k1确定的后，k2也就确定了。

所以我们可以在数组nums1中选一个k1，然后判断数组nums1的前k1个数和数组nums2的前k2个数是不是两个数组中最小的那一部分。判断条件为：

1. nums1[k1 + 1] < nums[k2]
2. nums2[k2 + 1] < nums[k1]

我们可以利用二分法来找这个k1。

实现代码：