Проблема алгоритма выбора

Предположим, у вас есть массив A из n элементов, и вы хотите найти k элементов в A ближайшем к медиане A. Например, если A содержит 9 значений {7, 14, 10, 12, 2, 11, 29, 3, 4} и k = 5, то ответом будут значения {7, 14, 10, 12, 11}, поскольку медиана равно 10, и это пять значений в A, наиболее близких к значению 10. Приведите алгоритм чтобы решить эту проблему за время O (n).

Я знаю, что алгоритм выбора (глубокий выбор) является подходящим алгоритмом для этой проблемы, но я думаю, что он будет работать за время O (n * logn) вместо O ( п). Любая помощь будет принята с благодарностью :)