Vibhu wrote: > How wud you handle the case where > > X= {1, 3, 5, 7, 9} > Y= {2,4,6,8} > > What wud be timecomplexity ?
Here is a more general solution, covering cases like your example where X and Y have different dimensions: Let Nx be dimension of X, Ny dimension of Y (assume Nx >= Ny > 0) H = (Nx + Ny + 1) / 2 max = H IF (Ny == H) min = 1 else min = H - Ny END IF WHILE (max > min) k = (max + min) / 2 IF (X[k] < Y[H - k]) min = k + 1 ELSE max = k END IF END WHILE k = max IF (k == Nx) IF (Ny == H) median = (X[H] + Y[1]) / 2 ELSE median = X[1] ENDIF ELSE IF (k == 1) IF (Ny == H) median = (X[1] + Y[H]) / 2 ELSE median = X[1] END IF ELSE IF (X[k + 1] < Y[H - k + 1]) median = (X[k] + X[k + 1]) / 2 ELSE median = (X[k] + Y[H - k + 1]) / 2 END IF This also corrects an error in what I previously said. I didn't consider the case were the first element of X greater than the median is less than the first element of Y greater than the median. This is a binary search, thus O(log n) where n is Nx + Ny . For your example: min max k 1 5 3 1 3 2 3 3 3 the integer median is 5, the rational median is 5.5. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---