算法导论[Exercises 9.38 ]

Exercises 9.3-8

Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y. 

解: 

     int findMedian( X[1..n], Y[1..n])  // X 和 Y均为n个以排序的数组

1.  在 X,Y中取中位数,分别为m1,m2   O(1)
2. 若m1=m2, return m1
3. //不妨设m1<m2,则有floor(n/2)个数小于m1,floor(n/2)个数大约m2.中位数一定在m1~m2的区间上
4. return findMedian(X[floor(n/2)+1..n],Y[1..floor(n/2)])

     T(n) = T(n/2)+O(1)

     有master定理,可知复杂度为O(lgn)

转自：http://blog.csdn.net/pennyliang/article/details/1186683

《算法导论》的参考解答也给了解决方法，但是没有上面直观，具体见《Instructor's Manual》P135

想法有了，但是实现起来却并不容易，详见：http://blog.csdn.net/deepenxu/article/details/5978622

 又看到一个更简洁的：http://blog.csdn.net/hackbuteer1/article/details/7584838