Recherche par dichotomie en 1ère
Recherche par dichotomie, 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 par dichotomie : le cours
La dichotomie est une recherche rapide dans une liste triée. On coupe la liste en deux, on compare avec le milieu, et on garde seulement la moitié pertinente. On répète jusqu'à trouver l'élément.
Exemple
Tu cherches un mot dans le dictionnaire : tu ouvres au milieu, tu vois si ton mot est avant ou après, tu jettes la moitié inutile, et tu recommences. Beaucoup plus rapide que de lire page par page.
À retenir
La dichotomie a une complexité en $O(\log n)$ : elle divise par 2 à chaque étape, donc elle est très rapide.
S'entraîner sur recherche par dichotomie
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).