Algorithmie Recherche Dichtomique

Recherche dichotomique

Fonction recherche_dichotomique (e :entier, nbelements :entier, tab : tableau)

        Déclaration de variables.

        |        deb,mil,fin : entier

        Fin de déclaration

Début

|        deb 🡨 0

|        fin  🡨 nbelements - 1

|         // Cette recherche a lieu après un tri

|         tantQue (deb  fin)[pic 1]

|         |        mil= (deb + fin) / 2

|        |        si (tab[mil]>= e)

|        |        |        fin 🡨 mil-1

|        |        sinon

|        |        |        deb 🡨 mil + 1

|        |        Finsi

|        FintantQue

|        si (tab[deb] = e) alors

|        |        retourne deb

|         sinon

|        |        retourne (-1)

|        FinSi

Fin

Algorithme : Utilisation

        Déclaration de variable

        |        tab :tableau[o..n] de entier, n, pos, e :entier

        Fin déclaration variable

Début

|        Ecrire (« nombre d’entier trier dans le tableau »)

|        lire (n)

|        tab 🡨  new entier [n]

|        // int[] tab = new int [n]

|        TantQue (i<n)

|        |        Ecrire (« entrez la valeur »,i)

|        |        Lire Valeur

|        |        Tab [i] 🡨 valeur

|        |        i++

|        FinTantQue

|        Ecrire («  Quel est l’élement à retrouver »)

|        lire (e)

|        pos 🡨 Recherche_dichotomique (e)

|        si (pos  -1) alors[pic 2]

|        |        Ecrire(pos)

|        sinon

|        |        Ecrire (« Cet élémement ne figure pas dans le tableau

|        Fin

Fin

...