####【题目】
给定两个有序数组arr1和arr2，已知两个数组的长度分别为 m1 和 m2，求两个数组中的中位数。要求时间复杂度O(log(m1 + m2))。
####【举例】
例如 arr1 = [1, 3]，arr2 = [2].
则中位数为 2.
例如 arr1 = [1,2]，arr2 = [3,4].
则中位数是 (2 + 3)/2 = 2.5
####【难度】
难
这道题和我上两次讲的那两道题是非常相似的，不过这道题比上面两道题要难很多，大家可以先想想怎么做这道题哦。
为什么说它难呢？其实是有原因的，如果两个数组的长度和为奇数的话，那么这道题不难，它比“求两个有序数组的第 K 小数”还简单；难就难在两个数组的长度和为偶数时，这道题的难度顿时上升了。
为什么呢?因为你要求出两个数，然后再来求平均，而且主要，这两个数可能一个数是位于 arr1 数组，而一个数是位于 arr2 数组，这会导致我们的判断逻辑变的很复杂。不信的话，你可以去试试。
那怎么办呢？实际上，这道题我们是可以进行一下转换，就是无论两个数组的长度和是奇数还是偶数，我们都求出第 （m1+m2+1)/2 小数以及第 （m1+m2+2)/2小数，然后求这两个数的平均数，就可以了。这样，我们就屏蔽了奇偶数的影响，会容易了挺多，并且可以利用我们上次写的”求两个有序数组的第 K 小数“来解决，这就是问题转换的重要性，要善于把复杂度的题转化为我们比较熟悉的题，才能举一反三。
代码如下：
// 由于中位数会受长度是奇偶数的影响，所以我们可以把问题转化为求
// (（n+m+1)/2+(n+m+2)/2)/2。
public double findMedianSortedArrays(int[] arr1, int[] arr2) {
int n = arr1.length;
int m = arr2.length;
return (findKth(arr1, arr2,(n+m+1)/2) + findKth(arr1,arr2,(n+m+2)/2)) /2;
}
public static int findKth(int[] arr1, int[] arr2, int k) {
if(arr1 == null || arr1.length < 1)
return arr2[k-1];
if(arr2 == null || arr2.length < 1)
return arr1[k-1];
// 注意这个函数的参数有7个，上面那个函数的参数只有3个，同名不同函数哈
return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k - 1);
}
public static int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {
// 递归结束条件
if(l1 > r1)
return arr2[l2 + k];
if(l2 > r2)
return arr1[l1 + k];
if (k == 0)// 注意，k == 0的结束条件与上面两个结束条件不能颠倒。
return Math.min(arr1[l1],arr2[l2]);
int md1 = l1 + k/2 < r1 ? l1 + k/2 : r1;
int md2 = l2 + k/2 < (r2 - l1) ? l2 + k/2 : r2;
if(arr1[md1] < arr2[md2])
return findKth(arr1, md1 + 1, r1, arr2, l2, r2, k - k / 2 - 1);
else if (arr1[md1] > arr2[md2])
return findKth(arr1, l1, r1, arr2, md2 + 1, r2, k - k / 2 - 1);
else
return arr1[md1];//返回arr2[md2]也可以，一样的。
}这三道递归的题可以说是后一道是前一道的进阶，虽然思路上不怎么难，但要实现出来还是有一定的难度，如果你都搞懂了，并且自己把代码写出来了，对你编写代码的能力一定会大大提升。
学习更多算法 + 计算机基础知识，欢迎关注我的微信公众号，每天准时推送技术干货
