算法导论[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)