There are two sorted arrays A and B 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)).
思路：1.可以转换为寻找第k小的数。if m+n is odd, find (m+n)/2 th is ok; if m+n is even ,find (m+n)/2 th and (m+n)/2+1 th, then get the average.
时间复杂度，在m+n的长度下每次剔除k/2, like binary search, 所以为O(lg(m+n));
2.另一种方法的时间复杂度是O(lgmin(n,m)) 还没看懂，待我我再看~~~~
class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { if(m==0 && n==0) return 0; int total = m+n; if(total%2==1) return findKth(A,0,m-1,B,0,n-1,total/2 + 1); else return (findKth(A,0,m-1,B,0,n-1,total/2)+findKth(A,0,m-1,B,0,n-1,total/2+1))/2; } double findKth(int A[], int al, int ah, int B[], int bl, int bh, int k){ int m = ah-al+1; int n = bh-bl+1; if(m>n) return findKth(B,bl,bh,A,al,ah,k); if(m==0) return B[k-1]; else if(k==1) return min(A[al],B[bl]); int pa = min(k/2,m); int pb = k-pa; if(A[al+pa-1]<B[bl+pb-1]) return findKth(A,al+pa,ah,B,bl,bh,k-pa); else if(A[al+pa-1]>B[bl+pb-1]) return findKth(A,al,ah,B,bl+pb,bh,k-pb); else return A[al+pa-1]; } };
上面代码写的很繁琐，需要改进。尤其是计算 al 和 ah时特别容易出错。 有啥好方法捏？？？？
Median of Two Sorted Arrays [hard]
原文：http://www.cnblogs.com/renrenbinbin/p/4339055.html