Find a number in unsorted array larger than the median number with complexity better than O(1/2n+1)

Question

Given an unsorted array with N positive integers.

Find a number in the array, that is larger than the median number in the array. for example if the array contains numbers between 1-10, the median is 5, so 6+ is acceptable.

This can be done with O(1/2n+1) which is less than O(N), by looping through 51% of the array and getting the maximum number.

But how can you do it with a better complexity?

Answer 1

That's actually untrue. For example, if the array contains 9 occurrences of the number 1 and a single 2. Selecting 51% of the data will likely have a maximum value of 1, which is equal to the median of 1 - not greater.