Search a number

Question

Given n numbers, design an algorithm to find the smallest $n^{\frac{2}{3}}$numbers, in sorted order. (Assume $n^{\frac{2}{3}}$ is an integer.)

I don't understand this question. Can I simply $x = n^{\frac{2}{3}}$ and fetch the $A[x]$?

Answer 1

That would only give you the $x$-th number. What the question is asking is to return a sorted list containing the smallest $n^{\frac{2}{3}}$ numbers of the input.

For example if $n=8$ and the input consists of the numbers $\langle 4, 3, 6, 1, 2, 5, 8, 7\rangle$ then you need to return the $x = n^\frac{2}{3} = 4$ smallest numbers in sorted order, i.e., $\langle 1, 2, 3 ,4 \rangle$.