Encontrar la mediana de una array sin ordenar en tiempo lineal usando C++ STL

Dada una array sin ordenar arr[] que tiene N elementos, la tarea es encontrar la mediana de la array en complejidad de tiempo lineal.

Ejemplos:

Entrada: N = 5, arr[] = {4, 1, 2, 6, 5}
Salida: 4
Explicación:
Dado que N = 5, que es impar, la mediana es el tercer elemento en la array ordenada.
El tercer elemento en el arreglo ordenado[] es 4.
Por lo tanto, la mediana es 4.

Entrada: N = 8, arr[] = {1, 3, 4, 2, 6, 5, 8, 7}
Salida: 4.5
Explicación:
Dado que N = 8, que es par, la mediana es el promedio de 4th y 5th elemento en la array ordenada.
El cuarto y quinto elemento en la array ordenada es 4 y 5 respectivamente.
Por tanto, la mediana es (4+5)/2 = 4,5.

Enfoque: la idea es utilizar la función nth_element() en C++ STL .

1. Si el número de elementos en la array es impar, busque el (N/2)-ésimo elemento usando la función nth_element() como se ilustra a continuación y luego el valor en el índice (N/2) es la mediana de la array dada.
   

   nth_element(arr.begin(), arr.begin() + N/2, arr.end())

2. De lo contrario, encuentre el elemento (N/2) y ((N – 1)/2) usando la función nth_element() como se ilustra a continuación y encuentre el promedio de los valores en el índice (N/2) y ((N – 1) /2) es la mediana de la array dada.
   

   nth_element(arr.begin(), arr.begin() + N/2, arr.end())
   nth_element(arr.begin(), arr.begin() + (N – 1)/2, arr.end( ))

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function for calculating
// the median
double findMedian(vector<int> a,
                  int n)
{
  
    // If size of the arr[] is even
    if (n % 2 == 0) {
  
        // Applying nth_element
        // on n/2th index
        nth_element(a.begin(),
                    a.begin() + n / 2,
                    a.end());
  
        // Applying nth_element
        // on (n-1)/2 th index
        nth_element(a.begin(),
                    a.begin() + (n - 1) / 2,
                    a.end());
  
        // Find the average of value at
        // index N/2 and (N-1)/2
        return (double)(a[(n - 1) / 2]
                        + a[n / 2])
               / 2.0;
    }
  
    // If size of the arr[] is odd
    else {
  
        // Applying nth_element
        // on n/2
        nth_element(a.begin(),
                    a.begin() + n / 2,
                    a.end());
  
        // Value at index (N/2)th
        // is the median
        return (double)a[n / 2];
    }
}
  
// Driver Code
int main()
{
    // Given array arr[]
    vector<int> arr = { 1, 3, 4, 2,
                        7, 5, 8, 6 };
  
    // Function Call
    cout << "Median = "
         << findMedian(arr, arr.size())
         << endl;
    return 0;
}

Median = 4.5

Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)