Algorithms: searching · Algorithmes : recherche
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
Ce que nous allons faire
- Un algorithme est une liste claire d'étapes qui résout un problème.
- Un travail très courant est la recherche : trouver où se trouve une valeur dans une liste.
- Nous apprendrons deux algorithmes : la recherche linéaire et la recherche binaire.
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
Recherche linéaire
- Vérifiez les éléments un par un, du début à la fin.
- Si vous trouvez la valeur, retournez son indice (position).
- Si vous arrivez à la fin sans jamais la trouver, retournez
-1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
Pourquoi une liste triée aide
- La recherche linéaire fonctionne sur n'importe quelle liste, même désordonnée.
- Mais si la liste est triée (petit à grand), nous pouvons être beaucoup plus rapides.
- La recherche binaire utilise l'ordre trié pour sauter la moitié de la liste à chaque fois.
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
Recherche binaire
- Regardez l'élément du milieu.
- S'il correspond à la cible, c'est fini.
- Si la cible est plus petite, cherchez dans la moitié gauche ; si plus grande, dans la moitié droite. Répétez.
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
Assembler les idées
- Une recherche combine trois blocs de construction que vous connaissez déjà.
- Séquencement : faites les étapes dans l'ordre. Sélection :
if/elif/else. - Itération : une boucle (
forouwhile) répète la vérification.
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
En pseudocode AP CSP
- L'examen écrit une boucle et une vérification comme ceci.
FOR EACHvisite chaque élément ;IFsélectionne ;REPEAT UNTILboucle jusqu'à ce qu'un test soit vrai.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
Erreurs courantes
- La recherche binaire nécessite une liste triée.
- La recherche linéaire vérifie chaque élément à son tour.
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
À vous maintenant
- Chaque tâche donne un nom de procédure et ce qu'elle doit retourner.
- Appuyez sur Vérifier la réponse pour tester votre code.
Searching a list · Recherche dans une liste
Binary search needs a sorted list but is far faster than linear. · La recherche binaire nécessite une liste triée mais est bien plus rapide que la recherche linéaire.
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one. · Écrivez linear_search(lst, target). Retournez l'index de target dans lst, 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(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time. · Écrivez binary_search(sorted_lst, target) pour une liste triée de petit à grand. Retournez l'index de target, ou -1. Regardez le milieu et divisez la recherche par deux à chaque fois.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write contains(lst, target) that returns True if · si target is in lst, else False. You may reuse linear search and compare the result to -1. · Écrivez contains(lst, target) qui retourne True si target est dans lst, sinon False. Vous pouvez réutiliser la recherche linéaire et comparer le résultat à -1.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.