algorithme de recherche dans un tableau trié

nicolas49 · June 2004

bonjour,

Travaillant dans l'informatique embarquée, les contraintes temps réelles sont très importantes. C'est pourquoi je recherche un algorithme de recherche convergeant le plus rapidement possible.

Il s'agit d'un tableau triés de chaines de caractères d'environs 1000 éléments. Le but est de trouver l'ensemble des chaines de caractères commencant par une chaine de caractère donné en entrée.

exemple : tableau (AA, ABB, ABC, AC, AD)
trouver les chaines commencant par "AB" : résultat (ABB, ABC)

Quel est le type d'algorithme le plus rapide pour mon problème ?

merci d'avance de votre réponse

Oblomov0 · June 2004

Bonjour,

Théoriquement, dans un tableau trié, je crois bien que c'est la recherche par dichotomie (tu coupes au milieu, tu testes <,= ou > et tu recommences) qui est la plus efficace. Ceci dit, cela dépend qussi beaucoup de comment tu codes.

Oblomov.

nathan g · June 2004

Intuitivement :

Pour moi, le problème revient "juste" à trouver les positions Nmin et Nmax des éléments encadrants la sous liste recherchée (car les éléments sont triés alphabétiquement). Donc, tu peux partir de Nmin =1 et Nmax = "taille du tableau".

Ensuite , tu procèdes par dichotomie à partir de l'ément de rang N = (Nmin+Nmax)/2. :

Si l'élement de rang N ne fait pas partie de la liste et s'il est placé avant le début de la liste (ex : Il commence par AA pour reprendre ton exemple), alors, tu peux écrire Nmin = N et recommencer.

Si l'élement de rang N ne fait pas partie de la liste et s'il est placé après le début de la liste (ex : Il commence par AC pour reprendre ton exemple), alors, tu peux écrire Nmax = N et recommencer.

Si l'ément de rang N est dans la sous liste recherchée, je te conseille alors de faire deux sous algorithmes similaires à celui-ci en recherchant Nmin et Nmax respectivement entre le Nmin courant et N et N et le Nmax courant, puisque tu disposes d'un élement que tu sais être dans la liste.

Ludovic1 · June 2004

On peut d'abord faire une recherche d'un élément de l'ensemble recherché par dichotomie et renvoyé les bornes où s'est arrêtée la recherche. Cela permet de gégrossir le problème. Puis faire la recherche du plus petit et du plus grand élément séparément mais toujours par dichotomie.

Voilou...

@++

Cédric · June 2004

Ah... bonheur je viens jsute de faire un DM d'info là dessus lol, il me semble que l'algorithme KMP (Knuth je sais plus quoi ...)

Enfin ça doit permettre de déterminer rapidement si une chaine est un sous-mot rapidement...

@+
Cédric

ArtAmi · November 2012

bonjour;j'aimerai vraiment avoir de l'aide
pour la conception de mes programmes.en faite je suis en première année informatique.je doit écrire un programme en C qui permet de chercher une chaîne de caractère dans un tableau de chaîne.

gerard0 · November 2012

Bonjour ArtAmi.

Puisque tu veux de l'aide, écris ici ce que tu as déjà fait (au moins un essai d'algorithme) et plutôt dans le forum "maths-info", et il y a des chances qu'un forumeur intéressé t'aide à continuer.

Cordialement.

algorithme de recherche dans un tableau trié

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 23