Всем Привет!

Попалась недавно задачка, к которой не могу подобрать алгоритм. ((
Когда уже мысли кончились, решил погуглить, но решения так и не обнаружил... хотя в некоторых статьях пишут, что оно существует ))

Задача такова, что необходимо найти медиану массива (неотсортированного конечно же).
Т.е. такое значение, которое после сортировки массива A[1...n]  будет равно:
элементу A[n / 2 + 1], при нечетном n и (A[n / 2] + A[n / 2 + 1]) / 2.0, при четном n.

НО.... самое интересное, что алгоритм должен быть линейным... 8)