Discussion :

[Gryzzly]

Bonjour,
j'aurais besoin d'aide pour cet algo

On considère une liste de n chaines de caractères mémorisée dans une table T.
La longueur maximale des chaines T[0],T[1],...,T[n-1] est notée M.
On note <= l'ordre lexicographique et on suppose que :
T[0]<=T[1]<=...<=T[n-1]

On considère un chaine x de longueur m (|x| = m)
Ecrire un algo qui fait la recherche dichotomique de x dans T en utilisant la comparaison de caractère

Merci d'avance

[sinok]

La recherche dichotomique s'effetue de la manière suivante

Soit a l'indice de la première case de ton tableau
Soit b l'indice de la dernière case de ton tableau
soit m une variable temporaire
Soit e la valeur que tu veux insérer
Soit T ta table

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
tant que b-a>1 faire
     m= (a+b)/2
     si e == T[m] 
          on retourne m
     si e>=T[m]
          a = m
     sinon 
          b = m 
fin tant que
on retourne b

a la fin de cette algo tu as dans a l'élément recherché (si il existe) ou la place ou tu peux l'insérer (si il n'est pas dans la table)