[zOdmin]

Не совсем по языку вопрос, скорее поиск алгоритма.

Возможно ли за O(N) найти число, которое было бы меньше ровно половины чисел из не отсортированного массива чисел, в котором четное количество элементов и никакие числа не равны?

Например, для массива [9,7,1,8] это число будет 7.5