如果某个有序数组长度是奇数，那么其中位数就是中间元素；如果长度是偶数，那么中位数就是中间两个数字的平均值.
假设两个有序数组的长度分别为 m 和 n，由于两个数组长度之和 m+n 的奇偶不确定，为了简化代码，在合并后的数组找到第 (m+n+1)/2 个元素，和第 (m+n+2)/2 个元素（这里的 / 指的是整除），然后求两者平均值. 若 m+n 为偶数，那么两者平均值刚好是中位数；若 m+n 为奇数，那么 (m+n+1)/2 和 (m+n+2)/2 的值相等，相当于两个相同的数字相加再除以 2，还是中位数本身.
可以实现一个函数 findKth(k)，返回两个有序数组合并后的第 k 个元素，最终答案为 findKth((m+n+1)/2) 和 findKth(m+n+2)/2 的平均值.
具体实现 findKth(k) 函数，需要对参数 k 进行二分处理：
nums1 和 nums2 中找到各自的第 k/2 个元素，并比较它们的大小.nums1 中的第 k/2 个元素更小，说明原 nums1 的前 k/2 个元素都不是合并后的第 k 个元素（可以参考后面的举例）. 因此可以忽略 nums1 中的前 k/2 个元素，继续求解在 nums1 的剩余部分和 nums2 合并后的第 k-k/2 个元素.nums2 中第 k/2 个元素更小，同理忽略 nums2 中的前 k/2 个元素，继续求解在 nums1 和 nums2 的剩余部分合并后的第 k-k/2 个元素.举例说明，假设 nums1=[1,3,6,9], nums2=[2,4,5,8], k=4 .
k/2=2，分别找 nums1 和 nums2 的第 2 个元素，nums1 的第 2 个元素是 3，nums2 的第 2 个元素是 4，由于 3<4，所以 nums1 中的前两个元素 1,3 在合并之后的数组中一定会排在第 4 个数之前，接下来将问题变成，nums1=[6,9], nums2=[2,4,5,8], k=2，k 的规模减半，可以递归求解.
特殊情况： 如果 nums1 的长度小于 k/2，则可直接忽略 nums2 的前 k/2 个元素，反之亦然. 比如 nums1=[3], nums2=[2,4,5,6,7], k=4，分别在 nums1 和 nums2 中找第 k/2=2 个数字，而 nums1 中只有 1 个数字，则可以直接忽略 nums2 中的前 2 个数字，因为最终答案是合并后数组的第 4 个数字，即使 nums1 中的数非常小， nums2 的前 2 个数字在合并之后也最多只能排在第 3 位.
递归终止条件：
nums1 或 nums2 为空时，直接返回非空数组的第 k 个元素即可.k=1 时，直接比较 nums1 和 nums2 的第 1 个元素大小即可.k 的规模不断减半，因此时间复杂度为
O
(
l
o
g
(
m
+
n
)
)
O(log(m+n))
O(log(m+n)).
class Solution {
public:
double findKth(vector<int>& nums1,vector<int>& nums2,int pos1,int pos2,int k){
//返回两个有序数组nums1(从pos1下标开始),nums2(从pos2下标开始)合并后的第k个元素
if(pos1>=(int)nums1.size()) return nums2[pos2+k-1];
if(pos2>=(int)nums2.size()) return nums1[pos1+k-1];
if(k==1) return nums1[pos1]<=nums2[pos2]?nums1[pos1]:nums2[pos2];
int midVal1=pos1+k/2-1<(int)nums1.size()?nums1[pos1+k/2-1]:INT_MAX;
int midVal2=pos2+k/2-1<(int)nums2.size()?nums2[pos2+k/2-1]:INT_MAX;
if(midVal1<=midVal2) return findKth(nums1,nums2,pos1+k/2,pos2,k-k/2);
else return findKth(nums1,nums2,pos1,pos2+k/2,k-k/2);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size(),n=nums2.size();
return 1.0*(findKth(nums1,nums2,0,0,(m+n+1)/2)+findKth(nums1,nums2,0,0,(m+n+2)/2))/2.0;
}
};
个人 LeetCode 代码仓库地址：MyLeetCode，记录刷题成长之路，欢迎各位小伙伴们多多 star ~