Recherche dichotomique en 1ère
Recherche dichotomique, c'est une notion de nsi du chapitre « Algorithmique et programmation », au programme de 1ère. Voici le cours, un exemple et de quoi t'entraîner.
Recherche dichotomique : le cours
Méthode rapide pour trouver un élément dans un tableau trié en divisant l'espace de recherche par deux à chaque étape. On compare avec l'élément du milieu et on élimine la moitié inutile.
Exemple
Chercher un mot dans un dictionnaire : au lieu de lire page par page, tu ouvres au milieu, tu vois si le mot est avant ou après, et tu recommences dans la bonne moitié.
À retenir
La recherche dichotomique est beaucoup plus rapide qu'une recherche linéaire sur un tableau trié.
S'entraîner sur recherche dichotomique
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction qui recherche un nombre dans une liste triée en utilisant la recherche dichotomique. Teste-la avec assert pour vérifier qu'elle retourne l'index correct ou -1 si le nombre n'existe pas.
Corrige cet exercice avec le tuteur →Exercice 2
Crée une fonction tri_par_insertion(liste) qui trie une liste en utilisant le tri par insertion. Utilise des assertions pour vérifier que la liste retournée est bien triée et contient les mêmes éléments.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation (NSI 1ère).