Idea:
The solution goes like this
A[1...m] B[1...n]
1. Compare A(k/2) and B(k/2)
if A(k/2) < B(k/2)
So the kth smallest can't be in A[1..k/2] and B[k/2+1 .. n]. A[1...k/2] < Kth smallest < B[k/2+1 ... n]
So we discard these elements. And now search for the k/2th smallest number in the 2 remaining arrays
if the reverse is true we do the same operation but with B and A swapped
2. if m<k
we discard B[1...k-m-1]
and look for (m+1)th (= k-(k-m-1)) smallest element in remaining arrays
Tuesday, December 9, 2008
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment