原题是这样的：
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
这是leetcode中一道比较难的题目，因为他要求在log(m+n)时间内完成，一开始看到这道题的时候我首先想到的是先把两个数组合并，然后直接找出合并后的数组的中位数，但是这种方法的时间复杂度为O(m+n),太慢，因此，之后听老师讲了一遍这道题，又在网上找到了相关的资料，了解到这道题用分治算法解决可以达到log级的算法复杂度，基本思路就是比较nums1和nums2中间的元素的大小，然后根据情况删除掉nums1或nums2的一部分元素，假设nums1和nums2长度一样并且a为nums1的中位数，b为nums2的中位数，若a>b，则将比b小的那部分长度为L的元素删掉，然后在新的两个数组中继续找（nums1.size()+nums2.size())/2-L小的数即可，注意，这是不再是找中位数，而是找第k小的数，因此，我们首先得实现找第k小的数的函数findKth()，然后再根据两个数组的长度是奇数还是偶数调用findKth()找到中位数，再接下来就是具体的算法描述：
找到第k小的数(输入有A、B两个数组)findKth(vector<int> A,vector<int>B,int k)：
1、我们将长度比较小的数组A放在前面，方便比较；
2、然后判断A数组的大小是否为0，是的话，返回B[k-1]即可；
3、若k=1，则返回A[0]、B[0]之间的较小值；
4、比较A数组大小n与k/2的大小，取较小的数a作为A数组元素的比较下标，以防k/2超过n，同时取k-a作为B数组的比较下标；
5、若A[a]<B[K-a]，则对A数组删掉a之前的元素，然后调用自身findKth(A,B,k-a);
6、若A[a]>B[K-a]，则对B数组删掉k-a之前的元素，然后调用自身findKth(A,B,a);
7、若A[a]=B[K-a],直接返回A[a-1]即可。
然后对于找两个数组的中位数，则只需分两数组的和是奇数还是偶数，调用findKth即可。可以看出最坏情况下，每次数组的总长度都会减少1/4，因此复杂度为O（log(m+n)），具体代码实现如下：
class Solution {
public:
double findKth(vector<int> nums1,vector<int> nums2,int k){
int n1=nums1.size();
int n2=nums2.size();
if(n1>n2){
return findKth(nums2,nums1,k);
}
if(n1==0)
return nums2[k-1];
if(k==1)
return min(nums1[0],nums2[0]);
int a=min(k/2,n1);
int b=k-a;
if(nums1[a-1]<nums2[b-1]){
nums1.erase(nums1.begin(),nums1.begin()+a);
return findKth(nums1,nums2,k-a);
}
else if(nums1[a-1]>nums2[b-1]){
nums2.erase(nums2.begin(),nums2.begin()+b);
return findKth(nums1,nums2,k-b);
}
else
return nums1[a-1];
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int sum=nums1.size()+nums2.size();
if(sum%2==1)
return findKth(nums1,nums2,sum/2+1);
else
return (findKth(nums1,nums2,sum/2)+findKth(nums1,nums2,sum/2+1))/2.0;
}
};