Quel algorithme a une complexité logarithmique O(log n) ?

L’algorithme de recherche binaire (ou dichotomique) a une complexité temporelle logarithmique O(log n).

Principe de fonctionnement de la recherche binaire :

1. Nécessite un tableau (ou une liste) trié.
2. À chaque étape, compare l’élément recherché avec l’élément au milieu de la plage de recherche actuelle.
3. Si les éléments correspondent, la recherche est terminée.
4. Si l’élément recherché est inférieur au milieu, la recherche continue dans la moitié gauche de la plage.
5. Si l’élément recherché est supérieur au milieu, la recherche continue dans la moitié droite de la plage.
6. La plage de recherche est réduite de moitié à chaque étape.

Exemple d’implémentation en Python :

# Fonction de recherche binaire
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Élément trouvé, retourne l’indice
        elif mid_val < target:
            low = mid + 1  # Ignore la moitié gauche
        else:
            high = mid - 1  # Ignore la moitié droite

    return -1  # Élément non trouvé

# Exemple d’utilisation
# liste_triee = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# valeur_cible = 23
# resultat = binary_search(liste_triee, valeur_cible)
# if resultat != -1:
#     print(f"Élément trouvé à l’indice : {resultat}")
# else:
#     print("Élément non trouvé")

La complexité logarithmique est due au fait que le nombre d’opérations est proportionnel au logarithme de la taille des données d’entrée (n), car à chaque étape, l’espace de recherche est réduit de moitié.