On ajoute 1 quand on veut passer du "plus grand inférieur ou égal" au "plus petit supérieur"
On ajoute 1 quand on veut passer du "plus grand inférieur ou égal" au "plus petit supérieur"
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é."
@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.
@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.
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++
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager