la recherche dichotomique

Recherche dichotomique (Binary Search)

Étant donné un tableau trié tab[] de n éléments, écrivez une fonction pour rechercher un élément donné x dans tab[].

Figure : Principe de la recherche dichotomique - à chaque étape, on élimine la moitié du tableau

La recherche dichotomique consiste à rechercher dans un tableau trié en divisant de manière récursive l'intervalle de recherche en deux. Commencez par un intervalle couvrant tout le tableau. Si la valeur de la clé de recherche est inférieure à l'élément situé au milieu de l'intervalle, limitez l'intervalle à la moitié inférieure. Sinon, le réduire à la moitié supérieure. Vérifiez à plusieurs reprises jusqu'à ce que la valeur soit trouvée ou que l'intervalle soit vide.

L'idée de la recherche dichotomique est de profiter du tableau trié et de réduire la complexité à O(log n), ce qui est exponentiellement plus rapide que la recherche linéaire O(n) pour de grands ensembles de données.

Implémentation récursive de la recherche dichotomique

FONCTION RechercheDichotomique(tab, debut, fin, x):
    SI fin >= debut ALORS
        milieu ← (debut + fin) // 2
        
        SI tab[milieu] == x ALORS
            RETOURNER milieu
        SINON SI tab[milieu] > x ALORS
            RETOURNER RechercheDichotomique(tab, debut, milieu-1, x)
        SINON
            RETOURNER RechercheDichotomique(tab, milieu+1, fin, x)
        FINSI
    SINON
        RETOURNER -1   // Élément non trouvé
    FINSI
FINFONCTION

def recherche_dichotomique_recursive(tab, debut, fin, x):
    """
    Recherche récursive d'un élément x dans un tableau trié.
    
    Paramètres:
        tab: tableau trié
        debut: indice de début de la recherche
        fin: indice de fin de la recherche
        x: élément recherché
    
    Retourne:
        L'indice de l'élément s'il est trouvé, -1 sinon
    """
    if fin >= debut:
        milieu = (debut + fin) // 2
        
        # Élément trouvé au milieu
        if tab[milieu] == x:
            return milieu
        
        # Si x est plus petit, chercher dans la moitié gauche
        elif tab[milieu] > x:
            return recherche_dichotomique_recursive(tab, debut, milieu - 1, x)
        
        # Sinon, chercher dans la moitié droite
        else:
            return recherche_dichotomique_recursive(tab, milieu + 1, fin, x)
    
    # Élément non trouvé
    return -1


# Test de la fonction
tab = [2, 7, 8, 20, 25, 30, 33, 39, 45, 50]
x = 8

resultat = recherche_dichotomique_recursive(tab, 0, len(tab) - 1, x)

if resultat != -1:
    print(f"L'élément {x} est présent à l'indice {resultat}")
else:
    print(f"L'élément {x} n'est pas présent dans le tableau")

L'élément 8 est présent à l'indice 2

Implémentation itérative de la recherche dichotomique

La version itérative utilise une boucle while au lieu de la récursion, ce qui évite l'utilisation de la pile d'appels et peut être plus efficace en termes de mémoire.

def recherche_dichotomique_iterative(tab, x):
    """
    Recherche itérative d'un élément x dans un tableau trié.
    
    Paramètres:
        tab: tableau trié
        x: élément recherché
    
    Retourne:
        L'indice de l'élément s'il est trouvé, -1 sinon
    """
    debut = 0
    fin = len(tab) - 1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        
        if tab[milieu] == x:
            return milieu
        
        elif tab[milieu] < x:
            # Chercher dans la moitié droite
            debut = milieu + 1
        
        else:
            # Chercher dans la moitié gauche
            fin = milieu - 1
    
    # Élément non trouvé
    return -1


# Test de la fonction
tab = [2, 7, 8, 20, 25, 30, 33, 39, 45, 50]
x = 8

resultat = recherche_dichotomique_iterative(tab, x)

if resultat != -1:
    print(f"L'élément {x} est présent à l'indice {resultat}")
else:
    print(f"L'élément {x} n'est pas présent dans le tableau")


# Test avec un élément absent
x = 15
resultat = recherche_dichotomique_iterative(tab, x)

if resultat != -1:
    print(f"L'élément {x} est présent à l'indice {resultat}")
else:
    print(f"L'élément {x} n'est pas présent dans le tableau")

L'élément 8 est présent à l'indice 2
L'élément 15 n'est pas présent dans le tableau

Analyse de complexité

Exemple d'exécution pas à pas

  Exemple n°1 : Recherche de 8 dans [2, 7, 8, 20, 25, 30, 33, 39, 45, 50]

  Exemple n°2 : Recherche de 15 dans le même tableau (non trouvé)

Comparaison : recherche linéaire vs dichotomique

Variantes de la recherche dichotomique

Recherche de la première occurrence (lower bound)

def premier_occurrence(tab, x):
    """Trouve la première occurrence de x dans un tableau trié."""
    debut, fin = 0, len(tab) - 1
    resultat = -1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        
        if tab[milieu] == x:
            resultat = milieu
            fin = milieu - 1  # Chercher encore à gauche
        elif tab[milieu] < x:
            debut = milieu + 1
        else:
            fin = milieu - 1
    
    return resultat

Recherche de la dernière occurrence (upper bound)

def derniere_occurrence(tab, x):
    """Trouve la dernière occurrence de x dans un tableau trié."""
    debut, fin = 0, len(tab) - 1
    resultat = -1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        
        if tab[milieu] == x:
            resultat = milieu
            debut = milieu + 1  # Chercher encore à droite
        elif tab[milieu] < x:
            debut = milieu + 1
        else:
            fin = milieu - 1
    
    return resultat

tab = [1, 2, 3, 3, 3, 4, 5, 5, 6]
x = 3

Première occurrence: 2
Dernière occurrence: 4
Nombre d'occurrences: 3