Buscar una matriz 2D ordenada

M es una matriz 2D de enteros (nXm) que están ordenados en fila y columna. Escribe una búsqueda de función (int s) que devuelve la ubicación exacta del número o nulo. ¿Cuál sería la forma más eficiente de hacerlo?

init: m [1..n (filas), 1 …. m (columnas)]

i = n, j = 1

Comience en (i, j):

STEP 1) if the value equals m(i,j) return (i,j) STEP 2) if the value > m(i,j) go to step 1 with j+=1 STEP 3) else go to step 1 with i-=1 

en cada paso si j o i está fuera de límite devuelve no-solución.

La complejidad de esta solución es O (n + m) en caso de que n = m la complejidad sea O (n)

Me pregunto si hay una solución de registro (n * m) como en la búsqueda binaria

EDITAR otra posible solución:

 STEP 1)take the middle (n/2,m/2) of the matrix and compare it to the value STEP 2) if the value equals m(i,j) return (i,j) STEP 3) if the value is higher you can get rid from the first quarter STEP 4) if the value is lower you can get rid from the forth quarter STEP 5) split the 3 other quarters to 2, a rectangle and a box, send those both items to step 1 in a recursive manner 

No estoy seguro acerca de la eficiencia de esta solución: si R = N * M entonces T (R) = T (R / 2) + T (R / 4) + O (1)

Digamos que tenemos

 1 2 5 7 2 4 7 9 3 5 8 9 5 6 9 9 

Ahora buscamos 6. Puedes ver que hay una “tira” que va de la parte superior derecha (5 7) a la inferior izquierda (5 6 7) donde los valores menores que 6 cambian a valores mayores que 6 (“tira” marcada con *):

 1 2 5*7 2 4*7 9 3 5*8 9 5*6*9 9 

Entonces un algoritmo sería:

  • compruebe si la parte superior izquierda es más grande que su número -> return null
  • compruebe si la esquina inferior derecha es más pequeña que su número -> return null
  • ve la diagonal desde arriba a la izquierda abajo a abajo a la derecha hasta que encuentres “la tira”
  • sigue la tira en ambas direcciones, hasta que encuentres el número.

Considere la entrada a continuación:

1 2 3

4 5 6

7 8 9

El algoritmo de DuduAlul no encontraría la ubicación del número 4, por ejemplo.

Acabo de abrir el bloc de notas y escribí un poco, pero creo que esto lo hará en el tiempo O (x), donde x es el índice más grande entre n y m. El peor caso para este algoritmo sería que el término de búsqueda fuera igual al término más grande en el conjunto, para el cual este método recorrerá n o m (el que sea mayor) veces. Si eso va a ser algo común, uno solo puede comenzar desde la parte inferior derecha en lugar de la esquina superior izquierda, y disminuir las indicaciones en lugar de incrementarlas.

 int[] SearchArray(int s, int[][] array) { int i = 0; int j = 0; int n = array.GetLength(0); int m = array.GetLength(1); if (s > array[n][m]) return null; while (i < n && j < m) { if (array[i][j] > s) return null; if (array[i][j] == s) return new int[]{i,j}; try { if (array[i+1][j+1] < s) { i++; j++; } else if (array[i+1][j] > array[i][j+1]) if (array[i+1][j] < s) i++; else j++; else if (array[i][j+1] > array[i+1][j]) if (array[i][j+1] < s) j++; else i++; else if (array[i+1][j] == array[i][j+1]) if (n < m) i++; else j++; } catch(IndexOutOfRangeException e) { if (i == n-1) j++; if (k == m-1) i++; } } } 

Editado para optimización y formateo