算法导论[Exercises 9.3-8 ]

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

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

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