Diviser pour régner : recherche dichotomique en Terminale
Diviser pour régner : recherche dichotomique, c'est une notion de nsi du chapitre « Algorithmique avancée », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Diviser pour régner : recherche dichotomique : le cours
La recherche dichotomique divise un tableau trié en deux et élimine la moitié où l'élément ne peut pas être. Elle répète jusqu'à trouver l'élément en $O(\log n)$.
Exemple
Chercher un mot dans un dictionnaire : tu ouvres au milieu, tu vois si le mot est avant ou après, puis tu recommences dans la bonne moitié.
À retenir
La recherche dichotomique ne fonctionne que sur un tableau trié et est beaucoup plus rapide que la recherche linéaire.
S'entraîner sur diviser pour régner : recherche dichotomique
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction récursive avec mémoïsation pour calculer le nombre de façons de monter un escalier de n marches si tu peux monter 1 ou 2 marches à la fois. Quelle est la complexité sans et avec mémoïsation ?
Corrige cet exercice avec le tuteur →Exercice 2
Implémente un BFS pour trouver le chemin le plus court entre deux nœuds dans un graphe représenté par une liste d'adjacence. Pourquoi BFS et pas DFS ?
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).