Searching algorithms · Algorithmes de recherche
| English | Français |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
| binary search/ˈbaɪnəri sɜːtʃ/ | recherche binaire |
Twenty questions for a million names
- A phone book holds a million names. Checking them one at a time, you would expect half a million comparisons before finding the one you want.
- Open it in the middle instead, decide which half the name is in, and throw the other half away. Repeat. You reach any name in twenty comparisons.
- Half a million against twenty is not a small saving; it is the difference between a program that works and one that cannot be used. And it costs one thing: the list must already be in order.
- This lesson is linear search 线性查找 and binary search 二分查找, how each performs, and how to choose.
Vingt questions pour un million de noms
- Un annuaire contient un million de noms. En les vérifiant un par un, on s'attendrait à effectuer demi-million de comparaisons avant de trouver celui que l'on cherche.
- Ouvrez-le au milieu au lieu de cela, décidez dans quelle moitié se trouve le nom, et jetez l'autre moitié. Répétez. Vous atteignez n'importe quel nom en vingt comparaisons.
- Demi-million contre vingt n'est pas une petite économie ; c'est la différence entre un programme qui fonctionne et un programme inutilisable. Et cela coûte une chose : la liste doit déjà être triée.
- Cette leçon traite de la recherche linéaire 线性查找 et de la recherche binaire 二分查找, de la performance de chacune, et de la manière de choisir.
Linear search
- It walks from the start, comparing each element with the target, and stops when it finds a match or reaches the end.
- It works on any list, sorted or not, and on any structure that can be stepped through.
- Worst case: the target is last or absent, so all $n$ elements are compared, which is $O(n)$. On average, about half.
One at a time, from the beginning
Recherche linéaire
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- Elle parcourt depuis le début, comparant chaque élément avec la cible, et s'arrête lorsqu'elle trouve une correspondance ou atteint la fin.
- Elle fonctionne sur n'importe quelle liste, triée ou non, et sur toute structure qui peut être parcourue élément par élément.
- Cas défavorable : la cible est la dernière ou absente, donc tous les $n$ éléments sont comparés, ce qui est $O(n)$. En moyenne, environ la moitié.
Un par un, depuis le début
A linear search: · Une recherche linéaire :
Linear search needs no preparation and works on any list, at worst O(n). · La recherche linéaire ne nécessite aucune préparation et fonctionne sur n'importe quelle liste, au pire O(n).
Linear search is the better choice when the data is: · La recherche linéaire est le meilleur choix lorsque les données sont :
With no order to exploit (or a tiny list), linear search avoids the cost of sorting first. · Avec aucun ordre à exploiter (ou une petite liste), la recherche linéaire évite le coût du tri préalable.
Binary search
- It requires the data to be sorted. Compare the middle element with the target: if it matches, stop; if the target is larger, discard the lower half; otherwise discard the upper half.
- Each comparison halves the range still to be searched, so the number of comparisons is $O(\log_2 n)$.
- That is why a million items need about twenty comparisons: $2^{20}$ is just over a million.
Recherche binaire
low ← 1 ; high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN
RETURN mid
ENDIF
IF A[mid] < target THEN
low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
RETURN -1
- Elle nécessite que les données soient triées. Comparez l'élément central avec la cible : s'il correspond, arrêtez ; si la cible est plus grande, jetez la moitié inférieure ; sinon jetez la moitié supérieure.
- Chaque comparaison divise par deux la plage encore à rechercher, donc le nombre de comparaisons est $O(\log_2 n)$.
- C'est pourquoi un million d'éléments nécessitent environ vingt comparaisons : $2^{20}$ est juste au-dessus d'un million.
Searching algorithms · Algorithmes de recherche
binary halves the range each step · la recherche binaire divise la plage par deux à chaque étape
Linear search checks every item; binary · binaire halves a sorted list — far fewer comparisons. · La recherche linéaire vérifie chaque élément ; la recherche binaire divise par deux une liste triée — bien moins de comparaisons.
The worst-case time complexity of binary search is: · La complexité temporelle au cas le plus difficile de la recherche binaire est :
Halving the range each step gives a logarithmic number of comparisons. · Diviser la plage par deux à chaque étape donne un nombre logarithmique de comparaisons.
About how many comparisons does a binary search need for one million sorted items? · Approximativement combien de comparaisons une recherche binaire nécessite-t-elle pour un million d'éléments triés ?
$\log_2(1\,000\,000) \approx 20$ — about 20 comparisons. · $\log_2(1\,000\,000) \approx 20$ — environ 20 comparaisons.
Binary search can be used on any list, sorted or not. · La recherche binaire peut être utilisée sur n'importe quelle liste, triée ou non.
It decides which half to discard by comparing with the middle element, which is only meaningful if the data is in order. · Elle décide quelle moitié éliminer en comparant avec l'élément central, ce qui n'a de sens que si les données sont ordonnées.
Binary search is O(log n) because each comparison ____ the range still to be searched. · La recherche binaire est O(log n) car chaque comparaison ____ la plage restante à rechercher.
Twenty halvings take a million down to one, which is why 2^20 being just over a million is the number to remember. · Vingt divisions par deux ramènent un million à un, c'est pourquoi 2^20 étant légèrement supérieur à un million est le chiffre à retenir.
Worked example: trace a binary search
- The sorted list is 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Trace the search for 23.
lowis 1,highis 10, somidis 5, holding 16. 16 is less than 23, so discard the lower half:lowbecomes 6.low6,high10, somidis 8, holding 56. 56 is greater than 23, sohighbecomes 7.low6,high7, somidis 6, holding 23. Found, in three comparisons where a linear search would have taken six.- Show
low,high,midand the value at each step. Most of the marks are in the trace, not the answer.
Exemple résolu : tracer une recherche binaire
- La liste triée est 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Tracez la recherche de 23.
lowvaut 1,highvaut 10, doncmidvaut 5, contenant 16. 16 est inférieur à 23, on élimine la moitié inférieure :lowdevient 6.lowvaut 6,highvaut 10, doncmidvaut 8, contenant 56. 56 est supérieur à 23, donchighdevient 7.low6,high7, doncmidest 6, contenant 23. Trouvé, en trois comparaisons là où une recherche linéaire aurait pris six.- Montrez
low,high,midet la valeur à chaque étape. La plupart des points sont dans le tracé, pas dans la réponse finale.
In the sorted list 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, how many comparisons does a binary search need to find 23? · Dans la liste triée 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, combien de comparaisons une recherche binaire nécessite-t-elle pour trouver 23 ?
mid 5 holds 16 (too small), mid 8 holds 56 (too large), mid 6 holds 23. A linear search would have taken six. · mid 5 contient 16 (trop petit), mid 8 contient 56 (trop grand), mid 6 contient 23. Une recherche linéaire aurait nécessité six comparaisons.
Choosing between them
| linear | binary | |
|---|---|---|
| data must be sorted | no | yes |
| comparisons, worst case | $n$ | $\log_2 n$ |
| a million items | up to 1,000,000 | about 20 |
| suits | unsorted or small lists, linked lists | large sorted arrays, searched repeatedly |
- Sorting first costs more than one linear search, so binary search pays only when the list is already sorted or will be searched many times.
- Binary search also needs direct access to the middle element, which an array has and a linked list does not.
Choisir entre eux
| linéaire | binaire | |
|---|---|---|
| les données doivent être triées | non | oui |
| comparaisons, cas pire | $n$ | $\log_2 n$ |
| un million d'articles | jusqu'à 1,000,000 | environ 20 |
| adapté à | listes non triées ou petites, listes chaînées | grands tableaux triés, recherchés fréquemment |
- Le tri préalable coûte plus qu'une recherche linéaire, donc la recherche binaire n'est rentable que si la liste est déjà triée ou sera recherchée de nombreuses fois.
- La recherche binaire nécessite aussi un accès direct à l'élément du milieu, ce qui est possible avec un tableau mais pas avec une liste chaînée.
Worked example: justify the choice
- A program searches an unsorted list of 50 records once. Linear search: sorting the list first would cost far more than the 50 comparisons the search needs.
- A program searches a sorted array of a million records thousands of times a second. Binary search: the data is already sorted and each search costs about 20 comparisons instead of up to a million.
- A program searches a linked list. Linear search: binary search needs to jump straight to the middle element, and a linked list can only be followed from the start.
- Name the algorithm, then the property of the data that decides it.
Exemple résolu : justifier le choix
- Un programme cherche dans une liste non triée de 50 enregistrements une seule fois. Recherche linéaire : trier la liste coûterait bien plus que les 50 comparaisons nécessaires à la recherche.
- Un programme cherche dans un tableau trié d'un million d'enregistrements des milliers de fois par seconde. Recherche binaire : les données sont déjà triées et chaque recherche ne coûte qu'environ 20 comparaisons au lieu de jusqu'à un million.
- Un programme cherche dans une liste chaînée. Recherche linéaire : la recherche binaire doit sauter directement vers l'élément du milieu, et une liste chaînée ne peut être parcourue qu'à partir du début.
- Nommez l'algorithme, puis la propriété des données qui le détermine.
Match each search to its key facts. · Associez chaque recherche à ses faits clés.
Binary search is far faster (O(log n)) but only on sorted data; linear works anywhere at O(n). · La recherche binaire est bien plus rapide (O(log n)) mais uniquement sur des données triées ; la recherche linéaire fonctionne partout en O(n).
When is linear search the better choice? Select all · tout that apply. · Quand la recherche linéaire est-elle le meilleur choix ? Sélectionnez toutes les options qui s'appliquent.
The last case is exactly where binary search wins. Sorting first costs more than a single linear search, so it pays only over many searches. · Le dernier cas est précisément celui où la recherche binaire l'emporte. Trier d'abord coûte plus cher qu'une unique recherche linéaire, donc cela ne devient rentable que sur de nombreuses recherches.
The cost of keeping the file sorted
- Binary search is only available on a sorted list, and that sorting is not free. A question that asks you to justify a choice is asking you to price it.
- If the data is searched often and changed rarely, sort it once and every later search is $\log_2 n$. That is the case for a dictionary or a lookup table.
- If the data changes constantly, every insertion has to keep the order, which costs a shift of the later elements. A linear search over unsorted data can then be the cheaper total.
- Numbers make the argument concrete: a million records need up to a million comparisons linearly, but only 20 by binary search, since $2^{20} > 10^6$.
- So the marked answer names both halves: how often it is searched, and how often it changes.
Le coût de maintenir le fichier trié
- La recherche binaire n'est disponible que sur une liste triée, et ce tri n'est pas gratuit. Une question vous demandant de justifier un choix vous demande de l'évaluer en termes de coût.
- Si les données sont recherchées souvent et changent rarement, triez-les une seule fois et chaque recherche ultérieure sera $\log_2 n$. C'est le cas pour un dictionnaire ou une table de correspondance.
- Si les données changent constamment, chaque insertion doit maintenir l'ordre, ce qui coûte un déplacement des éléments suivants. Une recherche linéaire sur des données non triées peut alors avoir un coût total moindre.
- Les chiffres rendent l'argument concret : un million d'enregistrements nécessitent jusqu'à un million de comparaisons en linéaire, mais seulement 20 en recherche binaire, car $2^{20} > 10^6$.
- Ainsi, la réponse marquée nomme les deux aspects : la fréquence de la recherche et la fréquence des changements.
Put the justification for choosing a search algorithm in order. · Placez la justification du choix d'un algorithme de recherche dans l'ordre.
A justify question wants the trade-off, not the winner. Binary search on a list that changes constantly can cost more in total than a linear search. · Une question de justification cherche le compromis, pas le gagnant. La recherche binaire sur une liste qui change constamment peut coûter plus au total qu'une recherche linéaire.
Marks that slip away
- Binary search requires sorted data. Saying "it is faster" without that condition loses the mark.
- Each step halves the range, which is where the $\log_2 n$ comes from. Give the reason, not just the notation.
- Both searches must be able to report not found, which is what the
-1and the loop condition are for. - Binary search needs direct access, so it does not apply to a linked list even if the list is sorted.
Pièges qui font perdre des points
- La recherche binaire requiert des données triées. Dire « c'est plus rapide » sans cette condition fait perdre les points.
- À chaque étape, la plage est divisée par deux, c'est d'où vient le $\log_2 n$. Donnez la raison, pas seulement la notation.
- Les deux recherches doivent pouvoir signaler non trouvé, ce qui est le rôle du
-1et de la condition de boucle. - La recherche binaire a besoin d'accès direct, elle ne s'applique donc pas à une liste chaînée même si celle-ci est triée.
You've got it
- linear search compares each element from the start, works on any list, and is $O(n)$
- binary search needs sorted data with direct access, compares the middle and halves the range each time, giving $O(\log_2 n)$: about 20 comparisons for a million items
- trace a binary search by showing
low,high,midand the value at each step - choose from the data: unsorted, small or a linked list means linear; large, sorted and searched often means binary
Vous avez compris
- recherche linéaire compare chaque élément depuis le début, fonctionne sur n'importe quelle liste, et est $O(n)$
- recherche binaire nécessite des données triées avec accès direct, compare le milieu et divise par deux la plage à chaque étape, donnant $O(\log_2 n)$ : environ 20 comparaisons pour un million d'éléments
- tracez une recherche binaire en montrant
low,high,midet la valeur à chaque étape - choisissez parmi les données : non triées, petites ou une liste chaînée signifie linéaire ; grand, trié et recherché souvent signifie binaire