Tuesday, December 9, 2008

Kth smallest in merge of 2 sorted arrays

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

No comments:

Related Posts with Thumbnails