Algorithmes de recherche
Introduit| English | Sens |
|---|---|
| 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é |
Trouver une valeur
- La recherche consiste à localiser une valeur cible dans une collection.
- Deux algorithmes standards : la recherche linéaire et la 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.
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).

La recherche linéaire vérifie chaque élément à tour de rôle jusqu'à ce que la cible soit trouvée

La recherche binaire divise la plage en deux à chaque étape
Recherche binaire
- Nécessite un tableau trié. Regardez l'élément central à chaque étape.
- 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.
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).
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).
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.
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.
Recherche linéaire vs binaire
La recherche binaire divise par deux la plage triée à chaque étape.
Une recherche linéaire...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Linéaire = début à fin ; fonctionne sur n'importe quel tableau.
La recherche binaire nécessite que le tableau soit...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
La recherche binaire ne fonctionne que sur des données triées.
Chaque étape de la recherche binaire...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Il compare avec le milieu et conserve une moitié.
Recherche binaire dans [1,3,5,7,9] pour 7 : combien de comparaisons (milieu à chaque fois) ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Compare à 5, puis à 7 — deux comparaisons.
La recherche binaire donne des résultats corrects sur un tableau NON TRIÉ.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Elle repose sur l'ordre ; les données non triées la font échouer.
Associez chaque recherche à sa propriété.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
La recherche linéaire est universelle mais plus lente ; la recherche binaire est rapide mais nécessite un ordre.