La facture 193, vite
Une cliente appelle la comptabilité au sujet de sa facture numéro 193. Le logiciel en contient des milliers.
On peut les lire une par une depuis le début. Mais si les factures sont rangées par numéro, il existe une méthode bien plus rapide.
Cette leçon montre les deux méthodes, et quand utiliser chacune.
À la fin de cette leçon
Remarque
Je peux trouver un élément par recherche séquentielle et par recherche dichotomique.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Algorithme | une suite d’étapes qui résout un problème |
| Recherche séquentielle | regarder chaque élément dans l’ordre |
| Trié | rangé du plus petit au plus grand |
| Recherche dichotomique | regarder le milieu et écarter une moitié |
| Étape | une comparaison avec un élément |
| -1 | la réponse convenue pour « absent » |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La recherche séquentielle lit chaque élément
La recherche séquentielle part du premier élément. Elle le compare à ce qu’on cherche, puis passe au suivant.
Elle s’arrête quand elle trouve, ou quand la liste est finie. Elle marche sur n’importe quelle liste, triée ou non.
Au pire, elle regarde tous les éléments. Pour 1 000 colis, cela peut faire 1 000 étapes.
À vous : chercher un colis
# Numéros de suivi des colis, dans l'ordre d'expédition.
colis = [58213, 58190, 58277, 58204, 58251, 58236]
cherche = 58251
etapes = 0
position = -1
for i in range(len(colis)):
etapes = etapes + 1
if colis[i] == cherche:
position = i
break
print("Trouvé à l'indice", position, "en", etapes, "étapes")
# Cherchez 99999, un numéro absent, puis exécutez.
La recherche dichotomique coupe en deux
La recherche dichotomique ne marche que sur une liste triée. Elle regarde l’élément du milieu.
Si c’est le bon, elle s’arrête. Si on cherche plus grand, elle écarte toute la moitié gauche. Si on cherche plus petit, elle écarte la moitié droite.
Puis elle recommence avec ce qui reste. Chaque étape divise la liste par deux.
À vous : chercher une facture
# Numéros de facture, triés du plus petit au plus grand.
factures = [102, 115, 123, 138, 141, 156, 162, 177, 185, 193, 204, 218, 226, 231, 249]
cherche = 193
bas = 0
haut = len(factures) - 1
etapes = 0
while bas <= haut:
etapes = etapes + 1
milieu = (bas + haut) // 2
print("Étape", etapes, ": indice", milieu, "contient", factures[milieu])
if factures[milieu] == cherche:
print("Trouvée à l'indice", milieu)
break
elif factures[milieu] < cherche:
bas = milieu + 1 # on écarte la moitié gauche
else:
haut = milieu - 1 # on écarte la moitié droite
# Cherchez 102, puis 249, et comptez les étapes.
Exemple travaillé : chercher 193 parmi 15
| Étape | Bas | Haut | Milieu | Valeur au milieu | Décision |
|---|---|---|---|---|---|
| 1 | 0 | 14 | 7 | 177 | 193 est plus grand : à droite |
| 2 | 8 | 14 | 11 | 218 | 193 est plus petit : à gauche |
| 3 | 8 | 10 | 9 | 193 | Trouvée |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une erreur fréquente
Attention
Beaucoup pensent que la recherche dichotomique marche sur n’importe quelle liste. C’est faux. Si la liste n’est pas triée, écarter une moitié peut écarter l’élément cherché. Le programme répond alors « absent » alors qu’il est là.
Exemple travaillé : le pire cas
| Nombre d’éléments | Séquentielle, au pire | Dichotomique, au pire |
|---|---|---|
| 15 | 15 étapes | 4 étapes |
| 1 000 | 1 000 étapes | 10 étapes |
| 1 000 000 | 1 000 000 étapes | 20 étapes |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.