Selection by Sampling distribution: R: 000 sample a small set R, selection in R by sorting roughly concentrated,but not good enough
Selection by Sampling distribution: sample a small set R, selection in R by sorting R: roughly concentrated, but not good enough
Selection by Sampling distributions: C Find such d and u that: ●LetC={xES|d≤x≤. ●The median is in C. .C is not too large (sort C is linear time)
Selection by Sampling distributions: d u Find such d and u that: • C is not too large (sort C is linear time). C • Let C = {x S | d ⇤ x ⇤ u}. • The median is in C. d u