Comment rechercher efficacement dans une matrice ordonnée?

Question

J'ai une matrice x par y , où chaque ligne et chaque colonne sont dans l'ordre croissant comme indiqué ci-dessous.

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

Comment rechercher dans cette matrice un nombre en O(x+y) ?

On m'a posé cette question pour une interview, mais je n'ai pas pu trouver le chemin. Curieux de savoir si cela pourrait être fait.

Answer 1

Début du dernier élément de la première ligne(en haut à droite).
Comparer avec l' key. Nous avons 3 cas:

• Si elles sont égales, nous sommes fait.

• Si key est supérieure à celle de l'élément cela signifie que l' key ne peut pas être présent dans cette ligne, donc aller à la recherche pour l'élément en dessous.

• Si key est inférieure à celle de l'élément puis cela signifie key pourrait être présent dans cet ligne vers la gauche et ne peuvent pas être présents dans la colonne plus bas, afin de déplacer la recherche à l'élément de gauche.

Continuer à le faire jusqu'à ce que vous trouver l'élément ou vous ne pouvez pas aller plus loin(la clé n'existe pas).

Le Pseudo-code:

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

Divisez la matrice en 4 sous-matrices. Si la partie inférieure droite d'une sous-matrice est inférieure à la clé, jetez-la. Si le coin supérieur gauche d'une sous-matrice est plus grand que la clé, jetez-le. Répétez la procédure de fractionnement pour les sous-matrices restantes.

[Mise à jour] Pour un pseudo-code (et une discussion sur la complexité), voir la réponse de Jeffrey L Whitledge à cette question .