Bases & algorithmique · 6 mondes · 18 étapes
Algorithmique
Apprendre à penser un problème, en Python, dans le navigateur.
Progression
0 %
0/18 étapes terminées
Intermédiaire · 9 min de lecture
Chercher une valeur
Linéaire, dichotomique, et le prix du tri
1Définition
Chercher, c'est répondre « où est cette valeur ? » ou « y est-elle ? ». La recherche linéaire parcourt tout et fonctionne toujours. La recherche dichotomique divise l'espace par deux à chaque tour, et exige une liste triée.
2Principes fondamentaux
01
Renvoyer une position, ou -1
-1 n'est pas une position valide : il ne peut pas être confondu avec un résultat. C'est la convention de tout le métier.
02
La dichotomie exige le tri
Sans tri, « trop petit » ne veut rien dire : l'algorithme jette une moitié qui contenait peut-être la valeur. Il donne des réponses fausses, pas lentes.
03
Trier coûte plus cher que chercher une fois
Une recherche linéaire coûte n ; trier coûte n log n. La dichotomie n'est rentable que si l'on cherche plusieurs fois dans la même liste.
04
Un dictionnaire bat les deux
Si les recherches sont nombreuses, indexer dans un dictionnaire donne du O(1) et rend la question du tri sans objet.
3Exemples pratiques
Les bornes de la dichotomie
1debut = 02fin = len(annuaire) - 13 4while debut <= fin: # <= et non <5 milieu = (debut + fin) // 26 if annuaire[milieu] == cherche:7 position = milieu8 break9 elif annuaire[milieu] < cherche:10 debut = milieu + 1 # +1 obligatoire11 else:12 fin = milieu - 1 # -1 obligatoireTrois détails font tout : <= pour examiner le dernier candidat, et les +1 / -1 qui garantissent l'arrêt.
Le coût, en nombre de lectures
1# 1 000 000 d'éléments2# linéaire : jusqu'à 1 000 000 lectures3# dichotomie : 20 lectures4# dictionnaire : 1 lectureLe même problème, trois ordres de grandeur. C'est la différence entre une page qui répond et une page qui expire.
4Erreurs courantes
Boucle infinie sur les bornes
À éviter
elif annuaire[milieu] < cherche: debut = milieuÀ faire
elif annuaire[milieu] < cherche: debut = milieu + 1Pourquoi : Sans le +1, milieu peut rester identique au tour suivant : la boucle tourne sans fin.
Sortir trop tôt
À éviter
while debut < fin:À faire
while debut <= fin:Pourquoi : Quand debut == fin, il reste un candidat. Avec <, une valeur présente peut être déclarée absente.
Dichotomie sur liste non triée
À éviter
valeurs = [42, 7, 19]# puis recherche dichotomiqueÀ faire
valeurs = sorted([42, 7, 19])Pourquoi : Le résultat est faux de façon silencieuse : le pire type de bug.
5Subtilités à connaître
- ◆
valeur in listefait une recherche linéaire ;valeur in dictionnaireouin ensembleest quasi instantané. - ◆Le module
bisectde la bibliothèque standard fournit une dichotomie testée : en production, on l'utilise. - ◆En très grand,
(debut + fin) // 2peut déborder dans certains langages ; d'où la formedebut + (fin - debut) // 2. Python n'a pas ce problème, ses entiers sont illimités.
6Vérifie ta compréhension
Question 1/3
Score 0
Combien de tours au maximum pour chercher dans 1 000 éléments triés ?
Envie d'essayer ? Ouvre le Labo et recopie les exemples pour les modifier.