🔍 La Recherche Dichotomique

❓ Qu'est-ce que la recherche dichotomique ?

📖 Définition

La dichotomie est une méthode de recherche qui permet de trouver rapidement un élément dans une liste triée en divisant récursivement l'espace de recherche par deux.

C'est comme chercher quelqu'un dans un annuaire téléphonique : au lieu de lire page par page, vous ouvrez au milieu et décidez de continuer à gauche ou à droite.

⚙️ Principe Fondamental

Le principe de la recherche dichotomique repose sur trois étapes simples :

1 Commencer au milieu de la liste

2 Comparer l'élément recherché avec la valeur médiane

3 Éliminer la moitié de la liste qui ne peut pas contenir l'élément

⚠️ Condition Préalable : La liste doit être triée (par ordre croissant ou décroissant)

🐍 Algorithme en Pseudocode

fonction recherche_dichotomique(liste, valeur):
    debut ← 0
    fin ← longueur(liste) - 1

    tant que debut <= fin:
        milieu ← (debut + fin) // 2
        si liste[milieu] == valeur:
            retourner milieu  # L'indice où se trouve la valeur
        sinon si liste[milieu] < valeur:
            debut ← milieu + 1
        sinon:
            fin ← milieu - 1

    retourner -1  # La valeur n'est pas dans la liste