题目要求很简单，就是给你两个已经排好序的数组nums1（长度为m）和nums2（长度为n），找出他们的中间值。返回值类型double是因为如果数字个数是偶数个，就要返回中间两个数的平均值。这题最简单的方法就是通过两个指针分别从nums1和nums2的头一直移动，直到走到nums1和nums2的中值位置为止。整个过程耗时大概是O((m+n) / 2)。但是题目附带需要用O(log(m+n))的时间完成，所以上述方法就不能用了。能用到O(log(m+n))的方法在leetcode的算法题里面没有几个，二分法是最常见的一种。其实一般来说，array，sorted，寻找某个数，看到这些关键词，就可以考虑（不是一定）使用二分法来做。问题是，这一题怎么使用二分法？
其实这一个问题可以延伸至在两个数组之间寻找第kth个元素，只是现在k = (m+n) / 2。为了方便理解，我举个例子，假设有两个数组，分别是:
nums1 = [1,4,5,6,8,10]
nums2 = [1,2,4,7,9,11]
因为我要找到第k个数，所以我把nums1从k/2处划分两部分，把nums2也从k/2处划分两部分，此题中，k/2 = (12 / 2) / 2 = 3，故index 应该是k/2 - 1处：
1 4 5 ｜ 6 8 10
1 2 4 ｜ 7 9 11
这时候，比较nums1和nums2在index处的大小，发现nums2[index] < nums1[index]，这个结果我们可以保证，第k个数一定不在1，2，4里面（为什么？请读者自己证明），所以我们可以大胆从nums2里面把1，2，4给删除。这样，就把在两个数组间寻找第k个元素转变为寻找第(k - (index+1))个元素，继续进入递归或者迭代，直到找到那个第k个元素为止。那什么时候算找到呢？有三种情况：
- 当其中一个数组被删光（假设为nums1)，则返回的就是nums2[k'-1]（这个k'是迭代多次后的k'）。
- 当k=1的时候，那么，只需要找nums1[0]和nums2[0]中的较小者就可以。
- 当nums1[k/2 - 1] ＝ nums2[k/2 - 1]的时候，则这个数就是所要寻找的第k个数。
当然，如果nums1的长度小于k/2怎么办？那么就用nums1[m-1]和nums2[k - m - 1]比较，比较后的处理也是一样的。代码如下：
//总体思路：把寻找两个sorted数组的中值转变为寻找两个sorted数组的第k大元素。
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
//元素个数为基数的时候
if (total % 2 != 0) {
return (double)findKth(nums1,nums2,total / 2 + 1);
}
//元素个数为偶数的时候
else {
return (findKth(nums1,nums2,total/2) +
findKth(nums1,nums2,total/2 + 1)) / 2.0;
}
} private int findKth(int[] nums1, int[] nums2, int k) {
//默认nums1的长度小于num2的长度，省去很多不必要的判断。
if (nums1.length > nums2.length) return findKth(nums2,nums1,k);
if (nums1.length == 0) return nums2[k-1];
if (k == 1) return Math.min(nums1[0],nums2[0]); //把K分成两部分。如果nums1.length < k/2,则取k/2个数，否则取nums1.length个数；
int index1 = Math.min(k/2,nums1.length);
//nums2里的前k-index1个数。
int index2 = k - index1;
//-1是因为index从0开始，第index1个数就是index1 - 1;
//当num1 < num2时，去除掉nums1里包括index1-1之前的所有数(index1个)。
if (nums1[index1 - 1] < nums2[index2 - 1]) {
int[] temp1 = new int[nums1.length - index1];
System.arraycopy(nums1,index1,temp1,0,nums1.length - index1);
//更新k值，进入下个递归。
return findKth(temp1,nums2,k-index1);
}
//情况与上面相反。
else if (nums1[index1 - 1] > nums2[index2 - 1]) {
int[] temp2 = new int[nums2.length - index2];
System.arraycopy(nums2,index2,temp2,0,nums2.length - index2);
return findKth(nums1,temp2,k - index2);
}
//两者相同，说明找到了k值。
else {
return nums1[index1 - 1];
}
}
}
当然，代码还可以继续优化，例如加两个变量，可以直接在nums1和nums2上递归而不需要重新建一个数组，这样就能节省不少空间和时间，但是总体的思路是一样的。