# Median of Two Sorted Arrays两个数组的中位数

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)).

Example1:

``````nums1 = [1, 3]
nums2 = [2]

The median is 2.0
``````

Example2

``````nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
``````

## 分析

``````[6 9 13 18] -> [# 6 # 9 # 13 # 18 #]  (N =4)
0 1 2 3 4  5 6  7 8	  (N'=9)

[6 9 11 13 18] -> [# 6 # 9 # 11 # 13 # 18 #]	(N=5)
0 1 2 3 4  5 6  7  8 9 10 11	(N'=11)
``````

``````A1: [# 1 # 2 # 3 # 4 # 5 #] (N1=5,N'=11)
A2: [# 1 # 1 # 1 # 1 #] (N2=4,N'=9)
``````

``````L1=A1[(C1-1)/2]=A1[(7-1)/2]=A1[3]=4;R1=A1[C1/2]=A1[7/2]=A1[3]=4;
L2=A2[(C2-1)/2]=A2[(2-1)/2]=A2[0]=1;R2=A2[C2/2]=A2[2/2]=A2[1]=1;
``````

### Solution1

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
//保证m小于n
if (m > n)
return findMedianSortedArrays(nums2,nums1);
int mid1,mid2,L1,L2,R1,R2,low=0,high=2*m;
while(low <= high)
{
//取较短的数组二分切
mid1 = (low+high)/2;
//
mid2 = m+n-mid1;
L1 = mid1==0?INT_MIN:nums1[(mid1-1)/2];
L2 = mid2==0?INT_MIN:nums2[(mid2-1)/2];
R1 = mid1==2*m?INT_MAX:nums1[mid1/2];
R2 = mid2==2*n?INT_MAX:nums2[mid2/2];

if (L1 > R2)
//数组1切的太靠右,需要向左切
high=mid1-1;
else if (L2 > R1)
//数组1切的太靠左,需要向右切
low=mid1+1;
else
return (max(L1,L2)+min(R1,R2))/2.0;
}
return -1;
}
};
``````

### Solution2

``````class Solution
{
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int k = (m + n) / 2;
//分奇偶判断
if((m+n)%2==0){
return (findKth(nums1,nums2,0,0,m,n,k)+findKth(nums1,nums2,0,0,m,n,k+1))/2;
}   else {
return findKth(nums1,nums2,0,0,m,n,k+1);
}

}
private:
double findKth(vector<int>& arr1, vector<int>& arr2, int start1, int start2, int len1, int len2, int k){
//保证数组1的长度比数组2短
if (len1 >len2) {
return findKth(arr2, arr1, start2, start1, len2, len1, k);
}
if (len1==0) {
return arr2[start2+k-1];
}
if (k==1) {
return min(arr1[start1], arr2[start2]);
}
//防止后面越界
int p1 = min(k/2, len1);
int p2 = k - p1;
if (arr1[start1+p1-1]<arr2[start2+p2-1])
{
//说明arr1的前p1个元素不在搜索范围内,丢弃
return findKth(arr1, arr2, start1+p1, start2, len1-p1, len2, k-p1);
}
else if(arr1[start1+p1-1]>arr2[start2+p2-1])
{
//说明arr2前p2的元素不在搜索范围内,丢弃
return findKth(arr1, arr2, start1, start2+p2, len1, len2-p2, k-p2);
}
else
{
//相等说明找到第k个元素
return arr1[start1+p1-1];
}
}
};
``````