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