Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm

Question

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.

Answer 1

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.

Answer 2

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