Search a 2D Matrix
Se te proporciona una cuadrícula de enteros matrix con m filas y n columnas, y un entero target. Cada fila está ordenada de forma creciente, y el primer valor de cada fila es mayor que el último valor de la fila anterior. Devuelve true si target aparece en la cuadrícula y false en caso contrario, en tiempo O(log(m × n)).
Función
- matrixinteger-2d-array
- la cuadrícula, dada como una lista de filas, ordenadas fila por fila
- targetinteger
- el valor que se debe buscar
- Devuelveboolean
- true si el objetivo está en la cuadrícula, false en caso contrario
Restricciones
1 ≤ m, n ≤ 100, dondem = matrix.lengthyn = matrix[i].length- Cada fila tiene la misma longitud
n. -104 ≤ matrix[i][j], target ≤ 104- Cada fila está ordenada en orden estrictamente creciente, y el primer valor de cada fila es mayor que el último valor de la fila anterior.
Ejemplos
- Entrada
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Salida
- true
- Explicación
- Leídos fila por fila, los 12 valores forman una lista ordenada. Una búsqueda binaria en las posiciones de 0 a 11 comprueba 21 en la posición 5 (demasiado pequeño), 33 en la posición 8 (demasiado grande) y después encuentra 26 en la posición 6.
- Entrada
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Salida
- false
- Explicación
- 16 iría después de 14, el último valor de la fila 0, y antes de 17, el primer valor de la fila 1. No hay nada entre ellos, así que 16 no está en la cuadrícula.
Para ir más allá
Supongamos que las filas pudieran tener longitudes diferentes y aun así estuvieran ordenadas de principio a fin. ¿Cómo convertirías una posición en una fila y una columna, y cuál sería el costo de búsqueda?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Lee la matriz fila por fila, de izquierda a derecha, como si fuera una lista larga. ¿Qué observas sobre el orden de los valores de esa lista?
Las dos reglas juntas significan que toda la matriz, leída fila por fila, es una lista ordenada de
m × nvalores. Puedes buscar en ella mediante búsqueda binaria sin tener que construirla nunca.Búsqueda binaria en las posiciones
0am × n - 1. La posiciónpestá en la filap / ny la columnap % n(división entera), así que cada paso lee una celda y descarta la mitad de las posiciones restantes.
Solución
Las dos reglas de ordenación juntas hacen que la cuadrícula, leída fila por fila, sea una lista ordenada de m × n valores. Busca en esa lista por posición mediante búsqueda binaria y convierte cada posición de nuevo en una fila y una columna con una división. Una cuadrícula de 100 por 100 necesita entonces como máximo 14 comparaciones en lugar de 10000.
Comprueba cada celda
Intuición
Compara cada celda con target y devuelve true si hay una coincidencia, false después de la última celda. Lee todas las celdas, así que es correcto para cualquier cuadrícula, esté ordenada o no. Nunca aprovecha el orden, por lo que una cuadrícula de 100 por 100 puede requerir hasta 10000 comparaciones.
Algoritmo
- Para cada fila de
matrix, examina cada valor en orden. - Si el valor es igual a
target, devuelvetrue. - Después de los bucles, devuelve
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseCamina desde la esquina superior derecha
Intuición
Desde la celda superior derecha, todos los valores a la izquierda son menores y todos los valores de abajo son mayores. Si la celda es mayor que target, la columna que está debajo también es mayor: avanza a la izquierda y descarta esa columna. Si es menor, la fila que está a su izquierda también es menor: baja y descarta esa fila.
En el primer ejemplo, 14 es menor que 26, así que baja hasta 30. 30 es mayor, así que avanza a la izquierda hasta 26: coincide. Cada paso elimina una fila o una columna, así que das como máximo m + n pasos: 200 para una cuadrícula de 100 por 100. El recorrido solo necesita que las filas y las columnas estén ordenadas, así que ignora la mitad de lo que ofrece esta cuadrícula.
Algoritmo
- Empieza en la fila
0y en la última columna. - Mientras la fila y la columna estén dentro de la cuadrícula, lee la celda.
- Si es igual a
target, devuelvetrue. - Si es mayor, muévete una columna a la izquierda; si es menor, muévete una fila hacia abajo.
- Cuando salgas de la cuadrícula, devuelve
false.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return FalseBúsqueda binaria en la cuadrícula aplanada
Intuición
Numera las celdas fila por fila: la fila 0 contiene las posiciones de 0 a n - 1, la fila 1 contiene las posiciones de n a 2n - 1, y así sucesivamente. Cada fila está ordenada y comienza por encima de donde terminó la fila anterior, por lo que los valores solo aumentan con la posición. Esa es una lista ordenada, y se puede aplicar la búsqueda binaria.
Nunca construyes la lista. La posición p está en la fila p / n y la columna p % n, usando división entera. En el primer ejemplo, n = 4, así que la posición 6 está en la fila 1, columna 2, que contiene 26. Cada comparación reduce a la mitad las posiciones que podrían contener target: como máximo 14 para 10000 celdas, con dos índices de memoria adicional.
Algoritmo
- Sean
mynel número de filas y columnas, y establecelo = 0,hi = m × n - 1. - Mientras
lo ≤ hi, tomamida medio camino entre ellos. - Lee
value = matrix[mid / n][mid % n]. - Si
valuees igual atarget, devuelvetrue. Si es menor, establecelo = mid + 1; de lo contrario, establecehi = mid - 1. - Cuando termine el bucle, devuelve
false.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
Errores comunes y casos límite
- Dividir por el número de filas en lugar de por el de columnas. La posición
pestá en la filap / n; si se usamen su lugar, el código funciona en cuadrículas cuadradas y falla con 3 filas y 4 columnas. - En la versión con dos búsquedas, no manejar
targetcuando es menor quematrix[0][0]. Ninguna fila empieza en ese valor o por debajo, y un índice de fila de-1llega a la segunda búsqueda. - Iterar con
lo < hicuandohies inclusivo. Una cuadrícula de 1 por 1 que contienetargetdevuelvefalse, porque el bucle nunca se ejecuta. - En Lua y R, olvidar el cambio a índices basados en 1: la posición
pestá en la filap / n + 1, columnap % n + 1.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Buscar en una matriz 2D?
La búsqueda binaria en la cuadrícula aplanada se ejecuta en tiempo O(log(m × n)) y espacio O(1): como máximo 14 comparaciones para 10000 celdas. Como log(m × n) = log m + log n, equivale a buscar la fila y después buscar dentro de ella.
¿Deberías usar el recorrido por la esquina superior derecha o la búsqueda binaria?
El recorrido por las esquinas requiere O(m + n) pasos y solo necesita que las filas y las columnas estén ordenadas, por lo que también resuelve la variante en la que una fila puede empezar por debajo del final de la fila anterior. Cuando cada fila empieza por encima del punto donde termina la anterior, como aquí, la búsqueda binaria es más rápida.
¿También es correcto hacer dos búsquedas binarias, una para la fila y otra dentro de ella?
Sí. Busca mediante búsqueda binaria en la primera columna la última fila cuyo primer valor sea como máximo target y, después, busca en esa fila mediante búsqueda binaria. Se ejecuta en O(log m + log n), el mismo límite. La búsqueda única realiza el mismo trabajo con un bucle y menos casos límite.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def searchMatrix(matrix, target):
# Escribe el código aquíPrueba #1
Prueba #2
Argumentos
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Salida Esperada
true