4. Median of Two Sorted Arrays |

最直观的解法是使用寻找一个数组中第k个元素的方式。

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length,
                left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKth(nums1, nums2, left) + findKth(nums1, nums2, right)) / 2.0;
    }
    int findKth(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        if (m > n) return findKth(nums2, nums1, k);
        if (m == 0) return nums2[k - 1];
        if (k == 1) return Math.min(nums1[0], nums2[0]);
        int i = Math.min(m, k / 2), j = Math.min(n, k / 2);
        if (nums1[i - 1] > nums2[j - 1]) {
            return findKth(nums1, Arrays.copyOfRange(nums2, j, n), k - j);
        } else {
            return findKth(Arrays.copyOfRange(nums1, i, m), nums2, k - i);
        }
    }
}

这段代码的一个难点是，

int i = Math.min(m, k / 2), j = Math.min(n, k / 2);
if (nums1[i - 1] > nums2[j - 1]) {
    return findKth(nums1, Arrays.copyOfRange(nums2, j, n), k - j);
} else {
    return findKth(Arrays.copyOfRange(nums1, i, m), nums2, k - i);
}

为什么找寻到k/2个元素和各自数组长度的最小值所对应的数组值后，就可以将另一部分砍掉？

例如，

if (nums1[i - 1] > nums2[j - 1]) {
    return findKth(nums1, Arrays.copyOfRange(nums2, j, n), k - j);
} 

这就把nums2的前半部分砍掉了。为什么呢？我们可以用反证法做推理。砍掉nums2的前半部分，无非是说：在这里面，一定不存在我们要搜寻的合并后数组的第k个元素。

假设存在，那么，合并两个数组时，一定是nums2的至少前k/2个元素（因为我们假设了第k个元素在这前半段），和nums1的至少前k/2个元素（否则，将无法从别处找到元素来填充构成合并数组的前k个元素。这条可以从两个数组的单调递增看出来）来组成整个的合并数组。

此时，nums1[i]就被放在了nums2的前半段，这就与nums1[i]大于nums2[j]相矛盾。

同理可证nums1[i]小于等于nums2[j]的情况。