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