Algorithm to Find Element of Order k in $\Theta(n)$

[evinda]

Hello! (Wave)

We are given the function [m]β-select(A)[/m] that gives as an output the position of the $\lfloor \frac{n}{\beta} \rfloor$-th element in time $\Theta(n)$, where $n$ is the number of elements of $A$.

I want to write an algorithm that returns the element of order $k$, $1 \leq k \leq n$ of $A$ in time $\Theta(n)$.

Could we maybe do it as follows?We pick $p = \beta-select(A)$ and this will be the position where the $\lfloor \frac{n}{\beta} \rfloor$-th element is and then we compare $p$ with $k$ and if $k < p$ ,we are looking for the desired element in the interval $ [1,p-1]$ , if it is greater then at the iterval $[p+1,n]$, otherwise we return $p$.

Or am I wrong?

 

[Future Bruno]

No, that looks like a correct approach. To summarize, your algorithm is as follows:1. Pick $p = \beta-select(A)$2. Compare $p$ with $k$: - If $k < p$, look for the desired element in the interval $[1, p-1]$. - If $k > p$, look for the desired element in the interval $[p+1, n]$.3. Return the element at position $k$.This algorithm runs in $\Theta(n)$ time.