meilleure complexité de recherche dans un matrice triée

Salut bon voila j'ai un probléme j'arrive pas a comprendre le principe de base de cete algorithme qui cherche un élement dans une matrice carrée triée.

voila le code source:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 bool Rechm(Matrice M,int n,int x) { i=n; while(M[i][1]>x&& i>=1) i--; if(M[i][1]==x) return true; if(i==0) return false; j=1; while(M[i][j]<x && j<=n) j++; if(M[i][j]==x) return true; if(j>n) return false; return false; }
Merçi.

C'est quoi une matrice triée ? Elle est triée comment ?

Si je comprend bien tu as une matrice (= tableau) à deux dimension triée par ordre croissant.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
   i=n;
   while(M[i][1]>x&& i>=1) 
      i--;
//Si le premier élément de la ligne est plus grand que la valeur recherchée, en recherche dans la ligne précédente.
//On continu tant qu'on arrive pas à la première ligne ou qu'on trouve la ligne où chercher
 
   if(M[i][1]==x)
      return true;
// Si le premier élément de la ligne est égal à x, on retourne true (trouvé) inutile
 
   if(i==0)
      return false;
// si on est à une ligne = 0 (ie ligne n'existant pas) on retourne false (= pas trouvé)
   j=1;
   while(M[i][j]<x && j<=n)
      j++;
//(on parcours la ligne et on s'arrête au premier élément supérieur ou égal à x)
   if(M[i][j]==x)
      return true;// (si on trouve la valeur : return true)
 
   if(j>n) return false;// (inutile)
   return false;// si on a pas trouvé la valeur, on retourne false.
}

Pour simplifier :
On recherche x
1) On recherche la ligne où chercher (= première ligne en partant de la fin où le premier élément est inférieur à x.
2) On parcours la ligne et dès qu'on trouve x, on renvoie true
3) Si on trouve une valeur supérieur à x, on arrête car la matrice est triée.
-> Si on n'a pas trouvé x, on renvois false.
Mais le code a quelques défauts selon moi (déjà le 1er élément d'une ligne est 0 et non 1:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
   i=n-1;
   while( i>=0 && M[i][0]>x) // tester si la ligne existe avant de regarder 
      i--; 
 
   if(i==-1) return false;
   j=0;
 
   while( j<n && M[i][j]<x) //idem avec la colonne
       j++;
 
   if(M[i][j]==x)   return true;
   return false;
}