Recherche dichotomique NSI : 5 pièges à éviter absolument

La recherche dichotomique (ou recherche binaire) est un algorithme fondamental au programme de NSI. Il te permet de retrouver un élément dans une liste triée en un temps logarithmique, c'est-à-dire très rapidement. Mais attention : cet algorithme, pourtant simple en apparence, cache des pièges redoutables qui peuvent faire échouer ton programme ou pire, te faire perdre des points au bac. Dans cet article, on va décortiquer ensemble les erreurs les plus fréquentes et te donner les clés pour les éviter. Prêt ? C'est parti !

Pourquoi la recherche dichotomique est-elle si importante en NSI ?

Imagine que tu doives trouver un mot dans un dictionnaire de 1000 pages. Tu ne vas pas lire chaque page une par une, n'est-ce pas ? Tu vas ouvrir le dictionnaire au milieu, regarder si le mot est avant ou après, puis répéter l'opération sur la moitié restante. C'est exactement le principe de la recherche dichotomique.

En NSI, cet algorithme est étudié en Première et en Terminale, car il illustre parfaitement la notion de diviser pour régner. Il est aussi un excellent exemple pour comprendre la complexité algorithmique : sa complexité est en O(log n), ce qui est extrêmement efficace par rapport à une recherche linéaire en O(n).

Mais ce qui intéresse le plus les examinateurs, ce n'est pas seulement que tu saches l'implémenter, mais que tu comprennes les pièges qui se cachent derrière. Alors, faisons le tour de ces pièges ensemble.

Le piège n°1 : oublier que la liste doit être triée

La condition sine qua non de la recherche dichotomique est que la liste soit triée dans l'ordre croissant (ou décroissant, selon l'implémentation). Si tu l'utilises sur une liste non triée, l'algorithme peut te renvoyer une réponse fausse ou même ne jamais trouver l'élément, alors qu'il est présent !

Prenons un exemple simple :

ma_liste = [3, 1, 4, 1, 5, 9, 2, 6]
# Cette liste n'est pas triée !
# Si tu cherches 5 avec une recherche dichotomique, tu risques de ne pas le trouver.

Pour éviter ce piège, tu dois t'assurer que la liste est triée avant d'appeler la fonction. Tu peux utiliser la méthode sort() de Python pour trier la liste en place, ou bien créer une copie triée avec sorted() si tu veux préserver l'ordre original.

ma_liste_triee = sorted(ma_liste)
# Maintenant tu peux faire une recherche dichotomique en toute sécurité.

Le piège n°2 : se tromper dans la gestion des indices (borne inclusive ou exclusive)

C'est LE piège classique qui fait bugger tout le monde. La recherche dichotomique manipule deux indices : gauche et droite. La question cruciale est : est-ce que droite est inclus dans la zone de recherche ou non ?

Deux conventions existent :

• Borne inclusive : gauche et droite sont inclus dans la zone. Initialisation : gauche = 0, droite = len(liste) - 1.
• Borne exclusive : gauche est inclus, droite est exclus. Initialisation : gauche = 0, droite = len(liste).

Si tu mélanges les deux, tu obtiens des indices incorrects, des éléments manqués ou des boucles infinies. Par exemple, avec la borne inclusive, la condition de boucle doit être while gauche <= droite. Avec la borne exclusive, c'est while gauche < droite.

Voici une implémentation correcte avec la borne inclusive :

def recherche_dichotomique(liste, cible):
    gauche = 0
    droite = len(liste) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu
        elif liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1  # non trouvé

Et avec la borne exclusive :

def recherche_dichotomique_excl(liste, cible):
    gauche = 0
    droite = len(liste)  # droite est exclusive
    while gauche < droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu
        elif liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu
    return -1

Remarque la différence dans la mise à jour de droite : dans le cas exclusif, on fait droite = milieu et non milieu - 1, car milieu est déjà exclu.

Le piège n°3 : créer une boucle infinie

Une boucle infinie se produit lorsque les indices ne convergent pas vers une condition de sortie. Par exemple, si tu oublies de modifier gauche ou droite dans certains cas, ou si tu utilises milieu au lieu de milieu + 1 ou milieu - 1 dans la mise à jour.

Prenons un exemple erroné :

def mauvaise_recherche(liste, cible):
    gauche = 0
    droite = len(liste) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu
        elif liste[milieu] < cible:
            gauche = milieu  # Erreur : on ne progresse pas
        else:
            droite = milieu  # Erreur : on ne progresse pas
    return -1

