https://leetcode.com/problems/median-of-two-sorted-arrays/?tab=Description
找出两个有序数组中的中位数
如果key1 < key2，那么第k个数不可能在nums1的start ~ start + mid之间
如果start1 + mid >= len，那么第k个数不可能在nums2的start ~ start + mid之间，否则nums2的前mid个数加上nums1的全部也不够k
public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len = nums1.length + nums2.length; if (len % 2 != 0) { return findKth(nums1, 0, nums2, 0, len / 2 + 1); } else { return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, 1 + len / 2)) / 2.0; } } private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) { if (start1 >= nums1.length) { return nums2[start2 + k - 1]; } if (start2 >= nums2.length) { return nums1[start1 + k - 1]; } if (k == 1) { return Math.min(nums1[start1], nums2[start2]); } int mid = k / 2 - 1; int key1 = start1 + mid >= nums1.length ? Integer.MAX_VALUE : nums1[start1 + mid]; int key2 = start2 + mid >= nums2.length ? Integer.MAX_VALUE : nums2[start2 + mid]; if (key1 < key2) { return findKth(nums1, start1 + mid + 1, nums2, start2, k - mid - 1); } else { return findKth(nums1, start1, nums2, start2 + mid + 1, k - mid - 1); } } }