Activité

activité 30.1

Faites un schéma permettant d'expliquer le principe de la recherche dichotomique en vous basant sur l'exemple suivant : t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 40 (valeur recherchée)

activité 30.2

Faites un schéma permettant d'expliquer le principe de la recherche dichotomique en vous basant sur l'exemple suivant : t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 9 (valeur recherchée)

activité 30.3

Soit l'algorithme de recherche dichotomique :

VARIABLE
t : tableau d'entiers trié
mil : nombre entier
fin : nombre entier
deb : nombre entier
x : nombre entier // x : l'entier recherché
tr : booléen
DEBUT
tr ← FAUX
deb ← 1
fin ← longueur(t)
tant que tr == FAUX et que deb ⩽ fin :
 mil ← partie_entière((deb+fin)/2)
 si t[mil] == x :
  tr = VRAI
 sinon :
  si x > t[mil] :
   deb ← mil+1
  sinon :
   fin ← mil-1
  fin si
 fin si
fin tant que
renvoyer la valeur de tr
FIN

1) Appliquez cet algorithme au tableau t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 40. Vérifiez que l'algorithme renvoie bien VRAI

2) Appliquez cet algorithme au tableau t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 9. Vérifiez que l'algorithme renvoie bien FAUX

activité 30.4

Implémentez l'algorithme de recherche dichotomique en Python.