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

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

你可以假设 nums1 和 nums2 不会同时为空。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

示例1：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

nums1 = [1, 3]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

nums2 = [2]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

则中位数是文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

示例2：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

nums1 = [1, 2]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

nums2 = [3, 4]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

则中位数是 (2 + 3)/2 =文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

演示动画文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

分析文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

寻找两个有序数组的中位数，我们能够很快的联想到使用二分法寻找一个有序数组的中位数，它的时间复杂度就是O（log(n)）。现在是有两个数组，时间复杂度要求的是O(log(m+n))，所以基本可以肯定就是和二分法有关了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

那么对于这个问题该如何使用二分发呢？我们进行进一步的分析。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

既然是中位数，那么这个数的位置其实是可以确定的：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

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

所以我们可以把上面的问题转换为寻找两个有序数组中第k大的数，k = (m + n) / 2。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

毫无疑问第k大的数有k1个来自于数组nums1，有k2个来自于数组nums2。由于k是确定的数，所以当k1确定的后，k2也就确定了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

所以我们可以在数组nums1中选一个k1，然后判断数组nums1的前k1个数和数组nums2的前k2个数是不是两个数组中最小的那一部分。判断条件为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

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

我们可以利用二分法来找这个k1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html

实现代码：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11029.html