la recherche dichotomique
Une approche simple consiste à effectuer une recherche linéaire. La complexité temporelle de l'algorithme ci-dessus est O (n). Une autre approche pour effectuer la même tâche consiste à utiliser la recherche binaire.
La recherche dichotomique consiste à rechercher dans un tableau trié en divisant de manière récursive l'intervalle de recherche en deux.
Commencez par un intervalle couvrant tout le tableau. Si la valeur de la clé de recherche est inférieure à l'élément situé au milieu de l'intervalle, limitez l'intervalle à la moitié inférieure. Sinon, le réduire à la moitié supérieure. Vérifiez à plusieurs reprises jusqu'à ce que la valeur soit trouvée ou que l'intervalle soit vide.
L’idée de la recherche dichotomique est de profiter du tableau trié et de réduire la complexité à O(Log n).
Implémentation récursive de la recherche dichotomique
- Comparez x avec l'élément du milieu.
- Si x correspond à l'élément du milieu, nous retournons l'indice du milieu.
- sinon Si x est supérieur à l'élément milieu, alors x ne peut se situer que dans la moitié droite du sous-tableau après l'élément milieu.
- Sinon recherchez dans la moitié gauche.
def RechercheDicho(tab, debut, fin, x):
if fin >= debut:
milieu = (debut + fin)//2
if tab[milieu] == x:
return milieu
elif tab[milieu] > x:
return RechercheDicho(tab, debut, milieu-1, x)
else:
return RechercheDicho(tab, milieu + 1, fin, x)
else:
return -1
# tester la fonction
tab = [2, 7, 8, 20, 25, 30, 33, 39, 45, 50]
x = 8
resultat = RechercheDicho(tab, 0, len(tab)-1, x)
if resultat != -1:
print("L'élément est présent à l'indice % d" % result)
else:
print("L'élément n'est pas présent dans le tableau")
L'élément est présent à l'indice 2
Implémentation itérative de la recherche dichotomique
def RechercheBinaire2(tab, x):
debut, fin = 0, len(tab)
while debut <= fin:
milieu = (debut + fin)//2
if tab[milieu] == x:
return milieu
elif tab[milieu] < x:
debut = milieu + 1
else:
fin = milieu - 1
# l'element n'existe pas
return -1
tab = [2, 7, 8, 20, 25, 30, 33, 39, 45, 50]
x = 8
result = RechercheBinaire2(tab, x)
if result != -1:
print("L'élément est présent à l'indice % d" % result)
else:
print("L'élément n'est pas présent dans le tableau")L'élément est présent à l'indice 2
