Selection (deterministic & randomized): finding the median in linear time

More generally, we solve the problem of finding the kth smallest out of an unsorted array of n elements. 4.2 The problem and a randomized solution ... of them (those groups whose median is ≤p) at least three of the five elements are ≤p. Therefore, the total numberof elements ≤p is at least 3⌈g/2⌉≥3n/10. Similarly, the total number ... ................
................