<!DOCTYPE html>
<html>
<head>
<meta name="description" content="RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE">
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<meta name="author" content="Papydall">
<title>Panoramic</title>
<style type="text/css">
body{margin:1em 8em 0;font-family:"georgia",serif;}
h1{color:green;font-weight:bold;text-align:left;}
h2{color:blue;}
p{text-align:justify;}
textarea{max-height:30em;height:30em;width:100%;border:1px solid #AAA;background:#DDD;white-space:nowrap;}
.note{color: green;font-size: small; font-style: italic;}
.button{float:right;}
table{background-color:#C0C0C0;width:100%;}
th{background:#BBF;font-size:1em;text-align:center;}
td{padding:0.5em;background:#EEF;}
ul{margin:0;padding-left:1em;}
</style>
</head>
<body>
<h1> ***** RECHERCHE DICHOTOMIQUE *****
<br> ************** PAR PAPYDALL *************</br></h1>
<!-- ***************************************************************************
* D E S C R I P T I O N
******************************************************************************** -->
<h2>Description</h2>
<p>On dispose d'un tableau trié contenant des valeurs de type entier, flottant ou string.
On désire savoir si une valeur bien déterminée existe ou non dans ce tableau.
Si oui, on désire également connaitre sa position (son rang) dans le tableau.
Le programme "DICHO.BAS" que je vous propose contient une procédure qui réalise la recherche.
Il vous montre aussi un exemple d'utilisation de cette procédure</p>
<!-- ***************************************************************************
* S O U R C E P A N O R A M I C
******************************************************************************** -->
<h2>Code</h2>
<textarea readonly="readonly" id="code" wrap="off">
' ******************************************************************************
' * RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE
' *
' * DICHOTOMIE.BAS par Papydall
' ******************************************************************************
' Exemple d'utilisation
' La recherche doit se faire sur un tableau trié
' Le tableau peut contenir n'importe quel type de données : entier, réel ,string
' La dichotomie consiste à couper le tableau en 2 et comparer la valeur du milieu
' avec celle à rechercher.
' si la valeur du milieu est supérieure à celle recherchée,on recherche alors
' dans la première moitié sinon dans la seconde.
' Cet algorithme est très rapide : sur un très grand tableau, il est très efficace
' ------------------------------------------------------------------------------
DIM dim% : dim% = 1000000 : ' Dimension du tableau pour notre exemple
DIM T%(dim%) : ' Un tableau d'entiers de dimension un million!
DIM i% : ' Variable compteur
DIM true,false : ' Déclaration des constantes booléènnes
true = 1 : false = 0 : ' Simulation du type booléen
caption 0,"Recherche dichotomique dans un tableau trié"
' ------------------------------------------------------------------------------
' Création d'un tableau d'entiers contenant les valeurs de 1 à 1000000
' (un million et plus si vous voulez!)
' Cette phase de création est assez longue!
' Lorsque vous validez le message "OK pour la recherche",le résultat de la
' recherche s'affiche instantanément : Appréciez la rapidité de l'algorithme !!
' ------------------------------------------------------------------------------
print_locate 100,100 : print " Veuillez patienter, je crée le tableau!"
print_locate 100,120 : print " Cette phase peut durer un certain temps!"
for i% = 1 to dim% : t%(i%) = i% : next i% : ' Remplissage du tableau
print_locate 100,160 : print " Le tableau a été créé : Validez le message"
message "Prêt pour la recherche"
cls
chercher(-10) : ' élément à rechercher ===> il n'est pas dans le tableau
chercher(3) : ' élément à rechercher ===> il est dans le tableau
chercher(999999) : ' élement à rechercher ===> il est dans le tableau
chercher(123456) : ' élément à rechercher ===> il est dans le tableau
chercher(1) : ' élément à rechercher ===> il est dans le tableau
chercher(0) : ' élémént à rechercher ===> il n'est pas dans le tableau
chercher(1000000) : ' élément à rechercher ===> il est dans le tableau
chercher(1110000) : ' élement à rechercher ===> il n'est pas dans le tableau
print_locate 100,100 : print "Terminé"
end
' *****************************************************************************
' Procédure de recherche par dichotomie
SUB chercher(element%)
dim_local premier%,milieu%,dernier%,trouve,position%,texte$
trouve = false : ' L'élément à rechercher n'est pas encore trouvé
premier% = 1 : ' On initialise les variables de debut
dernier% = dim% : ' et de fin du tableau
' Si le 1er élément du tableau est déjà plus grand que la valeur à rechercher,
' ( forcément cet élément n'appartient pas à la liste !)
' on affiche le message et on quitte la procédure
if t%(premier%) > element%
texte$ = str$(element%) + " : cet élément n'appartient pas à la liste"
message texte$ : EXIT_SUB
end_if
' C'est ici que commence la recherche
while (premier% <= dernier%) and trouve = false
milieu% = int((premier% + dernier%)/2)
if t%(milieu%) = element%
trouve = true : position% = milieu% : ' Si on a trouvé, on quitte au prochain WHILE
else : ' non, on n'a pas trouvé
if t%(milieu%) > element% : ' La valeur du milieu est supérieure à l'élément à rechercher ?
dernier% = milieu% : ' La recherche se fera donc dans la moitié gauche
else
premier% = milieu% + 1 : ' Sinon ça sera dans la moitié droite
end_if
end_if
end_while
if trouve = false : ' La recherche n'a pas aboutit ?
texte$ = str$(element%) + " : cet élément n'appartient pas à la liste"
else : ' La recherche est positive
texte$ = str$(element%) + " : cet élémént appartient à la liste "
texte$ = texte$ + chr$(13) + "il est en position: " + str$(position%)
end_if
message texte$ : ' On affiche le message et on quitte
END_SUB
' **************** FIN *********************************************************
</textarea>
</div>
<hr>
<p>édité le 26/10/2012.</p>
</body>
</html>
Accueil 
Calendrier
)