P1923 [Deep Basic 9.Example 4] Find the $k$-th Smallest Number

Given $n$ numbers $a_i$, output the $k$-th smallest among them. The smallest number is the $0$-th smallest. Please try not to use `nth_element` for this problem, because the main point is to practice divide and conquer algorithms.

The first line contains two integers, which are $n$ and $k$. The second line contains $n$ integers, and the $i$-th number is $a_i$.

Output one integer, the $k$-th smallest number.

For $100\%$ of the testdata, $1 \le a_i < {10}^9$, $1 \le n < 5 \times 10^6$, and $n$ is odd. Translated by ChatGPT 5