寻找两个正序数组的中位数

困难

给定两个大小分别为 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

题解

如果不考虑时间复杂度，最简单的做法就是合并数组，并进行排序，然后根据排序后的长度为偶数还是奇数来获取中位数
代码如下

javascript

var findMedianSortedArrays = function (nums1, nums2) {
  let arr = nums1.concat(nums2).sort((a, b) => a - b);

  let len = arr.length;
  let res = 0;

  if (len % 2 === 0) {
    let l = len / 2 - 1;
    let r = len / 2;
    res = (arr[l] + arr[r]) / 2;
  } else {
    res = arr[Math.floor(n / 2)];
  }

  return res;
};

该算法的时间复杂度为O((m+n) log(m+n))，但是由于题目中对时间复杂度有要求，所以不能这么写，题目中要求的是O(log(m+n))，一看到logn的复杂度就可以联想到二分查找。
思路如下

寻找两个正序数组的中位数 ​

题解 ​

寻找两个正序数组的中位数

题解