Animation de la recherche dichotomique
Cette page présente une animation permettant de comprendre le principe de la recherche par dichotomie.
L'algorithme de recherche est sous l'animation.
1 - Animation
On notera que le tableau doit être trié de façon croissante.
Valeur cherchée :
| Index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Elément | 06 | 08 | 09 | 13 | 18 | 37 | 37 | 59 | 60 | 60 | 61 | 68 | 70 | 80 | 80 | 83 | 83 | 89 | 91 | 96 |
2 - Algorithme
Algorithme de recherche dichotomique
But : fournir l'indice de la première occurrence trouvée d'un élément x dans un tableau t. La valeur de réponse de -1 indique l'absence de x dans le tableau.
Description des entrées / sortie
- ENTREES :
- x : un élément voulu qu'on tente de rechercher dans le tableau
- t : un tableau trié contenant un ensemble d'éléments.
- PRECONDITON : le tableau est trié en ordre croissant.
- (entrée optionnelle selon le langage d'implémentation) longueur : le nombre d'éléments dans le tableau
- SORTIE : un entier correspondant à un indice i du tableau tel que t[i] contient bien x, ou la réponse vide (-1 par exemple).
| t | ⇒ | RECHERCHER | ⇒ | |
| et | indice ou "vide" | |||
| x |
Algorithme
Dans l'algorithme ci-dessous, l'opérateur // désigne une division euclidienne.
r ← -1
g ← 0
d ← longueur - 1
TANT QUE (g <= d) ET (r vaut -1)
c ← (g + d) // 2
SI t[c] < x
on modifie g pour "supprimer" la partie gauche
g ← (c + 1)
SINON SI t[c] > x
on modifie d pour "supprimer" la partie droite
d ← (c - 1)
SINON
x est l'élément de t[c] : on sort du TANT QUE en modifiant r
r ← c
Fin du Si
Fin Tant que
Renvoyer c
3 - Implémentation Python
Supprimer le print() de la ligne 16 (ou 15 sur la version 2) si vous ne voulez pas de description progressive du déroulement.
Deux versions :
- La première avec juste un seul return, plus propre algorithmiquement.
- La deuxième plus simple mais comportant deux return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 |
def recherche_dicho(t, x):
'''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique
:: param t(list) :: un tableau trié d'éléments
:: param x (variable) :: l'élément à chercher dans le tableau
:: return (int) :: l'indice de l'élément ou -1
.. Précondition 1 :: le tableau ne doit pas être vide
.. Précondition 2 :: le tableau doit être TRIE de façon croissante
.. Précondition 3 :: x doit être du même type que les éléments du tableau
'''
r = -1
g = 0
d = len(t) - 1
while g <= d and r == -1:
print(f"Un tour de boucle avec l'intervalle [{g}; {d}]")
c = (g + d) // 2 # Division entière
if t[c] < x:
g = c + 1
elif t[c] > x:
d = c - 1
else:
r = c
return r
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | def recherche_dicho(tableau, x):
'''Fonction qui cherche l'élément x dans le tableau trié de façon dichotomique
:: param t(list) :: un tableau trié d'éléments
:: param x (variable) :: l'élément à chercher dans le tableau
:: return (int) :: l'indice de l'élément ou -1
.. Précondition 1 :: le tableau ne doit pas être vide
.. Précondition 2 :: le tableau doit être TRIE de façon croissante
.. Précondition 3 :: x doit être du même type que les éléments du tableau
'''
g = 0
d = len(tableau) - 1
while g <= d:
print(f"Un tour de boucle avec l'intervalle [{g}; {d}]")
c = (g + d) // 2 # Division entière
if tableau[c] < x:
g = c + 1
elif tableau[c] > x:
d = c - 1
else:
return c
return -1
|
Article publié le 11 04 2020
Dernière modification : 13 04 2020
Auteur : ows. h.