Discussion :

[DonQuiche]

On ajoute 1 quand on veut passer du "plus grand inférieur ou égal" au "plus petit supérieur"

[ol9245]

Mon algo est aussi trivial que rapide et s'implémente en quelques minutes. Commence donc par faire un test avec, puis tu essaies d'optimiser en testant les autres.

j'ai pas compris ton algo. Ca a l'air intéressant. Tu peux le mettre en pseudo-code ?

[Trademark]

Je me permet de le mettre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
find(x, matrix[n][m]):
 
  i = n - 1;
  j = 0;
  found = false;
 
  while(NOT found AND i >= 0 AND j < m) :
    if (x > matrix[i][j])
      ++j;
    else if(x < matrix[i][j])
      --i;
    else
      found = true;
 
  if(found) :
    print "Element aux indices (" i "," j ")."
  else
    print "Element non trouvé."

[kenzo75]

@donquich
La dichotomie sur la ligne du haut et la colonne de gauche ne permettent que de faire un decalage de 1 si elles ne contiennent pas la valeur cherchee je ne me trompe pas?
Si c est bien le cas j ai implementé l'algo correspondant en java mais je ne peux pas le diffuser ici avant 2 semaine, puis je vous l envoyer par mp pour verifier et confirmer la complexité? Puis je posterai biensur a la fin de ce delai.

[DonQuiche]

@kenzo
Non, pas forcément, considère par exemple la matrice suivante et la valeur 14, on peut exclure les deux lignes du bas d'après la colonne de droite.
1 2 5 7
8 9 11 12
10 13 16 19
11 14 17 23

Concernant la vérification, je t'engage plutôt à faire des tests. D'abord parce que je n'ai pas envie de me fatiguer à le relire, ensuite parce que de toute façon je ne suis pas infaillible.


Enfin, autre variante possible de l'algo que je viens de remarquer : à chaque valeur considérée on peut éliminer un quart de la matrice et diviser le problème en deux sous-matrices. Par exemple si je prends la valeur du milieu de la matrice (13) et que la valeur cherchée est inférieure à 13, alors je peux toujours éliminer les valeurs en bas à droite (en rouge). Ou le quart inférieur gauche si on cherche une valeur supérieure à 13.
01 02 05 07
08 09 11 12
10 13 16 19
11 14 17 23


Après ça le problème peut être divisé en deux matrices, l'une d'elles contenant la bonne valeur.
01 02 05 07
08 09 11 12
10
11

La complexité est du même acabit que le précédent algo mais celui-ci est peut-être un peu plus simple à comprendre et peut mieux se comporter.

[ToTo13]

Pour mon algo, sur un tableau T(M,N), on cherche V :
- commencer en bas à gauche T(0,N), soit x=0, y=N.
- Tant que V n'est pas trouvé et que l'on est dans la matrice
----- si T(x,y) == V , sortir.
----- sinon si T(x,y) < V => x++
----- sinon si V < T(x,y) => y++

[ol9245]

Je me permet de le mettre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
find(x, matrix[n][m]):
 
  i = n - 1;
  j = 0;
  found = false;
 
  while(NOT found AND i >= 0 AND j < m) :
    if (x > matrix[i][j])
      ++j;
    else if(x < matrix[i][j])
      --i;
    else
      found = true;
 
  if(found) :
    print "Element aux indices (" i "," j ")."
  else
    print "Element non trouvé."

en effet c'est magnifique !

ça me fait réflachir que l'algo de sedjevick que j'ai proposé n'est pas adapté à la question posée. Il concerne une recherche dans un nuage de points du plan.

[ToTo13]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
find(x, matrix[n][m]):
 
  i = n - 1;
  j = 0;
  found = false;
 
  while(NOT found AND i >= 0 AND j < m) :
    if (x > matrix[i][j])
      ++j;
    else if(x < matrix[i][j])
      --i;
    else
      found = true;
 
  if(found) :
    print "Element aux indices (" i "," j ")."
  else
    print "Element non trouvé."

Ben c'est l'algo que j'avais proposé : aussi simple que rapide !