Retrouver un contact parmi des milliers
Une recherche retrouve un élément dans une liste, comme un contact dans ton téléphone. Une bonne méthode reste rapide même avec des milliers d’éléments.
Lire 2 000 contacts un par un serait lent. Une liste rangée par ordre alphabétique permet de faire bien mieux.
À la fin de cette leçon
Remarque
Je peux trouver un élément dans une liste avec une recherche linéaire et avec une recherche dichotomique.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Recherche | retrouver la place d’un élément dans une liste | |
| Recherche linéaire | regarder les cases une par une, depuis le début | |
| Recherche dichotomique | regarder la case du milieu, puis garder la bonne moitié | |
| Liste triée | une liste rangée du plus petit au plus grand | |
| Comparaison | la question « ces deux valeurs sont-elles égales, ou laquelle est plus grande ? » | |
| Indice | le numéro d’une case, qui commence à 0 | liste[0] |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La recherche linéaire regarde chaque case
La méthode la plus simple : on regarde la première case, puis la deuxième, puis la suivante, jusqu’à trouver la valeur.
On compte les comparaisons. Si la valeur est la première, il n’y en a qu’une. Si elle est absente, il faut lire toute la liste.
Compte les comparaisons d’une recherche linéaire
def recherche_lineaire(liste, cible):
comparaisons = 0
for indice in range(len(liste)):
comparaisons = comparaisons + 1
if liste[indice] == cible:
print("trouvé à l’indice", indice, "après", comparaisons, "comparaisons")
return indice
print("absent après", comparaisons, "comparaisons")
return -1
notes = [12, 7, 31, 4, 19, 25]
recherche_lineaire(notes, 19)
# Change 19 en 99 : que se passe-t-il ?
La dichotomie coupe la liste en deux
Sur une liste triée, on peut faire mieux. On regarde la case du milieu. Si la valeur est trop petite, on garde la moitié de droite. Si elle est trop grande, on garde la moitié de gauche.
À chaque comparaison, la moitié des cases disparaît. On s’arrête quand on trouve la valeur, ou quand il ne reste rien.
Exemple travaillé : chercher 25 dans 15 valeurs
| Étape | Début | Fin | Milieu | Valeur du milieu | Décision |
|---|---|---|---|---|---|
| 1 | 0 | 14 | 7 | 47 | 25 est plus petit : on garde la gauche |
| 2 | 0 | 6 | 3 | 19 | 25 est plus grand : on garde la droite |
| 3 | 4 | 6 | 5 | 31 | 25 est plus petit : on garde la gauche |
| 4 | 4 | 4 | 4 | 25 | Trouvé à l’indice 4 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Lance la recherche dichotomique
def recherche_dichotomique(liste, cible):
debut = 0
fin = len(liste) - 1
etapes = 0
while debut <= fin:
milieu = (debut + fin) // 2 # // est la division entière
etapes = etapes + 1
if liste[milieu] == cible:
print("trouvé à l’indice", milieu, "après", etapes, "étapes")
return milieu
if liste[milieu] < cible:
debut = milieu + 1
else:
fin = milieu - 1
print("absent après", etapes, "étapes")
return -1
notes = [3, 8, 12, 19, 25, 31, 38, 47, 52, 60, 66, 71, 80, 88, 95]
recherche_dichotomique(notes, 25)
# Cherche 50, une valeur absente, puis 95.
Une erreur fréquente
Attention
Beaucoup pensent que la dichotomie marche sur n’importe quelle liste. Elle suppose que la liste est triée. Sur une liste mélangée, la case du milieu ne dit rien sur la gauche ou la droite : la réponse peut être fausse.
Compte les lignes du fichier du lab
docker exec jupyter wc -l hires.csvAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Compare la liste et la liste triée
docker exec jupyter python3 -c "import csv; v = [int(x['hires']) for x in csv.DictReader(open('hires.csv'))]; print(v[:8]); print(sorted(v)[:8])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Calcule le nombre maximal d’étapes pour 365 valeurs
docker exec jupyter python3 -c "import math; print(365, math.floor(math.log2(365)) + 1)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ce que disent les trois Runs
Le fichier a 366 lignes : un titre et 365 jours de locations de vélos. La colonne hires donne le nombre de vélos loués chaque jour.
Le deuxième Run affiche huit valeurs dans l’ordre du fichier, puis les huit plus petites de toute l’année. La liste est mélangée, donc il faut la trier avant une dichotomie.
Le troisième Run affiche 365 9. Trouver un jour parmi 365 prend au plus 9 comparaisons, contre 365 pour la recherche linéaire.
Pour aller plus loin : une liste de mots
La dichotomie marche aussi sur des mots rangés par ordre alphabétique. Python sait comparer "chat" < "chien".
Écris une liste triée de dix prénoms de ta classe et cherche l’un d’eux avec ta fonction. Combien d’étapes faut-il au plus ?