Binary Search · Recherche binaire
| English | Français |
|---|---|
| sorted/ˈsɔːtɪd/ | trié |
| Binary search/ˈbaɪnəri sɜːtʃ/ | Recherche binaire |
| target/ˈtɑːɡɪt/ | cible |
| middle/ˈmɪdl/ | au milieu |
| comparison/kəmˈpærɪsn/ | comparaison |
| halves/hɑːvz/ | diminue de moitié |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
Finding fast in a sorted list
- Binary search 二分查找 is a fast way to locate a target 目标 value in a sorted 已排序 list.
- "Sorted" means the values are in order — smallest to largest, say.
- It is far faster than checking every item.
- But it has one strict requirement.
Binary search needs sorted data. On an unsorted list it can jump past the target and miss it. Always sort first — or use a different search.
Trouver rapidement dans une liste triée
- La recherche dichotomique 二分查找 est un moyen rapide de 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.
Binary search can only be used on data that is: · La recherche binaire ne peut être utilisée que sur des données qui sont :
On unsorted data it can miss the target. · Sur des données non triées, elle peut manquer la cible.
Check the middle, then halve
- The idea is simple: check the middle 中间 element. Then:
- if the middle equals the target, you found it;
- if the target is smaller, search only the left half;
- if the target is larger, search only the right half.
Vérifier le milieu, puis diviser par deux
- L'idée est simple : vérifiez l'élément du milieu 中间. 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.
Linear vs binary search · Recherche linéaire vs binaire
binary halves the range each step · la recherche binaire divise la plage par deux à chaque étape
Linear search checks every item; binary search halves a sorted list each comparison, so it needs far fewer steps. · 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.
If the target is larger than the middle element, binary search next looks in the: · Si la cible est plus grande que l'élément central, la recherche binaire cherche ensuite dans le :
A larger target must be in the right (higher) half. · Une cible plus grande doit se trouver dans la moitié droite (plus élevée).
Each comparison in binary search ______ the remaining part of the list. · Chaque comparaison dans la recherche binaire ______ la partie restante de la liste.
Halving each step is why it is so fast. · Diviser par deux à chaque étape est pourquoi c'est si rapide.
About how many binary-search checks are needed for a sorted list of 1000 items? (2^10 = 1024) · Combien de vérifications de recherche binaire sont nécessaires pour une liste triée de 1000 éléments ? (2^10 = 1024)
Because 2^10 = 1024 ≥ 1000, about 10 halvings suffice. · Parce que 2^10 = 1024 ≥ 1000, environ 10 divisions suffisent.
Why it is so fast
- Each comparison 比较 halves 减半 the remaining part of the list.
- For 1000 items, a linear search may need up to 1000 checks.
- Binary search needs at most about 10, because $2^{10} = 1024$.
- The larger the list, the bigger the advantage.
Pourquoi c'est si rapide
- Chaque comparaison 比较 divise par deux 减半 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.
Binary search finds 14 in [2,5,8,11,14,17,20] in how many comparisons? · La recherche binaire trouve 14 dans [2,5,8,11,14,17,20] en combien de comparaisons ?
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons. · Milieu 11 → droite ; milieu 17 → gauche ; milieu 14 → trouvé : 3 comparaisons.
On a large sorted list, binary search needs far fewer comparisons than linear search. · Sur une grande liste triée, la recherche binaire nécessite beaucoup moins de comparaisons que la recherche linéaire.
Halving beats checking every item one by one. · Diviser par deux bat la vérification de chaque élément un par un.
Versus linear search
- A linear search 线性查找 checks every element one by one.
- Binary search beats it on large sorted lists by halving each step.
Search [2, 5, 8, 11, 14, 17, 20] for 14. Middle is 11; 14 > 11 → search the right half [14, 17, 20]. Middle is 17; 14 < 17 → search [14]. Middle is 14 — found in just 3 comparisons. A linear search would have taken 5.
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.
Binary search finds a target in a sorted list by checking the middle and keeping only the half that could contain it. Each comparison halves the range, so 1000 items need ~10 checks — far fewer than a linear search's 1000. It works only on sorted data.
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.