【算法】找两个正序数组的中位数难度：困难； 题目： 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1

难度：困难；

题目：

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

解题思路：

要找到两个已排序数组的中位数，并保证时间复杂度为O(log(m+n))，我们可以采用一种叫做“二分查找”的方法，但这次是在两个数组的合并空间上进行，即在m+n个元素上进行二分查找。不过，直接在m+n个元素上进行二分查找会比较困难，因此我们采取了一种更巧妙的方法，即在较小的数组上进行二分查找，这样可以简化问题。

1. 确定较小的数组：如果数组nums1比nums2大，那么就交换它们的位置，这样可以确保我们总是在较小的数组上进行操作。
2. 初始化边界：设置二分查找的边界，low为0，high为较小数组的长度。
3. 二分查找：

• 在较小的数组上进行二分查找，计算出中位数的可能位置i。
• 计算另一个数组中的对应位置j，使得两个数组被分割成左右两部分，左边部分的元素总数与右边部分相同。
• 确定四个关键数值：left1, left2, right1, right2，分别代表较小数组和较大数组左侧最大值及右侧最小值。
• 检查left1和left2是否都小于等于right1和right2，如果不是，则调整二分查找的边界，继续寻找正确的i值。

4.计算中位数：

• 如果(m + n)是奇数，那么中位数就是max(left1, left2)。
• 如果(m + n)是偶数，那么中位数是[max(left1, left2) + min(right1, right2)] / 2。

JavaScript代码实现：

var findMedianSortedArrays = function(nums1, nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    const x = nums1.length, y = nums2.length;
    let low = 0, high = x;

    while (low <= high) {
        const partitionX = Math.floor((low + high) / 2);
        const partitionY = Math.floor((x + y + 1) / 2) - partitionX;

        const maxLeftX = (partitionX === 0) ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];
        const minRightX = (partitionX === x) ? Number.POSITIVE_INFINITY : nums1[partitionX];

        const maxLeftY = (partitionY === 0) ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];
        const minRightY = (partitionY === y) ? Number.POSITIVE_INFINITY : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }

    throw new Error("Input arrays are not sorted");
};