Recherche
Rechercher dans une liste
- Rechercher signifie trouver si une valeur est dans une liste, et où.
- La réponse habituelle est l'index de la valeur, ou
-1si elle est absente. - Deux méthodes classiques sont la recherche linéaire et la recherche binaire.
Recherche linéaire
- Vérifiez chaque élément à tour de rôle, depuis le début.
- Arrêtez dès que vous trouvez une correspondance.
- Ça marche sur n'importe quelle liste, triée ou non.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Recherche binaire
- La recherche binaire nécessite une liste triée.
- Regardez l'élément du milieu. S'il est la cible, arrêtez.
- Si la cible est plus petite, cherchez dans la moitié gauche ; si plus grande, dans la droite.
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
Comparez-les
- La recherche linéaire peut vérifier chaque élément — lent pour une longue liste.
- La recherche binaire jette moitié de la liste à chaque étape, donc elle est beaucoup plus rapide.
- Mais la recherche binaire ne fonctionne que si les données sont déjà triées.
En pseudocode Cambridge
- Notez que
DIVest une division entière (la//de Python). - Les tableaux de Cambridge s'exécutent généralement de 1 à
n, le nombre d'éléments.LENGTH()est réservé aux chaînes, donc les boucles utilisentn.
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
Erreurs courantes
- La recherche binaire nécessite une liste triée ; elle divise la plage par deux à chaque étape.
- La recherche linéaire fonctionne sur n'importe quelle liste mais est plus lente.
À vous maintenant
- Retournez l'index de la valeur, ou
-1lorsqu'elle n'est pas trouvée. - Appuyez sur Vérifier la réponse pour tester votre code.
Recherche linéaire vs binaire
La recherche binaire moitié la liste à chaque étape — bien moins de comparaisons.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez linear_search(items, target) qui retourne l'index de target dans items, ou -1 si elle n'y est pas. Vérifiez les éléments un par un.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez binary_search(items, target) pour une liste triée. Returnez l'index de target, ou -1 si elle est absente. Moitiéz la plage à chaque étape.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez first_negative(items) qui parcourt la liste et retourne l'index du premier nombre inférieur à 0, ou -1 s'il n'y en a aucun.
Cliquez sur Exécuter pour voir le résultat ici.