Búsqueda eficiente en matriz ordenada MxN

Clase 31 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Qué es "Searching in a 2D Array Matrix"?

Cuando nos enfrentamos al problema de buscar un valor objetivo en una matriz de M por N enteros, estamos hablando de un algoritmo que debe ser eficiente y asegurar que el objetivo se encuentre de manera óptima. Este tipo de matrices tiene dos características fundamentales:

Orden por filas: Cada fila en esta matriz está ordenada de manera ascendente de izquierda a derecha.
Interrelación entre filas: El primer entero de cada fila es mayor que el último entero de la fila anterior.

Por ejemplo, si tenemos una matriz donde las filas son [1, 3, 5, 7], [10, 11, 16, 20], y [23, 30, 34, 60], podemos notar que no solo cada fila está ordenada, sino que también el último número de una fila es menor que el primer número de la siguiente.

¿Cómo aplicar la estrategia de búsqueda?

La manera más sencilla y directa de encontrar un número sería recorrer toda la matriz, lo cual resulta en una complejidad de O(N²). Sin embargo, podemos mejorar significativamente esta eficiencia.

¿Cómo aprovechar las propiedades de la matriz?

División lógica de la matriz: Al tratar con matrices que cumplen con las propiedades mencionadas, podemos aplicar estrategias de búsqueda que aprovechan la ordenación existente.
Búsqueda binaria: Implementar una búsqueda binaria permite reducir el tiempo de búsqueda significativamente. La idea es reducir la cantidad de elementos por revisar a la mitad en cada paso, logrando así una búsqueda más eficiente.

Esta es la base para optimizar tiempo y recursos en la búsqueda de un valor específico.

¿Qué desafíos pueden surgir?

Comprensión del problema: Antes de implementar soluciones, es crucial entender las propiedades de la matriz y cómo se relacionan las filas entre sí.
Implementación correcta: Aplicar algorítmicamente las propiedades de la matriz requiere cuidado para no romper la lógica ordenada en cada iteración.
Pruebas y ajustes: Finalmente, es esencial someter el algoritmo a pruebas con diferentes datos de entrada para garantizar que funcione correctamente en todos los casos.

Este análisis no solo facilita la construcción de un algoritmo eficiente, sino que nos prepara para enfrentar problemas similares en el futuro.

¡Sigue esforzándote por encontrar nuevas soluciones y desafíos! La práctica y la curiosidad son tus mejores aliados en este viaje de aprendizaje.

Carlos Damián Loaiza Artunduaga

student•

Me enorgullese decir que logré hacer la solución yo mismo, también lo probé en Leetcode y funciona:

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    i, d = 0, m * n - 1
    while i <= d:
        mi = i + (d - i) // 2
        fmi = mi // n
        cmi = mi % n
        if target == matrix[fmi][cmi]:
            return True
        if target < matrix[fmi][cmi]:
            d = mi - 1
        else:
            i = mi + 1
    return False
```def searchMatrix(matrix: list\[list\[int]], target: int) -> bool:    m, n = len(matrix), len(matrix\[0])    i, d = 0, m \* n - 1    while i <= d:        mi = i + (d - i) // 2        fmi = mi // n        cmi = mi % n        if target == matrix\[fmi]\[cmi]:            return True        if target < matrix\[fmi]\[cmi]:            d = mi - 1        else:            i = mi + 1    return False

Miguel Angel Reyes Moreno

student•

Aquí propongo mi solución:


from typing import List
def searchMatrix(matrix: List\[List\[int]], target: int) -> bool:    m = len(matrix)    n = len(matrix\[0])    left = 0    right = (m\*n) - 1
&#x20;   while left <= right:        k = (left + right) // 2        row = k // n        col = k % n
&#x20;       if matrix\[row]\[col] == target:            return True #\* target is found        elif matrix\[row]\[col] < target:            left = k + 1        else:            right = k - 1
&#x20;   return False #\* target is not found

print(searchMatrix(\[\[1,3,5,7],\[10,11,16,20],\[23,30,34,60]], 3)) # trueprint(searchMatrix(\[\[1,3,5,7],\[10,11,16,20],\[23,30,34,60]], 13)) # false

Juan Pablo Reina Gutierrez

student•

Esta es mi solución, realmente una matriz se puede tratar como un arreglo lineal:

public class SearchIn2DArray {

    public static int[] busquedaBinaria(int[][] nums, int target) {
        int mitad;
        int izquierda = 0;
        int derecha = nums.length * nums[0].length - 1;

        // Vamos a recorrer la matriz como si fuera un arreglo de una sola dimensión, para eso hay que traducir
        //  los índices a los indices de las filas y columnas, eso lo hacemos con el desplazamiento
        //  de bits
        while (izquierda <= derecha) {
            mitad = izquierda + (derecha - izquierda) / 2;

            // indice filas: mitad >> 2
            // indice columnas: mitad - (mitad >> 2 << 2)
            int indiceFila = mitad >> 2;
            int indiceCol = mitad - (mitad >> 2 << 2);
            if (nums[indiceFila][indiceCol] == target) {
                return new int[]{indiceFila, indiceCol}; // Si se encuentra el elemento
                // buscado retornamos un arreglo con los índices de la fila y columna
                // donde se encuentra el elemento
            } else if (nums[indiceFila][indiceCol] < target) {
                izquierda = mitad + 1;
            } else {
                derecha = mitad - 1;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[][] nums = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(Arrays.deepToString(nums));

        int indiceBusq = 34;
        int[] indicesBusq = busquedaBinaria(nums, indiceBusq);
        System.out.println("Indice buscado: " + indiceBusq + ", encontrado en: " + Arrays.toString(indicesBusq));

        indiceBusq = 3;
        indicesBusq = busquedaBinaria(nums, indiceBusq);
        System.out.println("Indice buscado: " + indiceBusq + ", encontrado en: " + Arrays.toString(indicesBusq));

        indiceBusq = 11;
        indicesBusq = busquedaBinaria(nums, indiceBusq);
        System.out.println("Indice buscado: " + indiceBusq + ", encontrado en: " + Arrays.toString(indicesBusq));

        indiceBusq = 30;
        indicesBusq = busquedaBinaria(nums, indiceBusq);
        System.out.println("Indice buscado: " + indiceBusq + ", encontrado en: " + Arrays.toString(indicesBusq));
    }
}

Nicolas Alpargatero

student•

Tengo curiosidad como logrará un O(log(m*n)), en este caso es O(m log n), aunque bueno ella dijo bajar la complejidad de O(n^2) entonces reto cumplido 🤓👀😅🐍🐧

Irving Juárez

student•

Mi primera idea para resolver este algoritmo sería utilizar binary search, pero por cada row. Por ejemplo, empiezamos con dos punteros, uno al principio y uno al final del primer row. Si esta dentro del rango, nos quedamos ahí, si no, nos movemos al segundo row hasta que encontremos el rango correcto o hasta que se nos acaben las filas dentro de la matriz.