一道非常经典的题目，Median of Two Sorted Arrays。（PS：leetcode 我已经做了 190 道，欢迎围观全部题解 https://github.com/hanzichi/leetcode）

题意非常简单，给定两个有序的数组，求中位数，难度系数给的是 Hard，希望的复杂度是 log 级别。回顾下中位数，对于一个有序数组，如果数组长度是奇数，那么中位数就是中间那个值，如果长度是偶数，就是中间两个数的平均数。

O(nlogn)

最容易想到的解法是 O(nlogn) 的解法，将两个数组合并成一个，然后排序，排序用 JavaScript 数组内置的 sort 函数，复杂度 nlogn，最后根据数组长度选择中位数，非常容易理解。

var findMedianSortedArrays = function(nums1, nums2) {  // 合并数组  var s = nums1.concat(nums2);  // 排序  s.sort(function(a, b) {    return a - b;  });  var len = s.length;  // 根据数组长度求中位数  if (len & 1) return s[~~(len / 2)];  else return (s[len / 2 - 1] + s[len / 2]) / 2;};

O(n)

将两个有序的数组合并成一个有序的数组，想到了什么？没错，这正是归并排序的关键一步。

关于归并排序，请看楼主以前写的这篇 【前端也要学点算法】 归并排序的JavaScript实现。这正是写博客的好处之一，可以将知识体系串联起来，比如这里我就不用介绍归并排序了，因为那篇文章我已经写的非常非常清楚了，而且就算现在我忘了，稍微看一遍也就能记起来了。

我们把归并排序中的 merge 函数拉出来，就 ok 了，一次线性的循环，复杂度降到了 O(n)。（其实应该是 O(n+m)，方案一也一样，就不多加区别了）

var findMedianSortedArrays = function(nums1, nums2) {  // 合并数组，返回有序数组  var s = merge(nums1, nums2);  var len = s.length;  // 根据数组长度求中位数  if (len & 1) return s[~~(len / 2)];  else return (s[len / 2 - 1] + s[len / 2]) / 2;};function merge(left, right) {  var tmp = [];  while (left.length && right.length) {    if (left[0] < right[0])      tmp.push(left.shift());    else      tmp.push(right.shift());  }  return tmp.concat(left, right);}

PS：其实对于此题，排序到一半就 ok 了，绝对的复杂度可以降到一半，不过也没什么必要。

O(logn)

以上两种解法，个人觉得难度系数对应的分别是 Easy 和 Medium，而 Hard 的解法应该把复杂度降到 log 级别。

换个方式思考，给出两个有序数组，假设两个数组的长度和是 len，如果 len 为奇数，那么我们求的就是两个数组合并后的第 (len >> 1) + 1 大的数，如果 len 为偶数，就是第 (len >> 1) 和 (len >> 1) + 1 两个数的平均数。

可以进一步扩展，给定两个有序数组，求第 k 大数。有序 + log 级别的复杂度，想到了什么？二分查找。

假设两个有序数组 a 和 b，长度分别是 m 和 n，求第 k 大数。假设在 a 中取 x 个，那么 b 数组中取的个数也就确定了，为 k - x 个，据此我们可以将两个数组分别一分为二，根据两边的边界值判断此次划分是否合理。而对于 x 的值，我们可以用二分查找。二分查找可以用迭代或者递归，这里我参考了 leetcode之 median of two sorted arrays 的递归写法，美中不足的是频繁调用了 slice 方法，可能导致性能下降。

var findMedianSortedArrays = function(nums1, nums2) {  var m = nums1.length;  var n = nums2.length;  var total = m + n;  var half = total >> 1;  if (total & 1)    return findKth(nums1, m, nums2, n, half + 1);  else     return (findKth(nums1, m, nums2, n, half) + findKth(nums1, m, nums2, n, half + 1)) / 2;};function findKth(a, m, b, n, k) {   // always assume that m is equal or smaller than n    if (m > n)      return findKth(b, n, a, m, k);    if (m === 0)      return b[k - 1];    if (k === 1)      return Math.min(a[0], b[0]);   // divide k into two parts    var pa = Math.min(k >> 1, m)    , pb = k - pa;    if (a[pa - 1] < b[pb - 1])      return findKth(a.slice(pa), m - pa, b, n, k - pa);    else if (a[pa - 1] > b[pb - 1])      return findKth(a, m, b.slice(pb), n - pb, k - pb);    else     return a[pa - 1];  }  

如果有其他解法或者建议，欢迎探讨~