image.png

求2个排序数组的中位数，要求时间复杂度为O（log(m + n)）
暴力解法就是将2个排序数组合并成1个数组，然后求出中位数，时间复杂度为O（m + n），但是显然不符合题意。
这道题需要使用二分查找进行求解，有点技巧性。
对于2个有序数组，x和y求中位数
x -> x1 x2 x3 x4 x5
y -> y1 y2 y3 y4 y5 y6
关键的点就是在x中找到1个分割点，在y中找到1个分割点，如下所示
x -> x1 x2 | x3 x4 x5 x6
y -> y1 y2 y3 y4 y5 | y6 y7 y8
这样进行分割以后，x的左边部分加上y的左边部分的数量等于x的右边部分加上y的右边部分的数量，如果此时，有x2 <= y6 && y5 <= x3，那么中位数一定是avg(max(x2, y5), min(x3, y6))。
这里先解释一下为什么，如上所示，因为x和y都是递增的，那么x2一定小于x3,x4,x5,x6，并且y5一定小于y6,y7,y8，如果此时x2小于等于y6且y5小于等于x3，那么我们分隔点左边的数一定都是小于等于分隔点右边的数，并且如果此时左右两边的数是相等的，那么中位数一定等于x2,x3,y5,y6这4个数排序后的中间2个数的平均数，又因为x2 <= x3, y5 <= y6，x2 <= y6，y5 <= x3 所以中位数一定是avg(max(x2, y5), min(x3, y6))。如果数组x和y的总数是奇数的话也同理，如下所示
x -> x1 x2 | x3 x4 x5
y -> y1 y2 y3 y4 y5 | y6 y7 y8
我们使得分隔后的左边元素比右边元素多1个，那么此时中位数就等于max(x2, y5)

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        int lo = 0, hi = m;
        while (lo <= hi) {
            int partitionX = lo + (hi - lo) / 2;
            int partitionY = (m + n + 1) / 2 - partitionX;
            int maxLeftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minRightX = partitionX == m ? Integer.MAX_VALUE : nums1[partitionX ];
            int maxLeftY = partitionY == 0 ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minRightY = partitionY == n ? Integer.MAX_VALUE : nums2[partitionY];
            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if ((m + n) % 2 == 0) {
                    return (double) (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
                } else {
                    return Math.max(maxLeftX, maxLeftY);
                }
            }else if (maxLeftX > minRightY) {
                hi = partitionX - 1;
            } else {
                lo = partitionX + 1;
            }
        }
        throw new IllegalArgumentException();
    }