Algo Dichotomie

Identification

Infoforall

Animation de la recherche dichotomique


Cette page présente une animation permettant de comprendre le principe de la recherche par dichotomie.

L'algorithme de recherche est sous l'animation.

1 - Animation

On notera que le tableau doit être trié.

Valeur cherchée :

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 06 08 09 13 18 37 37 59 60 60 61 68 70 80 80 83 83 89 91 96

2 - Algorithme

Algorithme de recherche dichotomique

But : trouver si un élément recherché existe bien dans un tableau. S'il existe, on fournit l'index de la première occurrence trouvée. Sinon, il renvoie une réponse vide.

Principe : dans un tableau trié, on regarde la valeur centrale dans les index encore disponibles. S'il ne s'agit pas de la bonne valeur, on enlève de l'intervalle de recherche les index qui ne peuvent pas contenir la valeur recherchée.

Description des entrées / sortie

  • ENTREES :
    • tableau : un tableau trié contenant un ensemble d'éléments.
    • x : un élément voulu qu'on tente de rechercher dans le tableau
    • (optionnelle selon les langages d'implantation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : une réponse vide (à définir) ou un nombre correspondant à l'index trouvé.

Algorithme commenté

Dans l'algorithme ci-dessous, l'opérateur // désigne une division entière.

    g ← 0

    dlongueur - 1

    TANT QUE g <= d

      c(g + d) // 2

      SI tableau[c] < x

        on ne garde que ce qui est à droite de l'index centre

        g(c + 1)

      SINON SI tableau[c] > x

        on ne garde que ce qui est à gauche de l'index centre

        d(c - 1)

      SINON

        Si on arrive ici, c'est que x est à l'index centre

        Renvoyer c

      Fin du Si

    Fin Tant que

    Si on arrive ici, c'est que l'intervalle de recherche est vide

    Renvoyer VIDE

Algorithme non commenté

    g ← 0

    dlongueur - 1

    TANT QUE g <= d

      c(g + d) // 2

      SI tableau[c] < x

        g(c + 1)

      SINON SI tableau[c] > x

        d(c - 1)

      SINON

        Renvoyer c

      Fin du Si

    Fin Tant que

    Renvoyer VIDE

3 - Python

Supprimer la ligne 27 si vous ne voulez pas de description progressive du déroulement.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
import random def creer(nbr) : '''Fonction qui renvoie un tableau de nbr éléments compris entre 0 et 100 :: param nbr(int) :: un entier correspondant au nombre d'éléments voulus :: return (list) :: un tableau d'entiers de nbr éléments compris entre 0 et 100 ''' tableau = [random.randint(0,100) for x in range(nbr)] return tableau def recherche_dicho(tableau, x) : '''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique :: param tableau(list) :: un tableau trié d'éléments :: param x (variable) :: l'élément à chercher dans le tableau :: return (NoneType ou int) :: l'index de l'élément ou None .. Précondition 1 :: le tableau ne doit pas être vide .. Précondition 2 :: le tableau doit être TRIE .. Précondition 3 :: x doit être du même type que les éléments du tableau ''' g = 0 d = len(tableau) - 1 while g <= d : print(f"Un tour de boucle avec l'intervalle [{g}; {d}]") c = (g + d) // 2 # Division entière if tableau[c] < x : g = c + 1 elif tableau[c] > x : d = c - 1 else : return c return None if __name__ == '__main__' : tab_test = sorted( creer(100) ) print(tab_test) numero = recherche_dicho(tab_test, 5) print(numero)

Article publié le 11 04 2020
Dernière modification : 13 04 2020
Auteur : ows. h.