W Karas wrote: > Manu wrote: > > Median of 2 combined array X[1...n] and Y[1...n] sorted. > > Find o(lgn) algo to find the median of all 2n elements in the 2 array. > > > > Well I tried and came up with this solution...if somebody has some > > other way plz tell..thnx in advance.... > > > > we cann't use merging and then find the median cause that will take > > o(n) time. > > > > let X be 1, 5, 6, 8 and Y be 2, 3, 4, 7 > > since X and Y are sorted find the middle of the two array ie 5(from X) > > and 3(from Y) > > now since 5 > 3 we choose the array to the right of 3 in Y ie 4, 7 for > > further processing (divide and conquer approach). which gives us 4 > > now 5 > 4 but since we are done with 2 steps ( as n=4 and lg4 =2 ) > > therefore 5 and 4 both are the median of the combined array. > > > > I guess this is one possible solution... > > I think the problem can be restated (using 1-base arrays) as: > > Find k where: > 1. 1 <= k <= n > 2. X[k] <= Y[n - k + 1] > 3. if k < n, X[k] >= Y[n - k] > > k can be found with a binary search. The (or a) median will be > (X[k] + Y[n - k + 1]) / 2 .
Oops. Find k where: 1. 1 <= k <= n 2. if k > 1, X[k] <= Y[n - k + 1] 3. if k < n, X[k] >= Y[n - k] --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
