I am having trouble figuring this out. How do I use this algorithm?

Question

Say that you are given an algorithm X that finds the median (the element that is smaller than roughly n/2 of the elements and larger that the other half) in Order(n) time. How would I use algorithm X to find for a given k the k-largest element?

Answer 1

Start with the whole array as set Q.
Use algorithm X to get the median M of Q.
Set a = [size of Q]/2.
If a = k, stop; M is your answer.
If a > k, set Q = the values less than M, otherwise set Q = the values greater than M.
Repeat.

This algorithm is a bit off because when [a > k], the comparison [a <=> k] is subsequently invalid. But you get the gist of it. Use X in a binary search mode.

Answer 2

Re you sure you want the kth largest element, or the kth element when the array is sorted in ascending order?
For the second case, proceed as follows.

1) find median.
2) Now create a new array from original array such that all the elements in are on the same half that of k. i.e if k is greater than the median, create an array of the elements which are greater than the median elements, or else create an array in which elements are less than the median element.
3) if k is greater than (n/2), k = k - (n/2).
4) continue untill k is zero.

This approch will be of O(nlogn).

Answer 3

This is exactly what a binary search does, but it operates on a sorted list. You would use it in the same way you do binary search but rather than operating on the middle of the list (same as the median for a sorted list), you operate on the median.