Quelle est la différence entre recherche dichotomique et recherche binaire ?

Aucune : ce sont deux noms pour le même algorithme. On dit aussi 'recherche par dichotomie'. Le terme 'binaire' vient du fait qu'on divise l'espace de recherche en deux à chaque étape.

Pourquoi la recherche dichotomique nécessite-t-elle un tableau trié ?

Parce que l'algorithme compare la valeur cherchée à l'élément du milieu pour décider dans quelle moitié continuer. Sans tri, cette décision n'a aucun sens et la recherche peut échouer.

Comment écrire la recherche dichotomique en Python ?

On utilise une boucle while avec deux bornes gauche et droite. On calcule milieu = (gauche + droite) // 2, puis on ajuste gauche ou droite selon la comparaison. Voir l'exemple complet dans l'article.

Quelle erreur classique faut-il éviter dans la recherche dichotomique ?

Oublier d'ajouter +1 ou -1 lors du déplacement des bornes (gauche = milieu + 1, droite = milieu - 1). Sans cela, la boucle peut devenir infinie.

La recherche dichotomique est-elle au programme du bac NSI ?

Oui, elle fait partie des algorithmes fondamentaux au programme de Première et Terminale NSI. Elle peut être demandée à l'écrit comme à l'épreuve pratique.

Recherche dichotomique NSI : la checklist pour réussir

Q: Quelle est la complexité de la recherche dichotomique ?

Elle est en O(log n) : à chaque étape, on divise la taille du problème par 2. Pour un tableau de 1 000 000 d'éléments, il faut environ 20 comparaisons.

Tu prépares le bac NSI et tu entends parler de la recherche dichotomique à chaque coin de cours ? Pas de panique : c'est un algorithme classique, très souvent demandé à l'épreuve écrite et pratique. Dans cet article, on te donne une vraie checklist pour la comprendre, la coder en Python et la réviser efficacement. À la fin, tu sauras pourquoi on dit que la recherche binaire est l'une des méthodes les plus élégantes de l'informatique.

1. C'est quoi la recherche dichotomique (ou recherche binaire) ?

La recherche dichotomique, aussi appelée recherche binaire, est un algorithme qui permet de savoir si une valeur est présente dans un tableau trié, et si oui, à quelle position. Son principe est simple : à chaque étape, on coupe l'espace de recherche en deux.

Imagine un dictionnaire papier. Pour trouver le mot « pomme », tu ne commences pas à la page 1. Tu ouvres au milieu, tu compares, puis tu continues dans la moitié qui contient « pomme ». C'est exactement ce que fait l'algorithme.

Les conditions indispensables

Le tableau doit être trié (par ordre croissant en général).
On travaille sur des indices : on garde une borne gauche et une borne droite.
À chaque tour, on regarde l'élément du milieu et on élimine la moitié inutile.

Si le tableau n'est pas trié, la recherche dichotomique ne fonctionne pas. Il faudra d'abord le trier (avec un tri par insertion, par sélection ou sorted() en Python).

Pourquoi c'est si rapide ?

Parce qu'à chaque comparaison on divise la taille du problème par 2. Pour un tableau de 1 000 000 d'éléments, il ne faut qu'environ 20 comparaisons ! C'est ce qu'on appelle une complexité logarithmique, notée O(log n). À comparer avec la recherche linéaire, en O(n), qui examinerait jusqu'à 1 000 000 d'éléments.

2. L'algorithme étape par étape

Voici la version itérative, celle qu'on te demandera le plus souvent en NSI. On cherche la valeur x dans un tableau t trié par ordre croissant.

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

Décortiquons ce code :

gauche et droite délimitent la zone où x peut encore se trouver.
// est la division entière : indispensable pour obtenir un indice entier.
Si t[milieu] < x, alors x est forcément à droite : on décale gauche.
Sinon, x est à gauche : on décale droite.
Quand gauche > droite, la zone est vide : la valeur n'est pas là.

Version récursive (bonus bac)

Le programme NSI mentionne aussi la version récursive. La voici, plus courte mais parfois moins intuitive :

def recherche_rec(t, x, gauche, droite):
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if t[milieu] == x:
        return milieu
    elif t[milieu] < x:
        return recherche_rec(t, x, milieu + 1, droite)
    else:
        return recherche_rec(t, x, gauche, milieu - 1)

Retiens bien la condition d'arrêt gauche > droite : c'est elle qui empêche la récursion infinie.

3. Mise en pratique : exemple concret

Testons sur un tableau trié de notes :

notes = [3, 7, 9, 12, 14, 15, 17, 18, 20]
print(recherche_dichotomique(notes, 14))  # affiche 4
print(recherche_dichotomique(notes, 10))  # affiche -1

Regardons le déroulement pour x = 14 :

gauche = 0, droite = 8, milieu = 4 → t[4] = 14 → trouvé !

Un coup de chance. Prenons x = 17 :

milieu = 4, t[4] = 14 < 17 → gauche = 5
milieu = (5+8)//2 = 6, t[6] = 17 → trouvé à l'indice 6

En seulement 2 comparaisons, on a trouvé la valeur. C'est ça la puissance de la dichotomie.

Un cas d'usage réel : annuaire de contacts

Imagine un annuaire de 50 000 contacts triés par nom. La recherche dichotomique te permet de trouver un contact en moins de 17 comparaisons. C'est pour cela que les bases de données et les moteurs de recherche utilisent des structures basées sur ce principe (arbres binaires, index).

4. Les erreurs classiques à éviter

Oublier le +1 / -1 : écrire gauche = milieu au lieu de milieu + 1 provoque une boucle infinie.
Ne pas trier le tableau : la dichotomie ne fonctionne que sur un tableau trié.
Confondre indice et valeur : la fonction renvoie la position, pas la valeur.
Mauvaise borne initiale : droite = len(t) au lieu de len(t) - 1 provoque une erreur d'indice.
Oublier le cas vide : un tableau vide doit renvoyer -1 sans planter.

Pour t'entraîner sur ces pièges, direction nos exercices NSI : tu y trouveras des tableaux à corriger et des QCM.

5. Méthode de révision et lien avec le bac NSI

La recherche dichotomique tombe régulièrement à l'épreuve écrite (partie algorithmique) et peut apparaître en pratique. Voici ta checklist de révision :

Savoir écrire la version itérative sans hésiter, en 5 minutes.
Savoir expliquer pourquoi la complexité est O(log n).
Savoir justifier la nécessité d'un tableau trié.
Savoir tracer l'exécution sur un petit tableau (les correcteurs adorent).
Savoir comparer avec la recherche linéaire (avantages/inconvénients).

Consulte nos fiches de révision pour des synthèses rapides, et nos cours NSI pour approfondir les algorithmes de tri et de recherche.

Astuce pour l'oral et l'écrit

Quand tu expliques la dichotomie, utilise toujours une métaphore : « annuaire », « dictionnaire », « jeu du plus ou moins ». Les examinateurs apprécient les explications claires. Et si tu veux aller plus loin, le réseau Allolycée propose des ressources complémentaires pour préparer le bac, tandis que Allobac t'aide à organiser tes révisions.

6. Conclusion : à toi de jouer !

La recherche dichotomique est un incontournable de la NSI. Avec cette checklist, tu as toutes les cartes en main : comprendre le principe, coder en Python, éviter les pièges et réviser intelligemment. Entraîne-toi régulièrement, trace des exemples à la main, et n'oublie jamais que la dichotomie n'a de sens que sur un tableau trié.

Alors, prêt à diviser pour mieux régner ? Ouvre ton éditeur Python et code ta première recherche binaire dès aujourd'hui. 💪