Задача на поиск k-ого элемента по величине это.
Представьте себе отсортированный по возрастанию список чисел от 1 до n. Вам нужно найти минимум - это первый элемент, то есть k = 0. Вам нужно найти максимальный элемент - k = n-1. Медиану найти нужно - k = n/2 (целочисленное деление, дробная часть просто выкидывается). Вроде как все довольно просто...
А теперь представим что список не отсортирован, что там есть повторяющиеся элементы и т.д. Вот... Можно отсортировать список за O(n log(n)) например, а потом сделать выборки по индексам. А можно за O(n) просто найти...