Java寻找两个有序数组的中位数

题目描述：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解题思路：

题目要求时间复杂度为 O(log(m+n))，很明显是要用到二分查找的思想。

首先，我们需要确定中位数的位置。对于两个长度分别为 m 和 n 的有序数组，它们的中位数位置为 (m+n+1)/2 和 (m+n+2)/2，因为当 m+n 为奇数时，这两个位置的值是相同的；当 m+n 为偶数时，这两个位置的值分别为中间两个数。

然后，我们需要在两个数组中分别找到第 k/2 个数（k 为中位数位置），比较它们的大小，如果 nums1[k/2-1] < nums2[k/2-1]，则说明中位数位于 nums1 的右半部分和 nums2 的左半部分之间，此时可以舍弃 nums1 的左半部分，将 k 减去 nums1 的左半部分的长度，继续在 nums1 的右半部分和 nums2 的左半部分中寻找第 k/2 个数；反之，如果 nums1[k/2-1] >= nums2[k/2-1]，则说明中位数位于 nums1 的左半部分和 nums2 的右半部分之间，此时可以舍弃 nums2 的左半部分，将 k 减去 nums2 的左半部分的长度，继续在 nums1 的左半部分和 nums2 的右半部分中寻找第 k/2 个数。

当 k=1 时，中位数为两个数组中的最小值。

Java代码实现：

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int k = (m + n + 1) / 2;
double median = findKth(nums1, 0, m - 1, nums2, 0, n - 1, k);
if ((m + n) % 2 == 0) {
int k2 = k + 1;
double median2 = findKth(nums1, 0, m - 1, nums2, 0, n - 1, k2);
median = (median + median2) / 2;
}
return median;
}

private double findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if (len1 > len2) {
return findKth(nums2, start2, end2, nums1, start1, end1, k);
}
if (len1 == 0) {
return nums2[start2 + k - 1];
}
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return findKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
} else {
return findKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
}