「算法」「4. 寻找两个有序数组的中位数」看似简单实际暗藏玄机，

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0
示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

---

这道题是我初学数据算法不久，第一次遇到的困难题。这道题如果没有时间复杂度的限制，则是一道非常简单的题目，但是难点就在这个时间复杂度（很多人都没理解题意，直接拼接了两个数组，然后进行排序直接提交了上去）。当初为了这个时间复杂度，写了100行的算法代码，但却没有通过。实在是有些遗憾。拜读了题解第三的解法，图文并茂。

题解思路是对于两个数组不断的使用二分法进行求解。

第一步操作

比如，有两个数组
 [1,3,4,9]
 [1,2,3,4,5,6,7,8,9,10]
而两个数组中，我们要求其中位数，则是第 target 为 第 7 位。而同时我们对两个数组进行操作，位数为 7 / 2 向下取整，即同时操作 3 位
则此时
 [1,3,4,9]
      ↑
 [1,2,3,4,5,6,7,8,9,10]
      ↑
由于
4 > 3
我们可以排除掉下边数组包括 3 前边的元素，因为它们必定不是我们要寻找的元素。
现在数组变成了
[1,3,4,9]
[4,5,6,7,8,9,10]

第二步操作

接着在新数组中寻找新的中位数，此时位数由 此时 target 为 7 减去已去除的 3 位，即为 4，按照上面的操作方法，此时我们同时操作 4 / 2 = 2 位
[1,3,4,9]
   ↑
[4,5,6,7,8,9,10]
   ↑
由于
5 > 3
我们可以去除上边数组包括 3 前边的元素。
此时数组变为
[4,9]
[4,5,6,7,8,9,10]

第三步操作

第一次操作去除了3位，第二次操作再次去除了 2 位，此时离我们的目标只剩下2位。再次使用上述方法，操作 2 / 2 = 1位
但是此时元素的相等了，那么就假定上边的数组的元素大于下边的数组的元素，进行操作
此时数组变为
[4,9]
[5,6,7,8,9,10]
此时我们还差最后一位进行操作，则直接比较返回即可。

此时代入代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    //首先获取两个数组的长度，
    const length1 = nums1.length
    const length2 = nums2.length
    
    const left = parseInt((length1 + length2 + 1) / 2)
    const right = parseInt((length1 + length2 + 2) / 2)
    //因为总数组的长度的奇偶不同，所需要求的中位数值是不同的，所以我们需要判断一下
    if(left === right) {
        return getMidNum(nums1, 0, length1 - 1, nums2, 0, length2 - 1, left) //如果左右相同，那么就只用计算一个进行返回
    }else {
        return (getMidNum(nums1, 0, length1 - 1, nums2, 0, length2 - 1, left) + getMidNum(nums1, 0, length1 - 1, nums2, 0, length2 - 1, right)) / 2//如果左右不能等，那么说明需要计算总数组的中间两位数
    }

    function getMidNum(nums1, start1, end1, nums2, start2, end2, key) {
        const len1 = end1 - start1 + 1 //先获取传入的两个数组的长度，就如前边一样，我们始终要保持nums2长度大于nums1。
        const len2 = end2 - start2 + 1
        if(len1 > len2) {
            return getMidNum(nums2, start2, end2, nums1, start1, end1, key) //递归终止，互换传入的数组
        }
        if(len1 === 0) { //len1已经不够了，直接计算剩下的key，返回nums2里的数据即可
            return nums2[start2 + key - 1]
        }
        if(key === 1) { //已经逼近了最后的一位数，此时直接比较数组的start位即可。因为len2 > len1，且len1 !== 0，此时两个数组都必是有值的。
            return Math.min(nums1[start1], nums2[start2])
        }
        //此时开始计算两个数组应该逼近的位数，
        let i = start1 + Math.min(len1, parseInt(key / 2)) - 1
        let j = start2 + Math.min(len2, parseInt(key / 2)) - 1
        //比较数组，小的数组的start去掉（实际是更新start位置
        if(nums1[i] > nums2[j]) {
            return getMidNum(nums1, start1, end1, nums2, j + 1, end2, key - (j - start2 + 1))
        }else {
            return getMidNum(nums1, i + 1, end1, nums2, start2, end2, key - (i - start1 + 1))
        }
    }
};

代码设计的得很精妙。
用到了递归，因为是一次递归，所以空间复杂度实际上是O（1），且时间复杂度是log(m+n)。

---

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。