转自：http://blog.unieagle.net/2012/10/04/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Amedian-of-two-sorted-arrays/
根据文章中的算法，每次能够剔除掉 k/2 个元素，每次减小一半，而 k= (m+n)/2 ，所以最后的复杂度是 log k = log(m+n)，符合题意。
这个问题可以用二分来解，算法有点复杂。
-
先说临界情况
- A为空或者B为空
直接在非空数组中找第k大的数即可。O(1) - 找最小的数，k==0的情况，也简单，比较两个数组最开头的元素，谁小就是谁
-
然后就是比较复杂的情况，假设寻找目标target是下标为k的数。
- 如果A[ka-1] >= B[kb-1]
说明在B前端的kb个数中，不可能出现我们要寻找的目标。
为什么呢？
假如A一共有m个数，B一共有n个数。
那么target(下标是k)后面有且只有n + m – 1 – k个数；
但是B[kb-1]在B中已经排在n – kb个数之前，加上A中的m – ka + 1(A[ka-a])，也就是说在排序后的整体数组中排在B[kb-1]之后的数，至少有n – kb + m – ka + 1 = n + m – k + 1个。
由于n + m – k + 1 > n + m – k – 1，所以B前端kb个数都不可能是target。
所以此时可以将问题转化为，在A[0,...,m-1]和B[kb,...,n-1]中，寻找下标为k – kb的数。 - 否则，A[ka-1] < B[kb-1]
同上，可以剔除A前端的ka个数。
那么意味着在排好的数组中，在目标数之前，一共有k个比目标更小的数。
将k分成两份，一份在A的前端，一份在B的前端。这里其实将k怎么分配是一个可以讨论的问题，但是平分k可以得到平均最快的效果。
设k = ka + kb，（k是偶数简单，k是奇数的话，剩下那一个随便放在两个数组中哪一个中都可以）
这里可以列出来我们想要的效果：
k=1 —-> ka = 1, kb = 1
k=2 —-> ka = 1, kb = 1
k=3 —-> ka = 1, kb = 1. [+1，表示还有一个元素，可以随意分配在ka或者kb中，只要不越界]
k=4 —-> ka = 2, kb = 2
k=5 —-> ka = 2, kb = 2. [+1]
已经可以看出来规律了，这个造成了下面代码中比较复杂的部分，这些细节消耗的时间不少啊。
然后就是主要逻辑：
这样循环下去，就能以二分的速度找到目标。
这个问题不仅要找到第k大的数，当C是偶数的时候，还要找到第k+1个数，取两者均值。
2.第二个方法是类似于找第Kth个数：注意没有getV方法会报错。
注意换数组查找的上下界确定，下界表示即使另一数组全排在前面，上界是下标自然的限制；
double findMedian(int a[],int b[],int l,int r,int m,int n)
{
if ( l > r) return findMedian(b,a,max(0,(m+n)/2-m),min(n,(m+n)/2),n,m);
int i= (l+r)/2;
int j=(m+n)/2-i-1;
if ( getV(a,m,i)< getV(b,n,j) )
return findMedian(a,b,i+1,r,m,n);
else if ( getV(a,m,i)> getV(b,n,j+1))
return findMedian(a,b,l,i-1,m,n);
else
{
if( (m+n)&1 ==1 )
return getV(a,m,i);
else
return (getV(a,m,i)+max(getV(b,n,j),getV(a,m,i-1)))*0.5;
}
}
double findMedianSortedArrays(int a[],int m,int b[],int n)
{
if ( m < n )
return findMedian(a,b,0,m-1,m,n);
else
return findMedian(b,a,0,n-1,n,m);
}
int getV(int a[],int m,int i)
{
if (i<0) return -10000000;
if (i>=m) return 10000000;
else return a[i];
}
3.第三种方法是二分 D&C, 去A的中位数和B的中位数，如果A[i]<=B[j]，那么应带在A[i]右边和B[j]左边寻找，理由是A[i]最大的序号也小于最后的median，B[j]的序号
最小也不会超过median。重点在于首先A[i[和B[j]不要去除，同时取出的长度应当相等。另外麻烦的地方在一些边界条件的处理。还有，要保证A总是短于B。
double MedianOfFour (int a, int b, int c, int d)
{
int minValue = min (d, min (a, min (b,c) ) );
int maxValue = max (d, max (a, max (b,c) ) );
return (a + b + c + d - minValue - maxValue) / 2.0 ;
}
double MedianOfThree (int a, int b, int c)
{
int minValue = min (a, min (b,c) ) ;
int maxValue = max (a, max (b,c) ) ;
return (a + b + c - minValue - maxValue);
}
//constraint : n <= m
double MedianSortedArrays (int A[MAX], int n, int B[MAX], int m)
{
//base case # 1
if ( n == 1 )
{
if ( m == 1 )
return (A[0] + B[0]) / 2.0;
if ( m % 2 == 1)
return ( B[m/2] + MedianOfThree (A[0], B[m/2-1], B[m/2+1]) ) / 2.0 ;
else
return MedianOfThree ( A[0], B[m/2-1], B[m/2] );
}
//base case # 2
if ( n == 2 )
{
if ( m == 2 )
return MedianOfFour (A[0], A[1], B[0], B[1]);
if ( m % 2 == 1 )
return MedianOfThree ( B[m/2], min(A[0], B[m/2+1]), max (A[1], B[m/2-1]) ) ;
else
return MedianOfFour ( B[m/2-1], B[m/2], min(A[0], B[m/2+1]), max(A[1], B[m/2-2]) );
}
int minRemoved, idxA = n/2 , idxB = m/2 ;
if ( A[idxA] < B[idxB] )
{
if ( n % 2 == 0 ) --idxA; //for even number of elements --idxA points to lower median of A[]
minRemoved = min ( idxA, m - idxB - 1) ;
return MedianSortedArrays ( A + minRemoved, n - minRemoved, B, m - minRemoved);
}
else
{
if ( m % 2 == 0 ) --idxB; //for even number of elements --idxB points to lower median of B[]
minRemoved = min ( n - idxA - 1, idxB) ;
return MedianSortedArrays ( A, n - minRemoved, B + minRemoved, m - minRemoved);
}
}
三种方法中第二种明显较简洁，但缺点是在一个数组中查找，如果失败，在另一个中查找，所以效率可能稍低。
我的思路与方法二类似：在数组A中取中位数A[i],然后在B中二分查找A[i]，这样可以确定A[i]排在median前还是后，从而缩小区间，但缺点是查找到A[i]后要log(Blen)才可以确定下一区间，而第二种方法只要在常数时间就可以确定下一区间，复杂度低了一个级别。
这里有个更好的总结：http://www.geeksforgeeks.org/median-of-two-sorted-arrays/