Finding the Median in Linear Time Pick randomly a number a from A = {a1, ..., an}. Partition the n ...

Please Visit: http://ift.tt/1ajReyV

Finding the Median in Linear Time

Pick randomly a number a from A = {a1,

..., an}.



Partition the n numbers into two sets:



S - all the numbers smaller than a

B - all the numbers bigger than a





If |S| = K-1 then a is the required

K-median. Return a

If |S| < K-1 then the K-median lies

somewhere in B. Call recursively to

FindKMedian( B, K - |S| - 1 )



Else, call recursively to FindKMedian( S, K ).

http://ift.tt/1qQXUjF

http://ift.tt/1oqw1u7

Finding the Median in Linear Time

from Public RSS-Feed of Jeffery yuan. Created with the PIXELMECHANICS 'GPlusRSS-Webtool' at http://gplusrss.com http://ift.tt/1qQXUjK

via LifeLong Community