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... --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
