Если вы хотите найти реальную медиану, нет способа сделать это быстрее, чем в O(n) (в неструктурированном массиве) - потому что вам нужно пройти через все числа.Вы никогда не знаете, будет ли последнее число, которое вы найдете, медианой или нет.
Для некоторых алгоритмов существует эвристика, используемая для поиска медианы, что означает, что вы не получаете точную медиану, но у вас есть некоторый подход, как ее получить (с помощьюнекоторая вероятность) близка к реальной.
Например, для быстрой сортировки требуется некоторое медианное значение, но прохождение всего массива увеличит среднюю сложность до O(n^2) (и причина использования быстрой сортировки заключается в том, что она имеет среднюю сложностьO(n*log n). В таком случае вы можете, например, выбрать 10 случайных чисел и посчитать для них медиану. Тогда вы можете сказать, что реальная медиана, вероятно, будет примерно с этим значением.