Programa Javascript para encontrar la mediana en la array ordenada por filas

Nos dan una array ordenada por filas de tamaño r*c, necesitamos encontrar la mediana de la array dada. Se supone que r*c siempre es impar.
Ejemplos: 

Input : 1 3 5
        2 6 9
        3 6 9
Output : Median is 5
If we put all the values in a sorted 
array A[] = 1 2 3 3 5 6 6 9 9)

Input: 1 3 4
       2 5 6
       7 8 9
Output: Median is 5

Método simple : el método más simple para resolver este problema es almacenar todos los elementos de la array dada en una array de tamaño r*c. Luego, podemos ordenar la array y encontrar el elemento mediano en O(r*clog(r*c)) o podemos usar el enfoque discutido aquí para encontrar la mediana en O(r*c). El espacio auxiliar requerido será O(r*c) en ambos casos.
Un enfoque eficiente para este problema es utilizar un algoritmo de búsqueda binaria . La idea es que para que un número sea la mediana debe haber exactamente (n/2) números que sean menores que este número. Entonces, tratamos de encontrar el conteo de números menor que todos los números. A continuación se muestra el algoritmo paso a paso para este enfoque: 
Algoritmo :  

1. Primero, encontramos los elementos mínimo y máximo en la array. El elemento mínimo se puede encontrar fácilmente comparando el primer elemento de cada fila y, de manera similar, el elemento máximo se puede encontrar comparando el último elemento de cada fila.
2. Luego usamos la búsqueda binaria en nuestro rango de números de mínimo a máximo, encontramos la mitad del mínimo y el máximo y obtenemos un conteo de números menor que nuestra mitad. Y en consecuencia cambiar el mínimo o máximo.
3. Para que un número sea la mediana, debe haber (r*c)/2 números más pequeños que ese número. Entonces, para cada número, obtenemos el conteo de números menores que usando upper_bound() en cada fila de la array, si es menor que el conteo requerido, la mediana debe ser mayor que el número seleccionado, de lo contrario, la mediana debe ser menor o igual al número seleccionado.

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

<script>
  
// Javascript program to find median 
// of a matrix sorted row wise
  
  
// Function to find median 
// in the matrix
function binaryMedian(m, r, c)
{
  var max = -1000000000;
  var min = 1000000000;
  
  for(var i = 0; i < r; i++)
  {
    // Finding the minimum 
    // element
    if(m[i][0] < min)
      min = m[i][0];
  
    // Finding the maximum 
    // element
    if(m[i] > max)
      max = m[i];
  }
  
  var desired =  parseInt((r * c + 1) / 2);
  while(min < max)
  {
    var mid = min + parseInt((max - min) / 2);
    var place = 0;
    var get = 0;
  
    // Find count of elements 
    // smaller than mid
    for(var i = 0; i < r; ++i)
    {
        var tmp = GetRow(m, i);
        for(var j = tmp.length; j>=0; j--)
        {
            if(tmp[j] <= mid)
            {
                get = j+1;
                break;
            }
        }
  
      // If element is not found 
      // in the array the binarySearch() 
      // method returns (-(insertion_
      // point) - 1). So once we know 
      // the insertion point we can 
      // find elements Smaller than 
      // the searched element by the 
      // following calculation
      if(get < 0)
        get = Math.abs(get) - 1;
  
      // If element is found in the 
      // array it returns the index(any 
      // index in case of duplicate). So 
      // we go to last index of element 
      // which will give  the number of 
      // elements smaller than the number 
      // including the searched element.
      else
      {
        while(get < GetRow(m, i).length && 
              m[i][get] == mid)
          get += 1;
      }
  
      place = place + get;
    }
  
    if (place < desired)
      min = mid + 1;
    else
      max = mid;
  }
  return min;
}
  
function GetRow(matrix, row)
{
  var rowLength = matrix[0].length;
  var rowVector = Array(rowLength).fill(0);
  
  for (var i = 0; i < rowLength; i++)
    rowVector[i] = matrix[row][i];
  
  return rowVector;
} 
    
// Driver code
var r = 3, c = 3;
var m = [[1,3,5], 
            [2,6,9], 
            [3,6,9]];
document.write("Median is " + 
                   binaryMedian(m, r, c));
  
  
// This code is contributed by rutvik_56.
</script>

Producción: 
 

Median is 5

Complejidad temporal : O(32 * r * log(c)). La función de límite superior tomará el tiempo log(c) y se realiza para cada fila. Y dado que los números tendrán un máximo de 32 bits, la búsqueda binaria de números de mínimo a máximo se realizará en un máximo de 32 operaciones (log2(2^32) = 32). 
Espacio Auxiliar : O(1) 
 

Consulte el artículo completo sobre Encontrar la mediana en la array ordenada por filas para obtener más detalles.