La Recherche Binaire (Dichotomie) : Principe, Complexité et Implémentation

Qu'est-ce que la recherche binaire ?

La recherche binaire, aussi appelée dichotomie, est un algorithme permettant de trouver un élément dans un tableau trié en un temps logarithmique. Au lieu de parcourir le tableau du début à la fin (O(n)), elle divise l'espace de recherche par deux à chaque étape, atteignant une complexité de O(log n).

C'est l'un des algorithmes les plus fréquemment utilisés en programmation compétitive, notamment sur France IOI.

Prérequis : un tableau trié

La recherche binaire ne fonctionne que sur des données triées. C'est sa condition sine qua non. Si votre tableau n'est pas trié, commencez par le trier.

Principe de fonctionnement

1. On définit deux pointeurs : gauche = 0 et droite = n - 1.
2. On calcule le milieu : milieu = (gauche + droite) // 2.
3. Si tableau[milieu] == cible → trouvé !
4. Si tableau[milieu] < cible → la cible est dans la moitié droite : gauche = milieu + 1.
5. Si tableau[milieu] > cible → la cible est dans la moitié gauche : droite = milieu - 1.
6. On répète jusqu'à trouver ou jusqu'à ce que gauche > droite.

Implémentation en Python

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

# Exemple
tab = [2, 5, 8, 12, 16, 23, 38, 42]
print(recherche_binaire(tab, 23))  # Affiche 5

Implémentation en C++

#include <iostream>
using namespace std;

int rechercheBinaire(int tab[], int n, int cible) {
    int gauche = 0, droite = n - 1;
    while (gauche <= droite) {
        int milieu = (gauche + droite) / 2;
        if (tab[milieu] == cible) return milieu;
        else if (tab[milieu] < cible) gauche = milieu + 1;
        else droite = milieu - 1;
    }
    return -1;
}

Complexité

Cas	Complexité
Meilleur cas (élément au milieu)	O(1)
Cas moyen	O(log n)
Pire cas	O(log n)
Espace mémoire	O(1)

Applications en programmation compétitive

• Recherche d'un élément : cas classique vu ci-dessus.
• Recherche de la première/dernière occurrence d'un élément dupliqué.
• Dichotomie sur la réponse : très puissant — on « devine » la réponse et on vérifie si elle est réalisable.
• Trouver un seuil : trouver le plus petit x tel qu'une condition f(x) est vraie.

Pièges classiques

• Dépassement d'entier : en C++, préférez milieu = gauche + (droite - gauche) / 2 pour éviter les overflows.
• Condition de boucle : gauche <= droite et non gauche < droite, sinon vous ratez l'élément seul.
• Off-by-one : bien vérifier que gauche = milieu + 1 et droite = milieu - 1 pour éviter les boucles infinies.

Conclusion

La recherche binaire est un outil fondamental que tout programmeur compétitif doit maîtriser. Sa puissance vient de sa capacité à réduire drastiquement l'espace de recherche. Une fois le principe assimilé, vous pourrez l'appliquer à des problèmes bien plus complexes, notamment la "dichotomie sur la réponse".