Recherche et parcours de tableau

**LEK** · 29/05/2007, 23h10

Bonjour,
je suis amené a construire un tableau contenant une liste de chaîne : Array("A",AB","Améthyste","Avion","Aviron","Bébé","Journal",....) , celui-ci sera trié alphabétiquement et comprendra au max 5000 éléments, j'aimerais savoir comment m'y prendre et avec quel algo afin de pouvoir rechercher tous les éléments commençant par une chaine de recherche donnée sans avoir à parcourir l'ensemble du tableau et avoir les meilleurs temps de réponse possible...

Merci d'avance de votre aide.

**Nemerle** · 30/05/2007, 01h48

t'as pas une fonction "find"?

**Senyk** · 30/05/2007, 08h54

Si tu as le choix dans la structure de données, tu peux stocker tous les mots en utilisant un arbre lexicographique
La ieme génération dans l'arbre représente la ième lettre du mot....
plus d'info sur le premier lien "arbre lexicographique" dans google. http://www.enseignement.polytechniqu...1/TD/td_6.html

La complexité de la recherche ou l'insertion est en N comparaisons où N est le nombre de lettres du mot.

Si le tableau est imposé, une recherche dichotomique devrait suffire...

**LEK** · 31/05/2007, 20h01

Le tableau est imposé mais des éléments peuvent être supprimés/ajoutés.
Je recherche surtout la performance mais j'utlise un langage de script qui ne possède pas de fonction find par exemple; par contre je peux utiliser des expressions régulières...
Dans ces conditions une recherche dichotomique m'apportera t elle la réponse la plus rapide?