$k$th Largest Algorithm in a range $[k, k+c]$

Question

The well-known algorithm for computing the $k$-th largest element in an unsorted array of size $n$ runs in $O(n)$ time.

How about for a range $[k, k+c]$, where $c$ is not necessarily independent of $n, k$? The obvious "brute-force" algorithm is to find the $k$th largest using the original $O(n)$-time algorithm, then the $k+1$-th largest the same way, ..., find the $k+c$-th largest (and also, the algorithm outputs these in sorted order). However, this takes $O(nc)$ time, and $c$ can possibly be $\Theta(n)$, which can lead to an $O(n^2)$ algorithm. In this case, we could have just sorted the array and extracted the elements, which takes $O(n \log n)$ time.

Is there a better (known) way of doing this? I can't find any references online.

Answer 1

Step 1. Use QuickSelect to find the $k$th largest number in the array. Call it $x$.

Step 2. Use QuickSelect to find the $k+c$th largest number in the array. Call it $y$.

Step 3. Find all elements in the array that are at least $x$ and at most $y$. This can be done by simply iterating over the array and comparing each element to $x$ and $y$.

Each step can be done in $O(n)$ time. Therefore, the total running time is $O(n)+O(n)+O(n) = O(n)$ time.