Programa de Python para encontrar la mediana en una 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:
 

# Python program to find median of matrix
# sorted row wise
  
from bisect import bisect_right as upper_bound
  
MAX = 100;
  
# Function to find median in the matrix
def binaryMedian(m, r, d):
    mi = m[0][0]
    mx = 0
    for i in range(r):
        if m[i][0] < mi:
            mi = m[i][0]
        if m[i][d-1] > mx :
            mx =  m[i][d-1]
      
    desired = (r * d + 1) // 2
      
    while (mi < mx):
        mid = mi + (mx - mi) // 2
        place = [0];
          
        # Find count of elements smaller than mid
        for i in range(r):
             j = upper_bound(m[i], mid)
             place[0] = place[0] + j
        if place[0] < desired:
            mi = mid + 1
        else:
            mx = mid
    print ("Median is", mi)
    return    
      
# Driver code
r, d = 3, 3
  
m = [ [1, 3, 5], [2, 6, 9], [3, 6, 9]]
binaryMedian(m, r, d)
  
# This code is contributed by Sachin BIsht

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.