Algorithmes : recherche
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.
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))
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.
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))
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.
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)
}
Erreurs courantes
- La recherche binaire nécessite une liste triée.
- La recherche linéaire vérifie chaque élément à son tour.
À 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.
Recherche dans une liste
La recherche binaire nécessite une liste triée mais est bien plus rapide que la recherche linéaire.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
É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.
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(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.
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 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.
Cliquez sur Exécuter pour voir le résultat ici.