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 . --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
