Vers l'algorithme de dichotomie
Exemple d'utilisation :
>>> tab = [1, 5, 7, 9, 12, 13]
>>> recherche_dichotomique(tab, 12)
True
>>> recherche_dichotomique(tab, 17)
False
Code à trous, newbie version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | def recherche_dichotomique(tab, val) :
'''
renvoie True ou False suivant la présence de la valeur val dans le tableau trié tab.
'''
i_debut = ...
i_fin = ...
while ... <= ... :
i_centre = (... + ...) // 2
val_centrale = tab[...]
if val_centrale == val:
return ...
if val_centrale < val:
i_debut = ... + 1
else :
i_fin = ... - 1
return False
|
Code à trous, regular version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | def recherche_dichotomique(tab, val) :
'''
renvoie True ou False suivant la présence de la valeur val dans le tableau trié tab.
'''
i_debut = ...
i_fin = ...
while ... <= ... :
i_centre = ...
val_centrale = ...
if ... == ... :
return ...
if ... < ...:
i_debut = ...
else :
i_fin = ...
return False
|
Code à trous, expert version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | def recherche_dichotomique(tab, val) :
'''
renvoie True ou False suivant la présence de la valeur val dans le tableau trié tab.
'''
... = ...
... = ...
while ... <= ... :
... = ...
... = ...
if ... == ... :
return ...
if ... < ...:
... = ...
else :
... = ...
return False
|
Code à trous, God version
| def recherche_dichotomique(tab, val) :
...
|
Pour tester :
>>> tab = [1, 5, 7, 9, 12, 13]
>>> recherche_dichotomique(tab, 12)
True
>>> recherche_dichotomique(tab, 17)
False