# Median solved by 465

Feb. 21, 2014, 5:36 p.m. by Rosalind Team

Topics: Sorting

## Problem

The task is to implement a linear time randomized algorithm for the selection problem.

Given: A positive integer $n \le 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$, a positive number $k \le n$.

Return: The $k$-th smallest element of $A$.

## Sample Dataset

11
2 36 5 21 8 13 11 20 5 4 1
8


## Sample Output

13


Please login to solve this problem.