现有两个有序数组 nums1 和 nums2，大小分别为 m 和 n。求这两个数组的中位数。算法时间复杂度应为 O(log(m+n))。
你可以认为 nums1 和 nums2 不同时为空。

例一：
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0。

例二：
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5。

/*
 * 4. Median of Two Sorted Arrays
 * https://leetcode.com/problems/median-of-two-sorted-arrays/
 * https://www.whosneo.com/4-median-of-two-sorted-arrays/
 */

public class FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 3};
        int[] nums2 = new int[]{4, 5};

        FindMedianSortedArrays solution = new FindMedianSortedArrays();

        System.out.println(solution.findMedianSortedArrays(nums1, nums2));
    }

    private double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;

        int target = (m + n + 1) / 2;
        if ((m + n) % 2 == 1)
            return getKth(nums1, nums2, target);
        else
            return (getKth(nums1, nums2, target) + getKth(nums1, nums2, target + 1)) * 0.5;
    }

    private int getKth(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int ptr1 = 0, ptr2 = 0;

        while (ptr1 < length1 && ptr2 < length2 && k > 1) {
            int i = ptr1 + k / 2 - 1;
            i = i < length1 ? i : length1 - 1;
            int j = ptr2 + k / 2 - 1;
            j = j < length2 ? j : length2 - 1;

            if (nums1[i] > nums2[j]) {
                k = k - (j - ptr2 + 1);
                ptr2 = j + 1;
            } else {
                k = k - (i - ptr1 + 1);
                ptr1 = i + 1;
            }
        }

        if (ptr1 == length1)
            return nums2[ptr2 + k - 1];
        else if (ptr2 == length2)
            return nums1[ptr1 + k -1];
        else
            return Math.min(nums1[ptr1], nums2[ptr2]);
    }
}