Let $A[1..n]$ be an unsorted array, we want to find the $n/lgn$ intermidiate numbers in the array.

Namely the $(n/2)+1$ biggest number and the $(n/2) + 2$ biggest number and so on... until the $(n/2) + (n/lgn)$ biggrst number.

We are studing on the select algorithm and sortings.

I think it should go somehow with select algorithm as it has an efficiency of $\Theta(n)$

But its not that simple. As just making a loop will get us to \Theta(n^2)$

Just a remainder - the select algorithm compute nad finc the median of the medians in order to find the $i$ value in the array with run tie of $\Theta(n)$

Any suggestions?

Thank you.


You can find a $k$-th order statistic of an array using a selection algorithm in $\Theta(n)$ time. It means that you can also find the $k$ least (and the $k$ greatest) elements of an array in $\Theta(n)$ time by first finding the $k$-th ordering statistic and then comparing it with each element of an array. So in your case we can find $n / 2$ (median) and $n/2 + n / \log(n)$ order statistics and then find all suitable elements by scanning an array and comparing its elements with both statistics.


I think this question is almost the same idea Algorithm to identify top $\log n$ elements in $O(n)$ time So u can combine the idea of the solution there with what was suggested to u here to get a better performance.. i.e., -find the (n/2 + 1) element and the (n/2+ n/log n) element (ur max & min) that's O(n) -Scan the whole array to get what's in between, that's O(n) too -If it's required to output them sorted, that's O(n/logn * log(n/log n) )... still O(n) .... As I said this Q is a variation of the previous one, and so is my answer here just mapping the idea suggested there


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.