title: Suggestion to search algorithm that runs in Θ(n)?
body: <p>Let A[0..n − 1] be an array of distinct integers. The integer with rank k in A is the k’th largest integer among the integers in A. The median of A is the integer in A with rank b(n − 1)/2c. How might an algorithm look, that given a k finds the integer with rank k in A in Θ(n) time?</p>