Encontrar el número en la matriz ordenada (Filas n Columnas) en O (log n)

Supongamos que tengo una matriz ( MxN ) que tiene ordenadas sus filas y columnas.

  1. Todos los elementos en cada fila están ordenados en orden creciente
  2. Todos los elementos en cada columna están ordenados en orden creciente
  3. Todos los elementos son enteros
  4. No se pueden hacer otras suposiciones

    Ejemplo:

    [1 5 8 20]

    [2 9 19 21]

    [12 15 25 30]

Tengo que encontrar si un número dado está presente en la matriz o no (Búsqueda básica). Tengo un algoritmo que ejecuta O(n)

 int row = 0; int col = N-1; while (row = 0) { if (mat[row][col] == elem) { return true; } else if (mat[row][col] > elem) { col--; } else { row++; } } 

Pero me pidieron una O(log (MxN)) == O(Log(n)) . ¿¿Algunas ideas??

La solución O (log (M * N)) no es posible para esta tarea.

Veamos una tarea simplificada: en matriz cuadrada “ordenada”, asum todos los elementos por encima de la diagonal secundaria (verde) menor que el número dado, todos los elementos debajo de la diagonal secundaria (rojo) mayor que el número dado, y sin suposiciones adicionales para los elementos en la diagonal secundaria amarillo).

enter image description here

Ni los supuestos originales de esta tarea, ni estas suposiciones adicionales nos dicen cómo los elementos en la diagonal secundaria están relacionados entre sí. Lo que significa que solo tenemos una matriz desordenada de N enteros. No podemos encontrar el número dado en la matriz no ordenada más rápido que O (N). Entonces, para el problema original (más complicado) con la matriz cuadrada, no podemos obtener una solución mejor que O (N).

Para una matriz rectangular, estire la imagen cuadrada y establezca los supuestos adicionales en consecuencia. Aquí tenemos sub-arreglos ordenados mínimos (N, M) de tamaño max (N, M) / min (N, M) cada uno. La mejor manera de buscar aquí es usar la búsqueda lineal para encontrar uno o varios sub-arreglos que puedan contener un valor dado, luego para usar la búsqueda binaria dentro de estos sub-arreglos. En el peor de los casos, es necesario realizar una búsqueda binaria en cada subarreglo. La complejidad es O (min (N, M) * (1 + log (max (N, M) / min (N, M)))). Entonces, para el problema original (más complicado) con la matriz rectangular, no podemos obtener una solución mejor que O (min (N, M) * (1 + log (max (N, M)) – log (min (N, M))) )

No es posible hacer mejor que O (n). Algunos chicos (hay al menos tres de ellos en esta página) creen que pueden hacerlo mejor, pero eso se debe a que sus algoritmos son incorrectos o porque no saben cómo calcular la complejidad de su algoritmo, por lo que intentan adivinarlo. Esta publicación de blog es muy buena y te explicará los errores de estos tipos.

Borrador de una prueba de que O (n) es óptimo: considere la siguiente matriz:

 1 2 3 4 5 6 … (n-2) (n-1) (n+1) 2 3 4 5 6 7 … (n-1) (n+1) (n+2) 3 4 5 6 7 8 … (n+1) (n+2) (n+3) … … … … … … … … … … (n-2) (n-1) … … … … … … … (2n-1) (n-1) (n+1) … … … … … … … 2n (n+1) (n+2) … … … … … (2n-1) 2n (2n+1) 

Si está buscando n en esta matriz, debe verificar al menos una vez para cada fila si n está en la fila porque n podría estar en cualquier fila. (La prueba no está completa pero esta es la idea)

Tienes que usar recursión para resolver este problema. Dada una matriz X y un número y, puede hacer una búsqueda binaria para y en la fila central de X y dividir la matriz en cuatro partes de manera que:

 A|B --- C|D 

todos los elementos en A son menores que y, todos los elementos en D son mayores que y, e y puede estar en B y C. Encuentra iterativamente y en B y C.

Desde altura (A) = altura (B) \ approx = altura (C) = altura (D), tamaño (X)> = 2 * (tamaño (B) + tamaño (C)). Entonces, la complejidad resultante es O (logn).

 def find(X,y): a,b = X.shape i = a /2 j = binsearch(X[i,:], y) if X[i,j]==y: return True else: return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y ) 

Dado que ambas filas y columnas están ordenadas, si miramos el primer elemento de cada fila, podemos encontrar cuál contiene el número que estamos buscando. Entonces, de nuevo, podemos aprovechar el hecho de que los elementos en cada fila están ordenados y encontrar ese número.
El algoritmo de búsqueda más rápido que conozco es Búsqueda Binaria, que tiene una complejidad de O (log n), por lo que la complejidad total será O (log m + log n).
Aquí hay un ejemplo, supongamos que estamos buscando 28:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
  • Hacemos una búsqueda binaria sobre los elementos de la primera columna (1, 11, 21, 31, 41) y encontramos que la fila es la tercera, porque su primer elemento es más pequeño que nuestro número, pero el primer elemento de la siguiente fila es más grande. Número de pasos: 2 (21, 31, encontrado)
  • Hacemos una búsqueda binaria nuevamente en la tercera fila (21, 22, 23, 24, 25, 26, 27, 28, 29, 30) y encontramos nuestro número. Número de pasos: 2 – 3 (25, 27 o 28, encontrados)