Chapitre 13 : Recherche dichotomique.
Introduction :
La recherche dichotomique, également appelée recherche binaire, est un algorithme de recherche efficace qui permet de trouver rapidement un élément dans un tableau trié en divisant à chaque étape la plage de recherche en deux et en éliminant la moitié inutile.
1. La Recherche Dichotomique
Comment fonctionne la Recherche Dichotomique ?
L'algorithme de recherche dichotomique fonctionne comme suit :
- Commencer par définir une plage de recherche qui couvre toute la liste triée.
- Calculer l'indice du milieu de la plage de recherche.
- Comparer l'élément au milieu avec l'élément recherché. Si les éléments sont égaux, l'élément est trouvé.
- Si l'élément au milieu est plus petit que l'élément recherché, la plage de recherche est réduite à la moitié supérieure. Sinon, elle est réduite à la moitié inférieure.
- Répéter les étapes 2 à 4 jusqu'à ce que l'élément soit trouvé ou que la plage de recherche devienne vide.
2. Exercice:
A faire dans le cahier.
On considère la liste suivante : [3, 5, 8, 12, 15, 19, 23, 35, 42, 56, 60, 67, 70, 78, 91]
En faisant une recherche dichotomique :
- Ecrire dans votre cahier les différentes étapes de la recherche du nombre 70.
- Ecrire dans votre cahier les différentes étapes de la recherche du nombre 14.
3. Exercice : Recherche dichotomique
Compléter la fonction ci-dessous qui implémente une recherche dichotomique :
Une liste est donnée afin de tester la fonction.
def dichotomie(tab, x):
"""
tab : tableau d’entiers trié dans l’ordre croissant
x : nombre entier
La fonction renvoie True si tab contient x et False sinon
"""
debut = 0
fin = len(tab) - 1
while debut <= fin:
m = ... # indice du milieu
if x == tab[m]:
return ... # trouvé
if x > tab[m]:
debut = m + 1 # on cherche à droite
else:
fin = ... # on cherche à gauche
return ... # non trouvé
liste = [3, 5, 8, 12, 15, 19, 23, 35, 42, 56, 60, 67, 70, 78, 91]
element_cherche = 12
if dichotomie(liste, element_cherche):
print(f"{element_cherche} est présent dans la liste.")
else:
print(f"{element_cherche} n'est pas présent dans la liste.")
Tests :
# TestsAffichage :
Console:
>>>