题目：

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)).
You may assume nums1 and nums2 cannot be both empty.

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
```

1.最简单的方法，并归然后取中位数，O(m+n)，想不到其他方法就硬着头皮试试，不知道为啥leetcode居然给过了。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1=nums1.size(),n2=nums2.size(),i1=0,i2=0,n=n1+n2;
        vector<int> nums;
        while(i1<n1 && i2<n2)
            if(nums1[i1]<nums2[i2])
                nums.push_back(nums1[i1++]);
            else
                nums.push_back(nums2[i2++]);
        while(i1<n1)
            nums.push_back(nums1[i1++]);
        while(i2<n2)
            nums.push_back(nums2[i2++]);
        if(n%2)
            return nums[n/2];
        else
            return (double)(nums[n/2]+nums[n/2-1])/2;	
    }
};

2.递归分治法 O（log（m+n）），将问题转化为求两个有序数组第k个元素。
不妨设数列A元素个数为n，数列B元素个数为m，各自升序排序，求第k小元素。
取A[k/2] B[k/2] 比较，假设 A[k/2] > B[k/2] ，那么，所求的元素必然不在B的前k/2个元素中(证明反证法)。
于是我们可以将B的前k/2元素删去，求剩下两个数列的k - k / 2小元素，于是得到了数据规模变小的同类问题，递归解决
如果 k / 2 大于某数列个数，所求元素必然不在另一数列的前k / 2个元素中，同上操作就好。

//nums1的i1位置开始, nums2的i2位置开始,找第k个数 
double find_kth(vector<int>& nums1, vector<int>& nums2,int i1,int i2,int k){
	if(i1>=nums1.size())
		return nums2[i2+k-1];
	if(i2>=nums2.size())
		return nums1[i1+k-1];
	if(k==1)
		return nums1[i1]>nums2[i2]?nums2[i2]:nums1[i1];
	int p1=i1+k/2-1>=nums1.size()?INT_MAX:nums1[i1+k/2-1];
	int p2=i2+k/2-1>=nums2.size()?INT_MAX:nums2[i2+k/2-1];
	if(p1<p2)
		return find_kth(nums1,nums2,i1+k/2,i2,k-k/2);
	return find_kth(nums1,nums2,i1,i2+k/2,k-k/2);
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	int n1=nums1.size(),n2=nums2.size(),i1=0,i2=0,n=n1+n2;
	if(n%2)
		return find_kth(nums1,nums2,0,0,n/2+1);
	else{
        cout<<find_kth(nums1,nums2,0,0,n/2)<<" "<<find_kth(nums1,nums2,0,0,n/2+1)<<endl;
        return (find_kth(nums1,nums2,0,0,n/2)+find_kth(nums1,nums2,0,0,n/2+1))/2;
    }		
}