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:
Compléter la fonction ci-dessous :
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 = ...
if x == tab[m]:
return ...
if x > tab[m]:
debut = m + 1
else:
fin = ...
return ...On pourra tester notre fonction avec cette liste :
[3, 5, 8, 12, 15, 19, 23, 35, 42, 56, 60, 67, 70, 78, 91]