Recherche dichotomique : diviser pour regner

Pourquoi la recherche dichotomique est-elle si puissante ?

Imagine que tu cherches un mot dans un dictionnaire. Tu ne vas pas le lire page par page, n'est-ce pas ? Tu l'ouvres au milieu, et selon le mot que tu cherches, tu continues dans la première ou la seconde moitié. Tu répètes cette opération jusqu'à trouver. C'est exactement le principe de la recherche dichotomique (ou binary search). C'est un algorithme de recherche incroyablement efficace, à condition que les données dans lesquelles tu cherches soient triées.

Comparée à une recherche séquentielle (parcourir tous les éléments un par un), qui a une complexité en O(n), la recherche dichotomique a une complexité en O(log n). Cela signifie que pour chercher dans un tableau d'un million d'éléments, elle ne nécessitera au pire qu'une vingtaine d'étapes, contre un million pour la recherche séquentielle ! C'est l'illustration parfaite de la stratégie « diviser pour régner » (divide and conquer).

Le principe pas à pas

L'algorithme fonctionne sur un intervalle défini par deux indices : gauche (début) et droite (fin).

1. Initialisation : On pose gauche = 0 et droite = len(tableau) - 1.
2. Condition de boucle : Tant que gauche <= droite, on continue.
3. Calcul du milieu : On calcule l'indice du milieu : milieu = (gauche + droite) // 2 (division entière).
4. Comparaison :
   • Si tableau[milieu] == cible : Victoire ! On a trouvé l'élément, on retourne son indice milieu.
   • Si tableau[milieu] < cible : La cible est potentiellement dans la moitié droite. On réduit l'intervalle : gauche = milieu + 1.
   • Si tableau[milieu] > cible : La cible est potentiellement dans la moitié gauche. On réduit l'intervalle : droite = milieu - 1.
5. Résultat : Si la boucle se termine sans avoir trouvé la cible, celle-ci n'est pas dans le tableau. On retourne généralement -1 ou None.

Implémentation en Python

Voici une implémentation classique et propre de l'algorithme en Python. Étudie-la ligne par ligne.

def recherche_dichotomique(tableau, cible):
    """
    Renvoie l'indice de `cible` dans le `tableau` trié.
    Renvoie -1 si l'élément n'est pas présent.
    """
    gauche = 0
    droite = len(tableau) - 1

    while gauche <= droite:
        milieu = (gauche + droite) // 2  # Division entière

        if tableau[milieu] == cible:
            return milieu  # Élément trouvé !
        elif tableau[milieu] < cible:
            # On cherche dans la moitié droite
            gauche = milieu + 1
        else:  # tableau[milieu] > cible
            # On cherche dans la moitié gauche
            droite = milieu - 1

    return -1  # Élément non trouvé

# Exemple d'utilisation
mes_notes = [8, 10, 12, 15, 17, 19, 20]
indice = recherche_dichotomique(mes_notes, 17)
print(f"La note 17 est à l'indice {indice}")  # Affiche : La note 17 est à l'indice 4

Points d'attention

Quelques détails cruciaux pour éviter les bugs :

• Tableau trié : L'algorithme ne fonctionne pas si le tableau n'est pas trié au préalable. C'est sa principale contrainte.
• Gestion des bornes : Bien mettre milieu + 1 et milieu - 1 pour réduire l'intervalle. Si on oublie le +1 ou -1, on risque une boucle infinie dans certains cas.
• Opérateur // : On utilise la division entière pour obtenir un indice valide.

Complexité et avantages

La force de la recherche dichotomique réside dans sa complexité logarithmique. À chaque étape, on divise la taille du problème par deux.

Petit rappel sur la complexité : Une complexité en O(log n) est extrêmement efficace pour de grandes quantités de données. Le logarithme (en base 2) croît très lentement.

Comparaison avec la recherche linéaire (séquentielle) :

L'avantage est écrasant ! Cependant, n'oublie pas le coût initial du tri. Si tes données ne sont pas triées et que tu ne fais qu'une seule recherche, il peut être plus rapide de faire une recherche linéaire. La dichotomique est intéressante quand le tableau est déjà trié, ou quand tu vas effectuer de nombreuses recherches sur le même jeu de données.

Applications et exercices pour t'entraîner

La recherche dichotomique n'est pas qu'un exercice académique. Elle est partout :

• Dans les systèmes de fichiers pour localiser rapidement une entrée.
• Dans les bases de données pour les recherches sur des index triés.
• Dans les algorithmes de résolution de problèmes plus complexes (comme trouver la racine carrée avec une précision donnée).

Exercices pour toi :

1. Modification : Adapte la fonction pour qu'elle renvoie True ou False selon la présence de l'élément.
2. Première occurrence : Modifie l'algorithme pour qu'il trouve l'indice de la première occurrence d'un élément dans un tableau qui peut contenir des doublons.
3. Insertion : Écris une fonction qui, étant donné un tableau trié et un élément, renvoie l'indice où cet élément devrait être inséré pour conserver l'ordre du tableau. C'est très utile !