Numérique et sciences informatiques · Première · Algorithmique · 3.º Período

Recherche dichotomique

Mettre en œuvre l'algorithme de recherche dichotomique dans un tableau trié. Comparer son efficacité logarithmique avec la recherche séquentielle.

En bref:La recherche dichotomique illustre parfaitement la puissance de l'algorithmique. En passant d'une recherche séquentielle à une stratégie de 'diviser pour régner', les élèves découvrent comment réduire drastiquement le temps de traitement sur des données triées. C'est l'occasion de manipuler la fonction logarithme de manière concrète, en observant qu'on peut trouver un élément parmi un million en seulement vingt étapes.

• Programmes Officiels
• BOEN spécialité NSI 1re - Recherche dichotomique dans un tableau trié
• BOEN spécialité NSI 1re - Variant de boucle et coût logarithmique

À propos de ce thème

La recherche dichotomique illustre parfaitement la puissance de l'algorithmique. En passant d'une recherche séquentielle à une stratégie de 'diviser pour régner', les élèves découvrent comment réduire drastiquement le temps de traitement sur des données triées. C'est l'occasion de manipuler la fonction logarithme de manière concrète, en observant qu'on peut trouver un élément parmi un million en seulement vingt étapes.

Ce sujet exige une grande rigueur dans la gestion des indices (début, fin, milieu). L'apprentissage par l'erreur est ici très formateur : un mauvais calcul de l'indice médian ou une condition d'arrêt mal définie mène souvent à une boucle infinie. Les activités de groupe où les élèves doivent 'jouer' le rôle de l'algorithme sur un dictionnaire ou un annuaire papier renforcent la compréhension de cette efficacité redoutable.

Questions clés

1. Pourquoi le tableau doit-il être trié pour utiliser la dichotomie ?
2. Comment le nombre d'étapes évolue-t-il avec la taille du tableau ?
3. Comment prouver la terminaison avec un variant de boucle ?

Attention à ces idées reçues

Idée reçue courante

Oublier que le tableau doit être impérativement trié.

Ce qu'il faut enseigner à la place

Si le tableau n'est pas trié, la dichotomie peut éliminer la moitié contenant l'élément. Faire tester l'algorithme sur une liste non triée montre immédiatement pourquoi le résultat est imprévisible.

Idée reçue courante

Se tromper dans la mise à jour des bornes (milieu + 1 ou milieu - 1).

Ce qu'il faut enseigner à la place

Les élèves oublient souvent d'exclure l'élément central déjà testé. Dessiner l'évolution des bornes sur un axe gradué lors d'une séance de peer-teaching aide à visualiser pourquoi le +1/-1 est nécessaire pour éviter les boucles infinies.

Idées d'apprentissage actif

Jeu de rôle

Le juste prix

Un élève choisit un nombre entre 1 et 1000. La classe doit le deviner en utilisant la stratégie dichotomique. On note le nombre de tentatives pour valider l'efficacité logarithmique.

20 min·Classe entière

Cercle de recherche

Le bug de l'indice

Les élèves reçoivent trois versions d'un code de recherche dichotomique contenant des erreurs subtiles (indices, conditions). Ils doivent les identifier et les corriger en équipe.

40 min·Petits groupes

Penser-Partager-Présenter

Pourquoi trier ?

Les élèves discutent en binôme : est-il rentable de trier un tableau juste pour y faire une seule recherche ? Ils doivent lister les conditions où la dichotomie devient avantageuse.

25 min·Binômes

Questions fréquentes

Pourquoi la recherche dichotomique est-elle plus rapide ?

Parce qu'elle divise par deux le nombre d'éléments à examiner à chaque étape. Au lieu de regarder chaque élément, on élimine de vastes portions du tableau instantanément.

Quelle est la complexité de la recherche dichotomique ?

Sa complexité est logarithmique, notée O(log n). C'est extrêmement efficace : pour un tableau de taille 1 000 000, il ne faut que 20 étapes maximum.

Comment l'apprentissage actif aide-t-il à maîtriser la dichotomie ?

En pratiquant des jeux comme 'Le Juste Prix' ou en manipulant des annuaires, les élèves ressentent physiquement la rapidité de la convergence. Les activités de débogage en groupe sur les indices permettent de comprendre l'importance de la précision mathématique dans l'écriture des boucles.

Qu'est-ce qu'un variant de boucle pour la dichotomie ?

C'est une valeur qui décroît à chaque tour de boucle, ici la différence entre la borne haute et la borne basse. Cela prouve que l'algorithme finira par s'arrêter.