Given an unsorted array of $n$ distinct elements, you want to find this set of $\log n$ elements: those at positions $1,2,4,8,16, \ldots, n/2$ if array were sorted. In other words, find the largest element, the second largest element, the fourth largest element, the eighth largest element and so on, terminating with the median element.
Consider that we have an algorithm to find $k$th smallest in an array of size $n$ using $\theta(n)$ time. Assume $n$ is a power of $2.$ How fast can you find all these $\log n$ elements? (Hint: Similar to binary search, we never have to worry about one of the subarray)
- $\Theta(\log n)$
- $\Theta(n)$
- $\Theta(n \log n)$
- $\Theta\left(n^{2}\right)$
