Searching · Recherche
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
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.
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
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)
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
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)
Compare them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
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.
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
En pseudocode Cambridge
- Notez que
DIVest une division entière (la//de Python).
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
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.
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
À 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.
Linear vs binary search · Recherche linéaire vs binaire
Binary search · Recherche binaire halves the list each step — far fewer comparisons. · La recherche binaire moitié la liste à chaque étape — bien moins de comparaisons.
Write linear_search(items, target) that returns · rendements the index of target in items, or -1 if it is not there. Check the items one by one. · É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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step. · É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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write first_negative(items) that scans the list and returns · rendements the index of the first number less than 0, or -1 if there are none. · É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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.