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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

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

class Solution {
    private int findKth(int[] num1, int[] num2, int k) {
        if (num1.length == 0) {
            return num2[k - 1];
        }

        if (num2.length == 0) {
            return num1[k - 1];
        }

        int[] shortArray = num1.length < num2.length ? num1 : num2;
        int[] longArray = shortArray == num1 ? num2 : num1;

        if (k <= shortArray.length) {
            return findUpMedian(shortArray, 0, k - 1, longArray, 0, k - 1);
        } else if (k <= longArray.length) {
            // 1 2 3 4 5
            // 1 [2 3 4 5 6 [7]] 8 9
            int longStart = k - shortArray.length - 1;
            if (longArray[longStart] >= shortArray[shortArray.length - 1]) {
                return longArray[longStart];
            }
            return findUpMedian(shortArray, 0, shortArray.length - 1, longArray, longStart + 1, k - 1);
        } else {
            // 1 2 [3 4 5]
            // 1 2 3 4 [5 6 7] | 8 9 [10] 11 12
            int shortStart = k - longArray.length - 1;
            int longStart = k - shortArray.length - 1;
            if (shortArray[shortStart] >= longArray[longArray.length - 1]) {
                return shortArray[shortStart];
            }

            if (longArray[longStart] >= shortArray[shortArray.length - 1]) {
                return longArray[longStart];
            }

            return findUpMedian(shortArray, shortStart + 1, shortArray.length - 1, longArray, longStart + 1, longArray.length - 1);
        }
    }

    /**
     * 发现两个等长增序数组的中位数
     */
    private int findUpMedian(int[] num1, int start1, int end1, int[] num2, int start2, int end2) {
        while (start1 < end1) {
            int m1 = (start1 + end1) >> 1;
            int m2 = (start2 + end2) >> 1;
            int offset = (end1 - start1 + 1) & 1 ^ 1;

            // 1 2 3 4 5
            // 1 2 3 4 5

            // 1 2 3 4 5 6
            // 1 2 3 4 5 6
            if (num1[m1] < num2[m2]) {
                start1 = m1 + offset;
                end2 = m2;
            } else {
                start2 = m2 + offset;
                end1 = m1;
            }
        }
        return Math.min(num1[start1], num2[start2]);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = (nums1.length + nums2.length);

        if (length % 2 == 0) {
            return (findKth(nums1, nums2, length / 2) + findKth(nums1, nums2, length / 2 + 1)) / 2.0;
        } else {
            return findKth(nums1, nums2, length / 2 + 1);
        }
    }
}