Ici, si cible est plus grande que tous les éléments, gauche reste bloqué sur la même valeur, et la boucle ne se termine jamais. La bonne pratique est de faire gauche = milieu + 1 et droite = milieu - 1 pour la borne inclusive, ou gauche = milieu + 1 et droite = milieu pour la borne exclusive.

Le piège n°4 : ne pas gérer le cas où l'élément n'est pas présent

Que se passe-t-il si la cible n'est pas dans la liste ? Si ton algorithme ne prévoit pas ce cas, il peut renvoyer un indice invalide ou planter avec une erreur d'index. Il est crucial de retourner une valeur sentinelle, comme -1 ou None, pour indiquer que l'élément n'a pas été trouvé.

Dans les exemples précédents, on retourne -1. Mais assure-toi de toujours inclure cette gestion dans ta fonction. Un bon réflexe est de tester ta fonction avec une liste vide et avec une liste où la cible est absente.

Le piège n°5 : ignorer la récursivité (en Terminale)

En Terminale, on te demande souvent d'implémenter la recherche dichotomique de manière récursive. C'est un piège si tu n'as pas bien compris le principe, car il faut définir une fonction auxiliaire avec des paramètres supplémentaires pour les bornes.

Voici un exemple récursif correct :

def recherche_dichotomique_recursive(liste, cible, gauche, droite):
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if liste[milieu] == cible:
        return milieu
    elif liste[milieu] < cible:
        return recherche_dichotomique_recursive(liste, cible, milieu + 1, droite)
    else:
        return recherche_dichotomique_recursive(liste, cible, gauche, milieu - 1)

# Appel initial :
# resultat = recherche_dichotomique_recursive(ma_liste, 5, 0, len(ma_liste) - 1)

Attention à bien passer les nouvelles bornes, sinon tu risques de tomber dans une récursion infinie.

Mise en pratique : un exemple complet et testable

Pour t'aider à bien comprendre, voici un programme complet qui utilise la recherche dichotomique pour trouver un nombre dans une liste triée de nombres aléatoires.

import random

def recherche_dichotomique(liste, cible):
    gauche = 0
    droite = len(liste) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu
        elif liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

# Génère une liste triée de 20 entiers aléatoires entre 1 et 100
liste = sorted(random.sample(range(1, 101), 20))
print("Liste triée :", liste)

cible = random.choice(liste)  # On choisit un élément présent
indice = recherche_dichotomique(liste, cible)
print(f"L'élément {cible} est à l'indice {indice}.")

# Test avec un élément absent
cible_absente = 101
indice_abs = recherche_dichotomique(liste, cible_absente)
print(f"L'élément {cible_absente} donne l'indice {indice_abs} (attendu : -1).")

Teste ce code chez toi, modifie-le, casse-le volontairement pour voir les erreurs. C'est en expérimentant que tu mémoriseras les bonnes pratiques.

Conseils pour réussir au bac NSI

Lors de l'épreuve de NSI, tu peux être amené à écrire une recherche dichotomique de zéro ou à l'utiliser dans un exercice plus vaste. Voici mes conseils pour être serein le jour J :

• Vérifie toujours que la liste est triée avant d'appeler la fonction. Si ce n'est pas le cas, trie-la d'abord.
• Choisis une convention d'indices et tiens-t'y : inclusive ou exclusive. Note-la en commentaire pour toi-même.
• Teste ta fonction avec des cas limites : liste vide, liste à un élément, cible au début, à la fin, absente.
• Entraîne-toi à écrire la version récursive et itérative pour être prêt à toute demande.
• Commente ton code pour montuer ton raisonnement au correcteur

Pour approfondir, n'hésite pas à consulter les cours NSI et à t'entraîner avec les exercices NSI proposés sur le site. Tu peux aussi télécharger les fiches de révision pour avoir une synthèse pratique.

Si tu veux des ressources complémentaires, jette un œil à AlloBac et AlloLycée pour des cours en ligne et du soutien.

Conclusion : la dichotomie, un jeu d'enfant avec de la pratique

La recherche dichotomique est un algorithme puissant, mais qui demande de la rigueur. En évitant ces cinq pièges, tu seras capable de l'implémenter sans erreur. N'oublie pas : la clé, c'est la pratique. Refais les exercices, écris le code toi-même, et tu verras que ça deviendra un réflexe.

Alors, lance-toi, amuse-toi avec le code, et surtout, n'aie pas peur de faire des erreurs. C'est comme ça qu'on apprend ! Et si tu as des questions, n'hésite pas à les poser en classe ou sur les forums. Bonne chance pour tes révisions !