2- Recherche Dichotomique (Tableau trié)

1- Algorithme récursive :

Algorithme RechDichoRec (recherche dans un tableau trié) :

Entrée : un tableau trié tab, un intervalle [min; max] avec
0 min max < taille et un élément e.
Sortie : i tel que tab[i] = e ou NonTrouvé (ex : -1).

Début
  si min = max alors
      si tab[min] = e alors

          retourner min
      sinon

          retourner NonTrouvé

      finsi

   finsi
   mid <- (min + max) / 2

   si tab[mid] < e alors
        retourner RechDichoRec(tab, mid+1, max, e)
   sinon
        retourner RechDichoRec(tab, min, mid, e)

   finsi

Fin.

=> Complexité : Θ(Log(N)). (Ajouter les détailles de calcul de la complexité)

2- Algorithme itérative (variante 1):

Algorithme (RechDichoIt recherche dichotomique itérative):

Début
   min <- 0;
   max <- taille - 1
   tant que min < max faire
       mid <- (min + max) / 2
       si tab[mid] < e alors
            min <- mid+1
       sinon
            max <- mid

       finsi

   fintantque

   si tab[min] = e alors

         retourner min
   sinon

         retourner NonTrouvé

    finsi

Fin.

=> Complexité : Θ(Log(N)). (Ajouter les détailles de calcul de la complexité)

3- Algorithme itérative (Variante 2): Sortir si la valeur est trouvée.

Algorithme (Recherche dichotomique variante) :

Début
   min <- 0;
   max <- taille - 1
   tant que min < max faire
      mid <- (min + max) / 2
      si tab[mid] = e alors

          retourner mid

      sinon

             si tab[mid] < e alors
                   min <- mid+1
             sinon
                   max <- mid-1

             finsi

        finsi

   fintantque

   si tab[min] = e alors

       retourner min
   sinon

       retourner NonTrouvé

   finsi

Fin.


=> Complexité : O(Log(N)) \ Ω(1). (Ajouter les détailles de calcul de la complexité)

Last modified: Saturday, 13 February 2021, 2:27 PM