Définition et utilité
La recherche dichotomique est une technique algorythmique applicable dans n'importe quel langage de
programmation (du moment que l'on peut faire des boucles bien sur). Elle est utilisable
UNIQUEMENT dans des tables de données ordonnées !!! (Ce qui est souvent le cas).
Nous pouvons lui trouver une utilité lorsque les données d'un tableau commencent à se faire nombreuses
et donc leur parcours laborieux pour les vieille bécanes et autres mobilettes.
Principe
Le principe est assez simple mais assez difficile à expliquer.
Prenons par exemple un tableau (Array) JavaScript, que nous nommerons de façon originale leTablo.
Considérons que la valeur recherchée est stockée dans la variable leCherche. (Essayez de suivre avec
l'illustration et l'exemple ce sera plus clair :)
Considérons que celui-ci est rempli avec des nombres aléatoires classés par ordre croissant.
Nous stockons dans deux variables, l'index du premier élement de notre tableau (en général 0 ou 1)
puis le dernier. Nous appellerons ces variables tout à fait au hazard Min et Max. Ces variables vont en
quelque sorte nous servir de délimiteur du tableau : ce sont des bornes qui délimiterons la partie du
tableau dans laquelle la valeur doit se trouver (sous réserve qu'elle existe bien sur).
Min=1;
Max=leTablo.length;
Nous stockons ensuite l'index du milieu de notre tableau retourné. Toujours originaux, nous la
nommerons Mil.
Mil=parseInt((Max+Min)/2);
Il suffit après de comparer la valeur du contenu de leTablo situé à l'index Mil, à leCherche.
if(leTablo[Mil]>leCherche)
Si la condition est juste, celà signifie que si la valeur existe dans le tableau, elle ne se situe pas
dans la partie située entre sa moitié et sa fin. Nous n'avons donc plus besoin de ce morceau.
Nous allons donc redéfinir notre délimiteur de fin (Max) pour qu'il vienne se placer au niveau du Milieu
du tableau (fournit par Mil).
Max=Mil
Sinon, dans le cas inverse, c'est notre délimiteur de début que devra se déplacer.
Min=Mil
Le tout devant être répété dans une boucle qui se terminera quand Mil et Min seront égaux.
while(Mil!=Min){
A la sortie de la boucle, il en vous restera plus qu'à tester si la valeur située à l'index Min (= Mil) de leTablo correspond à leCherche. Si c'est le cas, c'est que la valeur à été trouvée.
Sinon, cela signifie que la valeur n'a pas été trouvée et que la boucle s'est arrêtée car Mil et Min
se sont retrouvés.
Graphiquement ca donne quoi ?
Exemple de script
L'exemple ci-dessous crée un tableau avec les lettres de l'alphabet pour valeur. Il suffit ensuite de
rentrer une lettre dans le champs et d'appuyer sur le bouton pour lancer la fonction qui heberge la
recherche dichotomique. Pensez que cette technique trouve aussi bien son salut dans les éléments SELECT
et les tableaux à X dimensions.
| dichotomie.htm |  |  | |
|
<script language="JavaScript">
// Création du tableau
var leTablo= new Array();
// Remplissage du tableau
// ici avec les lettres de l'alphabet
// mais ça pourrait être n'importe quelles chaînes
for(i=1;i<27;i++) leTablo[i]=String.fromCharCode(64+i);
function Cherche(){
var leCherche=document.neb.champs.value.toUpperCase();
var Min=1;
var Max=leTablo.length;
var Mil=parseInt((Max+Min)/2);// On force en nombre entier
while(Mil!=Min){
if(leTablo[Mil]>leCherche)
Max=Mil
else
Min=Mil;
Mil=parseInt((Max+Min)/2)
}
if(leTablo[Min]==leCherche)
window.alert("J'ai trouvé le "+leCherche+" à l'index "+Min+ " !!!")
else
window.alert("Cette valeur n'existe pas dans le tableau !");
return false // pour ne pas soumettre le form
}
</script>
<form name="neb" onSubmit="return Cherche()">
<input name="champs" id="champs" size="5">
<input type="Submit" value="Cherche">
</form> |
Forum |
Actu |
Glossaire |
Codes |
Tips |
Liens |
Livres |
Annuaire
