Recherche dichotomique
Algo 05
Résumé du cours
Algorithme de recherche classique
def recherche_classique(tab: list, cherche: int) -> bool:
for element in tab:
if element == cherche:
return True
# à la fin de la boucle on n'a pas trouvé 'cherche'
return False
Information
La complexité temporelle de la recherche classique est linéaire.
Algorithme de recherche dichotomique
Les données étant triées}, l’algorithme de la dichotomie, pour chercher la présence d’un élément, consiste à:
- couper le tableau en deux parties égales,
- ne garder que la partie contenant l’élément,
- répéter l’opération jusqu’à trouver l’élément ou bien avoir une partie vide.
def recherche_dicho(tab: list, cherche: int) -> bool:
i_debut = 0
i_fin = len(tab)-1
while i_fin >= i_debut:
i_milieu = (i_debut+i_fin) // 2
if cherche == tab[i_milieu]:
return True
elif cherche < tab[i_milieu]:
i_fin = i_milieu-1
else: # cherche > tab[i_milieu]
i_debut = i_milieu+1
# à la fin de la boucle on n'a pas trouvé 'cherche'
return False
Information
La complexité temporelle de la recherche dichotomique est logarithmique.