Réviser la recherche dichotomique en NSI en 30 min/jour

Tu bloques sur la recherche dichotomique en NSI ? Bonne nouvelle : c'est un algorithme court, logique et très rentable au bac. Avec 30 minutes de révision par jour et une méthode claire, tu peux le maîtriser en une semaine. Dans cet article, on voit ensemble la notion, le code Python, un cas concret, puis un planning de révision jour par jour.

La recherche dichotomique, c'est quoi exactement ?

La recherche dichotomique (on dit aussi recherche binaire) est un algorithme qui permet de savoir si une valeur est présente dans un tableau trié, et si oui, à quel indice. Son principe est simple : on coupe l'espace de recherche en deux à chaque étape, comme quand tu cherches un mot dans un dictionnaire papier.

Imagine un dictionnaire de 1000 pages. Tu cherches le mot « ordinateur ». Tu n'ouvres pas la page 1 pour avancer mot à mot. Tu ouvres au milieu, tu regardes si « ordinateur » est avant ou après, puis tu recommences dans la bonne moitié. C'est exactement la recherche binaire.

Pourquoi c'est beaucoup plus rapide ?

Comparons deux méthodes :

• Recherche linéaire : on regarde chaque case une par une. Sur un tableau de n éléments, ça peut prendre n comparaisons.
• Recherche dichotomique : on divise par 2 à chaque étape. Sur 1 000 000 d'éléments, il faut seulement environ 20 comparaisons.

Mathématiquement, la complexité de la recherche dichotomique est O(log n), alors que la recherche linéaire est O(n). C'est une différence énorme quand les données grossissent. C'est pour ça que la recherche dichotomique NSI est un classique du programme.

La condition indispensable : le tableau doit être trié

Attention, piège classique : la recherche dichotomique ne fonctionne que sur un tableau trié (ordre croissant en général). Si le tableau n'est pas trié, l'algorithme peut renvoyer un faux résultat. Au bac, on te le rappellera souvent : soit le tableau est donné trié, soit tu dois d'abord le trier.

Le code Python de la recherche dichotomique

Voici une version itérative, celle que tu utiliseras le plus souvent en NSI. Elle est courte, lisible et testable.

def recherche_dichotomique(tableau, valeur):
    """Renvoie l'indice de valeur dans tableau trié, ou -1 si absent."""
    debut = 0
    fin = len(tableau) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tableau[milieu] == valeur:
            return milieu
        elif tableau[milieu] < valeur:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1

Décortiquons ce code ligne par ligne :

• debut et fin délimitent la zone dans laquelle on cherche.
• milieu = (debut + fin) // 2 : la division entière donne l'indice du milieu.
• Si tableau[milieu] est égal à la valeur, on a trouvé, on renvoie l'indice.
• Si la valeur du milieu est plus petite, alors la valeur cherchée est à droite : on déplace debut.
• Sinon, elle est à gauche : on déplace fin.
• Si la boucle se termine sans rien trouver, on renvoie -1.

Version récursive (bonus programme)

La version récursive est aussi au programme, et elle tombe parfois au bac. La voici :

def recherche_dicho_rec(tableau, valeur, debut, fin):
    if debut > fin:
        return -1
    milieu = (debut + fin) // 2
    if tableau[milieu] == valeur:
        return milieu
    elif tableau[milieu] < valeur:
        return recherche_dicho_rec(tableau, valeur, milieu + 1, fin)
    else:
        return recherche_dicho_rec(tableau, valeur, debut, milieu - 1)

Les deux versions font la même chose. La version itérative est souvent plus simple à écrire sous pression le jour de l'épreuve. Choisis celle que tu maîtrises le mieux.

Un cas concret : chercher un élève dans une liste triée

Imaginons que ton lycée stocke les notes d'un contrôle dans un tableau trié par ordre croissant. Tu veux savoir si la note 15 est présente.

