encontrar un elemento en una matriz ordenada

Problema: Dada una matriz en la que se ordena cada fila y cada columna, escriba un método para encontrar un elemento en ella.

Es una pregunta de entrevista clásica, aquí está mi solución

boolean F(int[][] matrix, int hs, int he, int ws, int we) { if (hs > he || ws > we) return false; int m = (hs + he) / 2; int n = (ws + we) / 2; if (matrix[m][n] == t) { return true; } else if (matrix[m][n] m,j>n F(m + 1, he, n + 1, we); } else if (matrix[m][n] > t) { // very similar to previous part } } 

El tiempo de ejecución del algoritmo es log (m) + log (n). Estoy buscando un algoritmo que sea más eficiente o con un código conciso.

Al tener más comentarios, se me ocurre el siguiente código:

 // return target recurrence in the matrix int F(int[][] m, int rs, int re, int cs, int ce, int t){ int r1 = rs, r2 = re; int c1 = cs, c2 = ce; int r=0 , c = c1; while( r1 < r2 && c1 < c2 ){ // find the last element that =t c = FfirstGreater( r, c1, c2, t); if( c == -1) break; else{ r2 = r; c1 = c; }// else }// else }// while }// f 

Aquí está el enlace para las funciones F1 y F2. Encuentre el primer elemento en una matriz ordenada que sea mayor que el objective.

 void FlastLess(int s, int e, int t){ int l = s, h = e; while( l != h ){ int mid = (l+h)/2; if( mid >= t) high = mid - 1; else { if( high < t) low= mid + 1; else low = mid; } } void FfirstGreater(int s, int e, int t){ while(l < h){ mid = (l+h)/2; if ( mid <= t) low = mid+1; else high = mid; } } } 

Comienza en la esquina inferior izquierda de tu matriz. Luego vaya a la derecha hasta encontrar el número exacto (hecho), o hasta que encuentre un número que sea más grande.

Luego, vaya hacia arriba en la matriz hasta que encuentre el número exacto (hecho), o hasta que encuentre un número que sea demasiado pequeño.

Luego, nuevamente te mueves hacia la derecha, … y así sucesivamente hasta que encuentres el número o hasta que llegues al lado derecho o superior de tu matriz.

Las siguientes imágenes contienen algunos ejemplos, utilizando una tabla de Excel que muestra el número de destino en verde y la ruta que se sigue en amarillo.

enter image description here

enter image description here

En el último ejemplo buscamos 207, que no está en la matriz:

enter image description here

Este es solo el algoritmo. La encoding se deja para ti como ejercicio 🙂

EDITAR: Al comenzar en la fila inferior, una búsqueda binaria puede dar un mejor punto de partida. Para el rest del algoritmo, probablemente no importe.

Su algoritmo puede ser O (log m + log n), pero también da la respuesta incorrecta.

Supongamos que busca “4” en la siguiente matriz (donde la esquina superior izquierda es row = 0, col = 0):

 0 1 4 1 2 5 2 3 6 

Su algoritmo comienza mirando los 2 en el centro. Como 4 es mayor que 2 , procede a buscar en la misma fila (no allí), la misma columna (no allí) y la esquina inferior derecha (no allí). Whoops.

La restricción que ordena cada fila y columna es bastante débil. En particular, los elementos a lo largo de la diagonal podrían estar en cualquier orden.

Creo que el enfoque correcto es realizar una búsqueda binaria en la primera y la última columna para delimitar un rango de posibles filas. Luego haga una búsqueda binaria en la primera y la última de esas filas para reducir las posibles columnas. Etcétera.

No estoy seguro de cómo analizar el rendimiento de este …

Esto es lo que probaría. Dada una matriz A m por n , compare el valor X con la entrada A(m/2,n/2) (use pisos si es necesario).

Si A(m/2,n/2) == X , hecho.

Si A(m/2,n/2) < X , entonces hay 3 matrices más pequeñas para verificar:

 A(1:m/2, 1:n/2) A(1:m/2, n/2+1:n) A(m/2+1:m, 1:n/2) 

Si A(m/2,n/2) > X entonces hay 3 matrices más pequeñas para verificar:

 A(m/2:m, n/2:n) A(1:m/2, n/2+1:n) A(m/2+1:m, 1:n/2) 

Puede eliminar dos de ellos (no siempre) comparando el valor con el valor más pequeño en la matriz correspondiente (el valor superior izquierdo). Luego, recursivamente, intentas encontrar el valor en cada una de las matrices restantes.

La complejidad de esto es aproximadamente O((n*m)^0.8) .


Una matriz ordenada por filas y columnas es un caso especial de un cuadro joven . Hice una búsqueda en Google para buscar en un cuadro joven y encontré este artículo que ofrece 3 buenos enfoques (el primero (y el peor) de los cuales es el que describí anteriormente).

Para un algoritmo basado en la comparación, las consultas O (lg (m) + lg (n)) son óptimas.

Prueba

Para una consulta basada en la comparación, cada consulta solo puede tener dos resultados: verdadero o falso. Una extensión obvia de esto es que para N consultas puede tener como máximo 2 N resultados. Por lo tanto, al usar N consultas, solo puede ubicar elementos en una matriz con un máximo de 2 elementos N.

¿Cuántas consultas se requieren para buscar una matriz mxn? Solo resuelve por N.

2 N = mn
lg (2 N ) = lg (mn)
N = lg (m) + lg (n)

Por lo tanto, las consultas lg (m) + lg (n) son óptimas.

Consultas sin comparación

Esa prueba es concluyente, pero solo para consultas basadas en comparación. Si consulta la matriz de una manera que no implique comparaciones, puede obtener un tiempo casi constante si conoce la distribución de valores. No le daré un algoritmo, pero le sugiero que busque en Radix, ya que contiene el tipo de técnicas sin comparación que se requieren para superar el límite inferior de lg (m) + lg (n).

Al leer los comentarios anteriores, se me ocurrió este algoritmo. Básicamente, supongamos que al comenzar en la esquina superior derecha, la matriz se puede utilizar como BST con algunos “bucles” (no nos importan estos bucles).

 1 4 9 5 6 10 9 / \ 4 10 / \ / 1 6 \ / 5 

Este algoritmo es lo mismo que buscar en un BST y es realmente fácil de entender. El peor tiempo de ejecución es O (n + m).

 public static boolean search( int[][] matrix, int value ) { int rows = matrix.length; int columns = matrix[0].length; int i = 0; int j = columns - 1; while( i < rows && j >= 0 ) { if( matrix[i][j] == value ) { System.out.println( "Found at " + i + " " + j ); return true; } if( matrix[i][j] < value ) { j--; } else { i++; } } return false; } 
 boolean FindElem(int[][] mat, int elem, int M, int N) { int row = 0; int col = N-1; while (row < M && col >= 0) { if (mat[row][col] == elem) { return true; } else if (mat[row][col] > elem) { col--; } else { row++; } } return false; } 

Creo que su algoritmo no tiene los límites de tiempo que usted cree que tiene.

Para ver esto, por simplicidad supongamos que su cuadrícula es un cuadrado nxn (llamemos a este tamaño m). Si puedo obtener un límite temporal diferente de O (log n) en este caso, puedo argumentar que lo que tienes no debería ser correcto.

En particular, observe que en el peor de los casos, realiza tres llamadas recursivas a problemas que son de tamaño (n / 2) x (n / 2) = m / 4. Esto significa que tenemos la recurrencia

 T(1) = 1 T(m) = 3T(m / 4) + O(1) 

Usando el teorema maestro , el tiempo de ejecución para esta función sería O (m log 4 3 ) = O (n 2 log 4 3 ) = O (n log 4 9 ) ≈ O (n 1.5849625 ). Esto es ω (log n + log m); es decir, es asintóticamente estrictamente mayor.

Como muchas otras personas han publicado, hay varios algoritmos conocidos que se ejecutan en O (m + n) que se basan en caminar un paso en la dirección correcta en cada paso. En consecuencia, dejando de lado la corrección, no aconsejaría usar el algoritmo que ha publicado.

Los elementos dados en 2d array (be a [n] [m]) aumentan horizontal y verticalmente. Entonces, para la pregunta dada, primero debemos encontrar el índice del elemento. Entonces, si podemos encontrar el elemento de manera más rápida, podemos optimizar la solución. La pregunta es cómo lo encontramos de manera eficiente. Un enfoque es tomar el elemento medio de la matriz y verificar el elemento dado con él

si el elemento dado es menor que el elemento medio, nuestra solución está en la matriz a [0] [0] a a [n / 2] [m / 2] porque todos los elementos a la derecha y abajo son mayores que el medio (dado que el elemento dado es menos que el elemento medio) por lo que hemos reducido nuestro espacio de búsqueda de un [n] [m] a un [n / 2] [m / 2] que es un cuarto del tamaño original.

si el elemento dado es mayor que el elemento medio, entonces nuestra solución no está en las matrices a [0] [0] a a [n / 2] [m / 2] porque todos los elementos a la izquierda y arriba son menores que el medio (dado que el elemento dado es mayor que el elemento medio) por lo que nuestro espacio de búsqueda es una matriz total menos un [0] [0] a un [n / 2] [m / 2] que es tres cuartos del tamaño original. Matriz total menos un [0] [0] a un [n / 2] [m / 2] significa que habrá tres llamadas recursivas con un índice de matriz

 --------->a[0][m/2](start index) to a[n/2][m](end index) --------->a[n/2][0](start index) to a[n][m/2](end index) --------->a[n/2][m/2](start index) to a[n][m](end index) 

Ahora llama recursivamente la misma función en función de nuestro espacio de búsqueda.

La complejidad del tiempo de nuestra función será la siguiente. NOTA: En el tiempo, la función n representa el número total de elementos pero no el número de filas, como se mencionó .n = (no_of_rows) * (no_of_columns)

  _________________T(n/4) if given element is less than middle of the array. / / T(n)==========------------------- 1 if n=1 (if element found) \ \_________________3T(n/4) if given element is greater than middle element of array 

así que la función de tiempo de salida

T (n) = 3T (n / 4) o T (n) = T (n / 4)

 In worst case T(n)=3T(n/4) T(n)=3{3T(n/4)} T(n)=3power(i)T(n/(4)poweri) equation------> (1) 

Pero T (1) = 1 (suponiendo que el elemet dado se encuentra en una matriz)

 so n/(4power(i))=1 ====> n=2power(2*i) ====> n=2power(2*i) Talking log to base 2 on both sides (log[n])/2=i ====> i=log(sqrt(n)) 

sustituyendo la ecuación 1 obtenemos

 T(n)=3power(log[sqrt(n)]) T(n)∈ θ( nlog sqrt(3) ).. 

Que yo sepa, este es el algoritmo que toma un número mínimo de comparaciones.

Solución de JavaScript:

 //start from the top right corner //if value = el, element is found //if value < el, move to the next row, element can't be in that row since row is sorted //if value > el, move to the previous column, element can't be in that column since column is sorted function find(matrix, el) { var row = 0; //first row var col = matrix[0].length - 1; //last column while (row < matrix.length && col >= 0) { if (matrix[row][col] === el) { //element is found return true; } else if (matrix[row][col] < el) { row++; //move to the next row } else { col--; //move to the previous column } } return false; }