Recherche dichotomique

Exercice 

Faire un algorithme qui fait une recherche dichotomique dans un tableau trié. On pourra utiliser les fonctions de l’exercice précédent.

Nous allons créer une action qui définie la zone de recherche, puis l’action RechercheDicho qui opérera la recherche dichotomique dans l’intervalle définie par la zone de recherche.

Action ZoneRecherche (E : tvt : TtabVar, E : n : entier, ES : Binf : entier, ES : Bsup : entier)

Var : milieu : entier

Début

                Milieu <= (Binf + Bsup)/2

                Si tvt.tab[milieu]=n alors

                               Début

                               Binf<=milieu

                               Bsup<=milieu

                               Fin

                Sinon

                               Si tvt.tab[milieu]>n alors Bsup<=milieu –1

                               Sinon Binf<=milieu+1

Fin

Fonction RechercheDicho (E : tvt : TtabVar, E : n : entier)

Var : Binf, Bsup : entiers

Début

                Binf<=0

                Bsup<=tvt.taille –1

                Tant que Bsup>Binf faire

                               ZoneRecherche (tvt, n, Binf, Bsup)

                               Si Bsup=Binf alors

                                               Retourner (Binf)

                               Sinon retourner ( -1)

• Tweet
• Share
• Share
• Share
• Share

Related Post