Discussion :

[kenzo75]

Bonjour, j'essaye d'implémenter un algorithme de recherche d'élément par dichotomie (récursif si possible) sur une matrice trié par ligne et par colonne mais je n y arrive pas trop voir même pas du tout.
Sur un tableau 1D j' y arrive parfaitement mais sur une autre matrice c'est une autre affaire.

Voici un exemple de matrice triée :

1 2 5 9
8 12 15 17
10 13 16 19
11 14 17 23

J'ai pensé à diviser à prendre l'élément du milieu par exemple 13, puis comparer l'élément x recherché a 10 (premier élément de la ligne du milieu) et a 19 (dernier élément de la ligne du milieu). Si x > 10 et x > 19 alors on recherchera en bas de du milieu.
Si x < 10 et x < 19 on recherchera en haut du milieu etc ..
Ensuite faire de même à gauche et a droite, donc on divise la matrice en 4 en quelque sorte.
Mais il reste plusieurs sous cas que je ne trouve pas et je ne suis même pas sur que c'est faisable.
Merci de m'aider

[DonQuiche]

Bonjour.

D'abord j'imagine que tes lignes sont triées en fonction de leur premier élément seulement ? Mais qu'entre deux lignes consécutives, deux éléments de la même colonne (hormis le premier) peuvent être arbitrairement ordonnés ? Autrement dit on peut affirmer que M[i,0] < M[j,0] mais on ne peut rien dire sur M[i,k] et M[j,k] ?

Si oui tu ne peux pleinement exploiter la dichotomie que sur la dimension horizontale, au sein d'une ligne. Mais entre les lignes tu ne peux utiliser la dichotomie que pour rechercher la dernière des lignes à scanner. En effet tu ne dois scanner que les i tels que M[i,0] <= x. Mais tu dois impérativement scanner tout ce sous-ensemble. Soit un O(n.log(n))



Si en revanche je me trompe et que M[i,k] < M[j,k] quel que soit k et quels que soient i < j, alors je pense que la bonne stratégie est de chercher (en utilisant la dichotomie) la dernière des ligne à parcourir d'après le premier élément, puis au sein de ce sous-ensemble la dernière des colonnes à parcourir en utilisant la dernière ligne, puis au sein de ce sous-ensemble la première des lignes en utilisant la dernière colonne, puis la première colonne en utilisant la première ligne, etc. Autrement dit tu décrirais une spirale pour circonscrire un rectangle de plus en plus petit. C'est du O(2*log(n) + 2*log(n/2) + 2*log(n/4) + ...). C'est inférieur à O(log(n)*log(n)) puisqu'on a log2(n) termes. Je pense qu'on ne peut pas faire mieux.

[ToTo13]

Bonjour,

dans le cas d'une matrice, la dichotomie n'est plus l'algorithme le plus approprié : tu ne supprimes plus la moitié des éléments, mais un quart.
Il existe une recherche beaucoup plus rapide.

[kenzo75]

@donquiche
Si il y a une relation d ordre entre deux elements d'une même colonne :

1 2 5 9
8 12 15 17
10 13 16 19
11 14 17 23

Ici : 1<8<10<11 et même raisonnement pour les autres colonnes
Pour les lignes : 1<2<5<9

Je pense qu'un algo en o(n) est faisable : en comparant l element cherché à chaque premier élement des lignes de la matrice, puis en effectuant une dichotomie sur la ligne qui correspond.
Mais y aurai-t-il un un algorithme de meilleur complexité??

[ToTo13]

Mais y aurai-t-il un un algorithme de meilleur complexité??

Pour une matrice de taille NxM, il y a un algorithme en O(N+M). Il suffit de partir d'en bas à gauche et de comparer la valeur avec celle cherchée : plus petit tu montes, plus grand tu vas à droite.
Cela est possible car ta matrice est doublement triée.

[kenzo75]

Je pense aussi que c'est la meilleure implémentation, j vais essayer ça, biensur si quelqu'un d'autre à meilleure j'suis preneur.
Merci pour tout

[DonQuiche]

Pour une matrice de taille NxM, il y a un algorithme en O(N+M). Il suffit de partir d'en bas à gauche et de comparer la valeur avec celle cherchée : plus petit tu montes, plus grand tu vas à droite.
Cela est possible car ta matrice est doublement triée.

@donquiche
Si il y a une relation d ordre entre deux elements d'une même colonne :

Alors c'est le second cas de figure pour lequel j'avais proposé un algo en O(ln(n) * ln(n)), ce qui est meilleur que du O(n+n).

[kenzo75]

@donquiche
Je ne comprends pas trop l'algo, y aurait moyen de l'expliquer un peu plus , ou donner un exemple ? Merci