Panoramic

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

Code :

(dernière modification Vendredi 26 Octobre à 10:45)

' ******************************************************************************
' *  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 *********************************************************

Pour Papydall :

Le code du tuto :

Recherche dichotomique dans un tableau trié

Description

Code :

Pour Papydall :

Le code du tuto :