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 `recherche_max(tableau)` qui parcourt séquentiellement un tableau et retourne l'indice de l'élément maximum. Teste ta fonction avec l'assertion suivante : `assert recherche_max([3, 7, 2, 9, 1]) == 3`
Corrige cet exercice avec le tuteur →Exercice 2
Implémente l'algorithme de tri par insertion pour trier un tableau en ordre croissant. Explique le principe en 3-4 lignes, puis fournis le code avec des assertions de test.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation (NSI 1ère).