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
Soit la fonction récursive suivante : ```python def mystere(n): if n == 0: return 1 else: return n * mystere(n - 1) ``` 1. Identifiez le cas de base et le cas récursif. 2. Tracez l'exécution de mystere(4) en dessinant la pile d'appels. 3. Que calcule cette fonction ?
Corrige cet exercice avec le tuteur →Exercice 2
On souhaite implémenter la **recherche dichotomique** sur un tableau trié. 1. Écrivez une fonction récursive `recherche_dichotomique(tab, cible, gauche, droite)` qui retourne l'indice de `cible` dans `tab`, ou -1 si absent. 2. Analysez la complexité temporelle en fonction de la taille n du tableau. 3. Testez avec `tab = [1, 3, 5, 7, 9, 11]` et `cible = 7`.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).