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é)