算法题之Median of Two Sorted Arrays

重刷leetcode，刷到此题。描述：

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

做这道题初，想着是分类，即把两个数组的包含关系分三个层次：完全错开、部分重叠和完全包含。分别求解，但是在讨论包含的时候，还是有一点束手无策了。回看以前提交的代码，囧了，是把两个数组重拍了，那算法估计得起码O(n+m)或者(n+m)O(log(n+m))了，竟然当时候可以通过。
这里直接带入我看到的算法，以供参考。
将原问题变为查找第k小的数，那么中位数即变为查找第(m+n)/2小的数。
假设原数组A和B元素个数都是大于k/2，比较Ak和Bk两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。
比较存在三种情况：>、<和=；
先看<：如果Ak<Bk，则可以说明在Ak之前的数都肯定不会包含第k小的数。因此这些数都可以省略掉。
反之如果>：说明在Bk之前的数都肯定不会包含第k小的数，Bk之前的数可以忽略。
如果最理想状况是相等，则已经找到。实际上是绝大部分情况都不会找到的，这里只是一个极端理想状况。更多的状况是删了数值以后，所找的第k小的数逐渐只变成了k=1，这样就直接找到了。
贴出JS代码：

var findMedianSortedArrays = function(nums1, nums2) {
    /**
     * @param {Number[]} nums1
     * @param {Number[]} nums2
     * @param {Number} k
     * @return {Number}
     */
    var findKth = function(nums1, nums2, k) {
        var m = nums1.length;
        var n = nums2.length;
        if (m > n) {
            return findKth(nums2, nums1, k);
        }
        if (m === 0) {
            return nums2[k - 1];
        }
        if (k === 1) {
            return Math.min(nums1[0], nums2[0]);
        }
        var pa = Math.floor(k / 2) < m ? Math.floor(k / 2) : m;
        var pb = k - pa;
        if (nums1[pa - 1] < nums2[pb - 1]) {
            var t1 = nums1.slice(pa);
            return findKth(t1, nums2, k - pa);
        } else if (nums1[pa - 1] > nums2[pb - 1]) {
            var t2 = nums2.slice(pb);
            //nums2.splice(0,pb);
            return findKth(nums1, t2, k - pb);
        } else {
            return nums1[pa - 1];
        }
    };

    var m = nums1.length;
    var n = nums2.length;
    var tol = m + n;
    if (tol / 2 - Math.floor(tol / 2) > 0.1) {
        return findKth(nums1, nums2, Math.floor(tol / 2) + 1);
    } else {
        return (findKth(nums1, nums2, Math.floor(tol / 2)) + findKth(nums1, nums2, Math.floor(tol / 2) + 1))/2;
    }
};