Recherche séquentielle dans une liste en 1ère
Recherche séquentielle dans une liste, c'est une notion de mathématiques du chapitre « Algorithmique et programmation Python », au programme de 1ère. Voici le cours, un exemple et de quoi t'entraîner.
Recherche séquentielle dans une liste : le cours
La recherche séquentielle parcourt la liste élément par élément jusqu'à trouver ce qu'on cherche. C'est simple mais lent pour les grandes listes : on peut faire jusqu'à n comparaisons.
Exemple
Tu cherches le numéro de téléphone d'un ami dans un annuaire papier : tu lis page par page jusqu'à le trouver. Si la liste n'est pas triée, c'est la seule méthode.
À retenir
La recherche séquentielle a une complexité en $O(n)$ : elle parcourt toute la liste dans le pire cas.
S'entraîner sur recherche séquentielle dans une liste
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction recherche_dichotomie(liste, cible) qui cherche cible dans une liste triée et retourne son index (ou -1 si absent). Teste avec assert recherche_dichotomie([1, 3, 5, 7, 9], 5) == 2.
Corrige cet exercice avec le tuteur →Exercice 2
Écris une fonction tri_insertion(liste) qui trie une liste en place par insertion. Teste avec assert tri_insertion([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5].
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation Python (Mathématiques 1ère).