Recherche binaire
Introduit| English | Sens |
|---|---|
| sorted/ˈsɔːtɪd/ | trié |
| Binary search/ˈbaɪnəri sɜːtʃ/ | recherche dichotomique |
| target/ˈtɑːɡɪt/ | cible |
| middle/ˈmɪdl/ | milieu |
| halves/hɑːvz/ | moitiés |
| comparison/kəmˈpærɪsn/ | comparaison |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
Trouver rapidement dans une liste triée
- La recherche binaire est une méthode rapide pour localiser une valeur cible dans une liste triée.
- "Triée" signifie que les valeurs sont dans l'ordre — du plus petit au plus grand, par exemple.
- Elle est bien plus rapide que de vérifier chaque élément.
- Mais elle a une exigence stricte.
La recherche dichotomique nécessite des données triées. Sur une liste non triée, elle peut sauter la cible et la manquer. Triez toujours d'abord — ou utilisez une autre recherche.
La recherche binaire ne peut être utilisée que sur des données qui sont :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Sur des données non triées, elle peut manquer la cible.
Vérifier le milieu, puis diviser par deux
- L'idée est simple : vérifiez l'élément central. Ensuite :
- si le milieu égale la cible, vous l'avez trouvée ;
- si la cible est plus petite, cherchez uniquement dans la moitié gauche ;
- si la cible est plus grande, cherchez uniquement dans la moitié droite.

La recherche binaire divise la plage à chaque étape (la liste doit être triée)
Recherche linéaire vs binaire
la recherche binaire divise la plage par deux à chaque étape
La recherche linéaire vérifie chaque élément ; la recherche binaire divise une liste triée par deux à chaque comparaison, elle nécessite donc beaucoup moins d'étapes.
Si la cible est plus grande que l'élément central, la recherche binaire cherche ensuite dans le :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Une cible plus grande doit se trouver dans la moitié droite (plus élevée).
Chaque comparaison dans la recherche binaire ______ la partie restante de la liste.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Diviser par deux à chaque étape est pourquoi c'est si rapide.
Combien de vérifications de recherche binaire sont nécessaires pour une liste triée de 1000 éléments ? (2^10 = 1024)
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Parce que 2^10 = 1024 ≥ 1000, environ 10 divisions suffisent.
Pourquoi c'est si rapide
- Chaque comparaison moitié la partie restante de la liste.
- Pour 1000 éléments, une recherche linéaire peut nécessiter jusqu'à 1000 vérifications.
- La recherche dichotomique nécessite au maximum environ 10, car $2^{10} = 1024$.
- Plus la liste est grande, plus l'avantage est important.
La recherche binaire trouve 14 dans [2,5,8,11,14,17,20] en combien de comparaisons ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Milieu 11 → droite ; milieu 17 → gauche ; milieu 14 → trouvé : 3 comparaisons.
Sur une grande liste triée, la recherche linéaire nécessite moins de comparaisons que la recherche binaire.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Faux. La recherche binaire divise la liste par deux à chaque étape, nécessitant donc bien moins de comparaisons que de vérifier chaque élément séquentiellement.
Comparé à la recherche linéaire
- Une recherche linéaire vérifie chaque élément un par un.
- La recherche dichotomique la bat sur les grandes listes triées en divisant par deux à chaque étape.
Recherche [2, 5, 8, 11, 14, 17, 20] pour 14. Le milieu est 11 ; 14 > 11 → recherche dans la moitié droite [14, 17, 20]. Le milieu est 17 ; 14 < 17 → recherche dans [14]. Le milieu est 14 — trouvé en seulement 3 comparaisons. Une recherche linéaire aurait pris 5.
La recherche dichotomique trouve une cible dans une liste triée en vérifiant le milieu et en conservant uniquement la moitié susceptible de la contenir. Chaque comparaison divise par deux 减半 la plage, donc 1000 éléments nécessitent ~10 vérifications — bien moins que les 1000 d'une recherche linéaire 线性查找. Elle ne fonctionne que sur des données triées.