分治算法用到极限是什么样子?

摆上题目：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

刚开始，看到时间复杂度为O(log(m+n))，立马就会想到二分法，没错，但是针对这一题而言，拿到的是两个数组，两个数组长度的和为奇数和偶数怎么处理？遇到什么情况进行二分？怎么分？这是我们必须考虑的问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

一、什么是中位数？

首先，巩固一下中位数的概念: 有n个已经排好序的数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

• 对于n为奇数的情况，中位数则是第(n+1)/2个，即最中间的那个数。
• 对于n为偶数的情况，中位数则是第n/2个数和第n/2 + 1个数的算术平均值。

二、数组总长度奇数和偶数的情况怎么处理？

设总长度为n，找到第(n+1)/2个数，再找到第(n+2)/2个数 (注意:索引值都向下取整)。 然后，求两个数的平均值，即是最后要求的中位数。这样可以涵盖奇数和偶数的任一情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

三、遇到什么情况进行二分?怎么分？

回到原题的起点，我们是要找到特定位置的数，那么想一想可以通过什么方式排除绝对不属于这个位置的数？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

比如现在两个数组是[1, 2, 4, 6, 8], [5, 7, 9,11]。总长度为9，中位数为第5个，一个数组还好办，不过现在是两个数组的情况，我们采取一个比较巧妙的方式获得第5个数:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

• step1: 将5/2, 向下取整即为2，比较两个数组的第二个数，对应为2和7，明显前者比后者小，那么现在直接把第一个数组的前2个数剔除，因为它们百分之百在中位数的前面。
• step2: 那么，现在我们确定了前2个数，那即将要求的就是后面所有的数字中排第3的数了。按照之前的做法，3/2，向下取整为1， 比较两个数组的第一个数，对应4和5, 前者比后者小，直接把第一个数组的前1个数剔除，因为百分之百在中位数的前面，不用考虑。
• step3: OK，现在我们确定了前三个数，即将要求的就是后面所有的数字中排第2的数了，依照上述做法，我们剔除了5。
• step4: 现在确定了前四个数，即将要求的就是后面所有的数字中第1个数了，直接比较目前两个数组的第一个数即可，6 < 7， 我们取6。完成！

将问题一般化就是获取第k个数，取两个数组中第k/2个数进行比较，如果比较小，就把这个数组的前k/2个元素全部剔除，依次循环，直到k为1或者有一个数组为空。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

四、 如果k/2比其中一个数组的长度还要大怎么办？

这种情况，我们只需要取这个数组末尾的元素即可。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

五、JS代码展示

代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html

//找到第k大的元素
const findKMax = (num1, start1, end1, num2, start2, end2, k) => {
    let len1 = end1 - start1 + 1;
    let len2 = end2 - start2 + 1;
    //这里我是来保证num1的长度一定小于num2,这样确定num1为空，直接来取num2的第k个数
    if (len1 > len2)
        return findKMax(num2, start2, end2, num1, start1, end1, k);
    if (len1 == 0) return num2[start2 + k - 1];

    if (k == 1) return Math.min(num1[start1], num2[start2]);
    // |0这个操作为向下取整
    //如果k/2比其中一个数组的长度还要大,取数组末尾元素即可
    let i = start1 + Math.min(len1, k / 2 | 0) - 1;
    let j = start2 + Math.min(len2, k / 2 | 0) - 1;

    if (num1[i] > num2[j])
        //已经剔除j - start2 + 1个元素
        return findKMax(num1, start1, end1, num2, j + 1, end2, k - (j - start2 + 1));
    else
        //已经剔除i - start1 + 1个元素
        return findKMax(num1, i + 1, end1, num2, start2, end2, k - (i - start1 + 1));
}
//核心函数
const findMedianSortedArrays = (nums1, nums2) => {
    let m = nums1.length;
    let n = nums2.length;
    //向下取整
    let left = (m + n + 1) / 2 | 0;
    let right = (m + n + 2) / 2 | 0;
    
    //处理了数组总长度为奇数和偶数的情况
    return (findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, left) +
        findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, right)) * 0.5;
}
复制代码

成功AC！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16425.html