4. 寻找两个正序数组的中位数

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

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

奇偶分析+二分查找

如果 pivot1 <= pivot2，说明 nums1 的 index1 到 newIndex1 范围内的元素都不可能是第 k 小的元素 （因为即使这些元素与 nums2 中的前几个元素合并，数量也还不够 k）。因此，这些元素可以被安全地排除掉， 同时更新 index1 的位置到 newIndex1 + 1（即排除这部分元素后，index1 的新起点）。

k -= (newIndex1 - index1 + 1); 这行代码更新了 k 的值，减去了被排除的元素的数量，即下一次寻找第 k 小的元素变为寻找第 k - 排除的元素数量 小的元素。

• 如果 $A[k / 2-1]<B[k / 2-1]$, 则比 $A[k / 2-1]$ 小的数最多只有 $A$ 的前 $k / 2-1$ 个数和 $B$ 的前 $k / 2-1$ 个数，即比 $A[k / 2-1]$ 小的数最多只有 $k-2$ 个，因此 $A[k / 2-1]$ 不可能是第 $k$ 个数， $A[0]$ 到 $A[k / 2-1]$ 也都不可能是第 $k$ 个数，可以全部排除。
• 如果 $A[k / 2-1]>B[k / 2-1]$ ，则可以排除 $B[0]$ 到 $B[k / 2-1]$ 。
• 如果 $A[k / 2-1]=B[k / 2-1]$ ，则可以归入第一种情况处理。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        
        if (totalLength % 2 == 1) {
            // 当总长度为奇数时，中位数是中间的一个元素
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            // 当总长度为偶数时，中位数是中间两个元素的平均值
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    // 找到两个正序数组中第 k 小的元素
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况。注意有两个边界情况，一个是数组为空，一个是k=1。几个独立变量就有几种边界情况。
            if (index1 == length1) {
                // 如果nums1为空数组，则直接返回nums2中的第k小的元素，类似下面的newIndex2的计算
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                // 如果nums2为空数组，则直接返回nums1中的第k小的元素
                return nums1[index1 + k - 1];
            }
            // 注意不要漏掉1这个边界情况
            if (k == 1) {
                // 如果k为1，即找最小元素，直接返回nums1和nums2当前索引的最小值
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 正常情况，二分查找
            int half = k / 2;
            // 计算新的检查位置，从起点向后查k/2-1个，到达本数组的第k/2个数，注意不能超出数组长度
            // k对应的是长度，index是索引，长度-1=索引
            int newIndex1 = Math.min(index1 + half - 1, length1 - 1);
            int newIndex2 = Math.min(index2 + half - 1, length2 - 1);
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            
            if (pivot1 <= pivot2) {
                // pivot1较小或等于pivot2，排除nums1中index1到newIndex1的部分，并更新k值和本数组的起点
                // k 向 1 靠近，起点向终点靠近，这样就能被上面的边界情况处理。即每次排除一些元素，收敛到边界情况。
                // 举例，index1=0，newIndex1=k/2-1，此时k-k/2=k/2.
                // 注意不一定是减去k/2！因为newIndex还有一个上界——length - 1
                k -= (newIndex1 - index1 + 1);
                // index1=k/2，index2=0，下一轮假设index1越界了，则nums[index2+k-1]=nums[k-1]即第k个元素
                index1 = newIndex1 + 1;
            } else {
                // pivot2较小，排除nums2中index2到newIndex2的部分，并更新k值和本数组的起点
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

• 时间复杂度: $O(\log (m+n))$ ，其中 $m$ 和 $n$ 分别是数组 $nums_1$ 和 $nums_2$ 的长度。初始时有 $k=(m+n) / 2$ 或 $k=(m+n) / 2+1$ ，每一轮循环可以将查找范围减少一半，因此时间复杂度是 $O(\log (m+n))$ 。
• 空间复杂度: $O(1)$ 。