Livre_silo 30 août 2013 16:32 Page 157
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
157
6 – Notions de complexité et algorithmique sur les tableaux
On commence par initialiser les variables g et d avec 0 et len(a)-1, respectivement :
def recherche_dichotomique(x, a):
g, d = 0, len(a)-1
Tant que la portion à considérer contient au moins un élément :
while g <= d:
on calcule l’indice de l’élément central, en faisant la moyenne de g et d :
m = (g + d) // 2
Il est important de noter qu’on effectue ici une division entière. Qu’elle soit arrondie vers
le bas ou vers le haut, on obtiendra toujours une valeur comprise entre g et d, ce qui assure
d’une part que a[m] existe et qu’il est bien situé entre g et d. Si a[m] est l’élément recherché,
on a terminé la recherche :
if a[m] == x:
return m
Sinon, on détermine si la recherche doit être poursuivie à gauche ou à droite. Si a[m] < x,
on poursuit à droite :
if a[m] < x:
g = m+1
Sinon, on poursuit à gauche :
else:
d = m-1
Si on sort de la boucle while, c’est que l’élément ne se trouve pas dans le tableau, car il ne
reste que des éléments strictement plus petits (à gauche de g) ou strictement plus grands
(à droite de d). On renvoie alors None pour signaler l’échec.
return None
Le code complet est donné programme 1 ci-dessous.
PROGRAMME 1 Recherche dichotomique dans un tableau trié
def recherche_dichotomique(x, a):
"""renvoie, si elle existe, la position d'une occurrence de x dans a
supposé trié, et None sinon"""
g, d = 0, len(a)-1
while g <= d:
m = (g + d) // 2
if a[m] == x:
return m
if a[m] < x:
g = m+1
else:
d = m-1
return None
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
157
6 – Notions de complexité et algorithmique sur les tableaux
On commence par initialiser les variables g et d avec 0 et len(a)-1, respectivement :
def recherche_dichotomique(x, a):
g, d = 0, len(a)-1
Tant que la portion à considérer contient au moins un élément :
while g <= d:
on calcule l’indice de l’élément central, en faisant la moyenne de g et d :
m = (g + d) // 2
Il est important de noter qu’on effectue ici une division entière. Qu’elle soit arrondie vers
le bas ou vers le haut, on obtiendra toujours une valeur comprise entre g et d, ce qui assure
d’une part que a[m] existe et qu’il est bien situé entre g et d. Si a[m] est l’élément recherché,
on a terminé la recherche :
if a[m] == x:
return m
Sinon, on détermine si la recherche doit être poursuivie à gauche ou à droite. Si a[m] < x,
on poursuit à droite :
if a[m] < x:
g = m+1
Sinon, on poursuit à gauche :
else:
d = m-1
Si on sort de la boucle while, c’est que l’élément ne se trouve pas dans le tableau, car il ne
reste que des éléments strictement plus petits (à gauche de g) ou strictement plus grands
(à droite de d). On renvoie alors None pour signaler l’échec.
return None
Le code complet est donné programme 1 ci-dessous.
PROGRAMME 1 Recherche dichotomique dans un tableau trié
def recherche_dichotomique(x, a):
"""renvoie, si elle existe, la position d'une occurrence de x dans a
supposé trié, et None sinon"""
g, d = 0, len(a)-1
while g <= d:
m = (g + d) // 2
if a[m] == x:
return m
if a[m] < x:
g = m+1
else:
d = m-1
return None