¿Cómo buscar eficientemente en una matriz ordenada?

Question

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 esta matriz por 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).
Compararlo con key. Tenemos 3 casos:

• Si son iguales, hemos terminado.

• Si key es mayor que el elemento entonces significa key no puede estar presente en esa fila así mover la búsqueda de al elemento por debajo de ella.

• Si key es menor que el elemento continuación que significa key podrían estar presentes en esa fila hacia la izquierda y no puede estar presente en la columna más abajo, por lo que mover la búsqueda de al elemento que queda de ella.

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

Dividir 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 algunos pseudocódigos (y una discusión sobre la complejidad), vea la respuesta de Jeffrey L Whitledge this question.

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 de destino mediante una búsqueda binaria en primer lugar, a continuación, encontrar el objetivo en la fila de búsqueda binaria, por lo que el tiempo de complejidad es O (lgx) + O (lgy) , es O (lgx + lgy), mejor el O (x + y).