arrays - array_search - ¿Cómo buscar eficientemente en una matriz ordenada?

algorithm matrix

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo busco un número en una matriz de 2d ordenada de izquierda a derecha y de arriba a abajo? 19 respuestas

Tengo una matriz x por y , donde cada fila y cada columna están en orden ascendente como se indica a continuación.

1   5   7    9
4   6   10   15
8   11  12   19
14  16  18   21

¿Cómo buscar en esta matriz un número en O(x+y) ?

Me hicieron esta pregunta para una entrevista, pero no pude encontrar el camino. Es curioso saber si podría hacerse.

Answer 1

Comience en el último elemento de la primera fila (esquina superior derecha).
Compáralo con la key . Tenemos 3 casos:

• Si son iguales, hemos terminado.

• Si la key es mayor que ese elemento, significa que la key no puede estar presente en esa fila, por lo tanto, mueva la búsqueda al elemento que se encuentra debajo.

• Si la key es menor que ese elemento, significa que la key podría estar presente en esa fila hacia la izquierda y no puede estar presente en la columna más abajo, así que mueva la búsqueda al elemento que queda.

Siga haciéndolo hasta que encuentre el elemento o no podrá seguir moviéndose (la clave no existe).

Pseudo código:

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = C-1

found = false
while( i>=0 && i<R) && (j>=0 && j<C) )
   if (matrix[i][j] == key )
      found = true
      break
   else if( matrix[i][j] > key )
       j--
   else if( matrix[i][j] < key )
       i++
end-while

Answer 2

Divida la Matriz en 4 submatrices. Si la parte inferior derecha de una submatriz es menor que la clave, deséchela. Si la parte superior izquierda de una submatriz es más grande que la clave, deséchela. Repita el procedimiento de división para las submatrices restantes.

[Actualización] Para algún pseudo código (y una discusión sobre la complejidad), vea la respuesta de Jeffrey L Whitledge a esta pregunta .

Answer 3

// the matrix is like this, from left to right is ascending, and
// from down to up is ascending, but the second row''start is not always bigger than the first row''s end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/
// 1   5   7    9
// 4   6   10   15
// 8   11  12   19
// 14  16  18   21
// time complexity is O(x+y), x is the count of row, and y is the count of column

public boolean searchMatrix2(int[][] matrix, int target) {
    int rowCount = matrix.length;
    if(rowCount == 0) return false;

    int colCount = matrix[0].length;
    if(colCount == 0) return false;

    //first find the target row, needs O(x)
    int targetRow = 0;
    while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) {
        targetRow++;
    }
    //than find the target in the target row, needs O(y), so the total is O(x)+O(y)
    boolean result = false;
    for(int i = 0; i < colCount; i ++) {
        if(matrix[targetRow][i] == target) {
            result = true;
            break;
        }
    }
    return result;
}

En realidad, podemos usar la búsqueda binaria dos veces, encontrar la fila objetivo por búsqueda binaria primero, luego buscar el objetivo en la fila por búsqueda binaria, entonces la complejidad del tiempo es O (lgx) + O (lgy), es O (lgx + lgy ), mejor el O (x + y).