Searching Algorithms · Algorithmes de recherche
| English | Français |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | Recherche |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
| binary search/ˈbaɪnəri sɜːtʃ/ | recherche binaire |
| sorted/ˈsɔːtɪd/ | trié |
Finding a value
- Searching 查找 means locating a target value in a collection.
- Two standard algorithms: linear search 线性查找 and binary search 二分查找.
- Both return the index where the target sits — or a "not found" signal (often
-1). - Which one you may use depends on whether the data is sorted.
Trouver une valeur
- Chercher 查找 signifie localiser une valeur cible dans une collection.
- Deux algorithmes standards : recherche linéaire 线性查找 et recherche binaire 二分查找.
- Tous deux retournent l'index où se trouve la cible — ou un signal « non trouvé » (souvent
-1). - Le choix dépend du fait que les données soient triées.
Linear search
- Check each element from the start, one by one, until you find the target.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Works on any array — sorted or not.
- Worst case: it looks at every element (
nchecks).
Recherche linéaire
- Vérifiez chaque élément du début, un par un, jusqu'à trouver la cible.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Fonctionne sur tout tableau — trié ou non.
- Cas le plus défavorable : il examine tous les éléments (
nvérifications).
Binary search
- Needs a sorted 已排序 array. Look at the middle element each time.
- If the middle is the target, done. If the target is smaller, search the left half; if larger, the right half.
- Each step halves the range that's left to search.
- Far faster on large sorted arrays — about
log₂ nchecks, notn.
Recherche binaire
- Nécessite un tableau trié 已排序. Regardez l'élément central à chaque fois.
- Si le central est la cible, c'est fini. Si la cible est plus petite, cherchez dans la moitié gauche ; si plus grande, dans la moitié droite.
- À chaque étape, la zone restante à chercher est divisée par deux.
- Bien plus rapide sur de grands tableaux triés — environ
log₂ nvérifications, pasn.
Why binary search is fast
- Linear search of a million items: up to a million checks.
- Binary search of a million sorted items: about 20 checks.
- The catch: the array must already be sorted.
- Halving repeatedly is the big idea behind
O(log n).
Pourquoi la recherche binaire est rapide
- Recherche linéaire sur un million d'éléments : jusqu'à un million de vérifications.
- Recherche binaire sur un million d'éléments triés : environ 20 vérifications.
- Le piège : le tableau doit déjà être trié.
- Diviser par deux répétément est l'idée derrière
O(log n).
Binary search only works on a SORTED array — running it on unsorted data gives wrong answers. It also compares to the middle and throws away half the range each step; a linear search compares from the start and drops just one element. If you're not sure the data is sorted, you must use linear search (or sort first).
La recherche binaire ne fonctionne que sur un tableau TRIÉ — l'exécuter sur des données non triées donne de mauvais résultats. Elle compare aussi au central et élimine la moitié de la zone à chaque étape ; une recherche linéaire compare depuis le début et ne retire qu'un élément. Si vous n'êtes pas sûr que les données sont triées, vous devez utiliser la recherche linéaire (ou trier d'abord).
Binary search for 7 in [1, 3, 5, 7, 9]:
- Middle is
5(index 2). 7 > 5, so search the right half. - Right half is
[7, 9]; middle is7. Found at index 3. - Two checks instead of four — the range halved each time.
Recherche binaire pour 7 dans [1, 3, 5, 7, 9] :
- Le central est
5(index 2). 7 > 5, donc cherchez dans la moitié droite. - La moitié droite est
[7, 9]; le central est7. Trouvé à l'index 3. - Deux vérifications au lieu de quatre — la zone a été divisée par deux à chaque fois.
Linear search checks elements from the start (works on any array, up to n checks). Binary search needs a sorted array, compares to the middle, and halves the search range each step (about log₂ n checks). Both return the index found, or a "not found" signal like -1.
La recherche linéaire vérifie les éléments depuis le début (fonctionne sur tout tableau, jusqu'à n vérifications). La recherche binaire nécessite un tableau trié, compare au central et divise par deux la zone de recherche à chaque étape (environ log₂ n vérifications). Tous deux retournent l'index trouvé, ou un signal « non trouvé » comme -1.
Linear vs binary search · Recherche linéaire vs binaire
Binary search halves the sorted range each step. · La recherche binaire divise par deux la plage triée à chaque étape.
A linear search... · Une recherche linéaire...
Linear = start to end; works on any array. · Linéaire = début à fin ; fonctionne sur n'importe quel tableau.
Binary search requires the array to be... · La recherche binaire nécessite que le tableau soit...
Binary search only works on sorted data. · La recherche binaire ne fonctionne que sur des données triées.
Each step of binary search... · Chaque étape de la recherche binaire...
It compares to the middle and keeps one half. · Il compare avec le milieu et conserve une moitié.
Binary search in [1,3,5,7,9] for 7: how many comparisons (middle each time)? · Recherche binaire dans [1,3,5,7,9] pour 7 : combien de comparaisons (milieu à chaque fois) ?
Compare to 5, then to 7 — two comparisons. · Compare à 5, puis à 7 — deux comparaisons.
Binary search gives correct results on an UNSORTED array. · La recherche binaire donne des résultats corrects sur un tableau NON TRIÉ.
It relies on order; unsorted data breaks it. · Elle repose sur l'ordre ; les données non triées la font échouer.
Match each search to its property. · Associez chaque recherche à sa propriété.
Linear is general but slower; binary is fast but needs order. · La recherche linéaire est universelle mais plus lente ; la recherche binaire est rapide mais nécessite un ordre.