notes = [3, 7, 8, 11, 12, 15, 17, 18, 19]
print(recherche_dichotomique(notes, 15))  # affiche 5
print(recherche_dichotomique(notes, 10))  # affiche -1

Déroulons les étapes pour la valeur 15 :

• debut = 0, fin = 8, milieu = 4 → notes[4] = 12, trop petit, on va à droite.
• debut = 5, fin = 8, milieu = 6 → notes[6] = 17, trop grand, on va à gauche.
• debut = 5, fin = 5, milieu = 5 → notes[5] = 15, trouvé ! On renvoie 5.

En 3 étapes seulement, sur 9 éléments. Sur 1 000 000 d'éléments, ce serait environ 20 étapes. Voilà la force de la recherche binaire.

Erreurs fréquentes à éviter

• Oublier que le tableau doit être trié.
• Écrire debut = milieu au lieu de debut = milieu + 1 : boucle infinie.
• Utiliser / au lieu de // : milieu devient un flottant, erreur d'indice.
• Confondre < et <= dans la condition du while.

Réviser en 30 minutes par jour : le planning

Pas besoin d'y passer des heures. Voici un planning réaliste sur 7 jours, à raison de 30 minutes par jour. Tu peux t'appuyer sur les cours NSI et les exercices NSI du site pour t'entraîner.

Jour 1 — Comprendre la notion (30 min)

Lis le cours, retiens la condition du tableau trié et la complexité O(log n). Écris l'algorithme en français sur une feuille, sans code.

Jour 2 — Écrire le code à la main (30 min)

Recopie la version itérative de mémoire. Puis teste-la dans un éditeur Python avec un petit tableau. Corrige tes erreurs.

Jour 3 — Tracer l'exécution (30 min)

Prends un tableau de 8 valeurs et note sur papier les valeurs de debut, fin et milieu à chaque étape. C'est l'exercice le plus formateur.

Jour 4 — Exercices variés (30 min)

Fais 3 exercices : valeur présente, valeur absente, tableau d'un seul élément. Compare avec la version récursive.

Jour 5 — Annales du bac (30 min)

Cherche un sujet de bac NSI qui parle de recherche dichotomique. Rédige la réponse comme le jour J, chrono en main.

Jour 6 — Fiche mémo (30 min)

Crée ta fiche : définition, condition, code, complexité, erreurs fréquentes. Range-la dans tes fiches NSI.

Jour 7 — Auto-évaluation (30 min)

Reprends tous les exercices sans regarder. Si tu réussis, c'est bon. Sinon, refais les jours 2 et 3.

Cette méthode marche aussi pour d'autres algorithmes du programme. Si tu veux élargir, jette un œil aux ressources d'Allolycée et d'Allobac pour compléter tes révisions.

Lien avec l'épreuve du bac NSI

Au bac NSI, la recherche dichotomique peut apparaître sous plusieurs formes :

• Écrire l'algorithme complet en Python.
• Compléter un code à trous.
• Analyser la complexité et comparer avec la recherche linéaire.
• Tracer l'exécution étape par étape sur un tableau donné.

Ce qui est évalué, c'est ta capacité à expliquer et à écrire l'algorithme proprement. Entraîne-toi à écrire les commentaires : ils montrent que tu comprends ce que tu fais.

Astuce pour gagner des points

N'oublie jamais de préciser en début de réponse : « le tableau doit être trié par ordre croissant ». C'est une phrase qui rapporte souvent des points, car elle montre que tu connais les prérequis de l'algorithme.

Conclusion : 30 minutes par jour, et c'est acquis

La recherche dichotomique NSI n'est pas un monstre. C'est un algorithme court, logique, et très bien payé au bac. En 30 minutes par jour pendant une semaine, tu peux le comprendre, l'écrire et le restituer sous pression. Commence par le cours, trace à la main, code en Python, puis entraîne-toi sur des annales. Et surtout : répète régulièrement, car la mémoire aime les révisions espacées. Tu vas y arriver 💪