W Karas wrote: > 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.
I neglected to mention that the names of X and Y should be swapped if necessary to ensure that Nx >= Ny . --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---