给定两个大小为 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
题解：
首先求中位数，两种情况:
（1）假设两个数组的总长度是奇数， 那么其中位数是一个值
（2）假设偶数的中位数是两个值的平均值
这样子就要分奇数跟偶数长度来算了。我们探索到一个规律，
假设两个数组和起来长度是偶数10,那么就是 第5个跟第6个位置的数了，5 = (10+1)/2, 6 = (10 + 2 )/ 2；
假设两个数组和起来长度是奇数11， 那么中位数就是第6个位置的数了， 6 = (11 + 1) / 2, 6 = (11 + 2) / 2；
所以题目可以转化成第 (n + 1) / 2 跟 (n + 2) / 2位上的数的平均值。
接着，我们的问题转移成：求两个有序数组中第n大的位置上的值了。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
int a = (n + 1) / 2;
int b = (n + 2) / 2;
search(nums1, nums2, 0, 0, a);
search(nums1, nums2, 0, 0, b);
return (double)(search(nums1, nums2, 0, 0, a) + search(nums1, nums2, 0, 0, b)) / 2;
}
public int search(int[] nums1, int[] nums2, int index1, int index2, int target) {
if (index1 >= nums1.length) {
return nums2[index2 + target - 1];
}
if (index2 >= nums2.length) {
return nums1[index1 + target - 1];
}
if (target == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
int midVal1 = (index1 + target / 2 - 1 < nums1.length) ? nums1[index1 + target / 2 - 1] : Integer.MAX_VALUE;
int midVal2 = (index2 + target / 2 - 1 < nums2.length) ? nums2[index2 + target / 2 - 1] : Integer.MAX_VALUE;
if (midVal1 < midVal2) {
return search(nums1, nums2, index1 + target / 2, index2, target - target / 2);
} else {
return search(nums1, nums2, index1, index2 + target / 2, target - target / 2);
}
}
}