Algorithmes de recherche O(log n) vs O(n) en Python

Comparaison des algorithmes de recherche : O(n) vs. O(log n) pour développeurs

Sur des tableaux contenant des millions d’éléments, la recherche linéaire peut nécessiter jusqu’à 10 millions d’opérations — tandis que la recherche binaire s’achève en seulement 24 comparaisons. Nous analysons quatre algorithmes de recherche en Python, en détaillant leur complexité temporelle, leurs compromis pratiques et des recommandations concrètes pour choisir le bon algorithme selon le contexte. Inclut des implémentations résistantes au dépassement d’entier, les fonctions lower_bound/upper_bound, et des exemples prêts à être utilisés sur LeetCode.

Le problème de recherche : étant donné une collection arr, trouver l’indice de target, ou renvoyer -1. La collection peut être triée ou non, statique ou dynamique. Des cas d’usage réels incluent la recherche de références produits (SKU) dans le e-commerce (des millions de références) ou la validation d’identifiants de transaction dans le secteur fintech.

Recherche linéaire sur données non triées

Fonctionne avec toute collection. Parcourt les éléments séquentiellement.

Implémentation :

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Complexité :

• Temps : O(n) dans le pire cas et en moyenne, O(1) dans le meilleur cas.
• Espace : O(1).

Recherche binaire et ses variantes

Nécessite un tableau trié. Réduit itérativement l’intervalle de recherche de moitié à chaque étape.

Implémentation itérative : Utilisez mid = left + (right - left) // 2 pour éviter les dépassements d’entier (critique en C++/Java ; sécurisé et idiomatique aussi en Python).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Exemple
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5))  # 3
print(lower_bound(sorted_arr, 3))     # 1
print(upper_bound(sorted_arr, 3))     # 3

Complexité : Temps O(log n), espace O(1).

lower_bound renvoie la position d’insertion la plus à gauche pour target ; upper_bound renvoie celle la plus à droite. Indispensables pour gérer les doublons et résoudre des problèmes comme « Trouver la première et dernière occurrence d’un élément dans un tableau trié » sur LeetCode.

Recherche exponentielle pour les flux ou données de taille inconnue

Idéale pour des tableaux triés dont la longueur est inconnue — ou lorsque target est probablement proche du début. Elle identifie d’abord une plage bornée par croissance exponentielle, puis applique une recherche binaire.

def exponential_search(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0

    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2

    left = bound // 2
    right = min(bound, len(arr) - 1)
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Exemple
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456))  # 123456

Complexité : O(log i), où i est l’indice de la cible ; dans le pire cas O(log n) ; espace O(1).

Recherche basée sur hachage pour collections dynamiques

Recherche moyenne en O(1) grâce aux tables de hachage (set/dict en Python).

def hash_search_set(arr, target):
    s = set(arr)
    return target in s

def hash_search_dict(pairs, key):
    d = dict(pairs)
    return d.get(key)

# Exemple
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30))  # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b"))  # 2

Complexité : O(1) en moyenne, O(n) dans le pire cas (collisions de hachage), espace O(n).

Recommandations pour choisir l’algorithme

• Tableau non trié : Recherche linéaire si N < 100 ou si les recherches sont rares.
• Données triées et statiques : Recherche binaire.
• Données dynamiques avec insertions fréquentes : Table de hachage (l’ordre n’a pas d’importance).
• Flux ou données de taille inconnue : Recherche exponentielle.

| Algorithme | Temps moyen | Temps au pire | Espace | Prérequis |

|------------|-------------|----------------|--------|-----------|

| Linéaire | O(n) | O(n) | O(1) | Aucun |

| Binaire | O(log n) | O(log n) | O(1) | Trié |

| Exponentielle | O(log i) | O(log n) | O(1) | Trié |

| Hachage | O(1) | O(n) | O(n) | Clés hachables |

Points clés à retenir

• Pour 10 millions d’éléments : la recherche binaire effectue environ 24 comparaisons contre 10 millions pour la recherche linéaire.
• Privilégiez toujours un calcul sécurisé de mid dans la recherche binaire — même en Python, c’est une bonne pratique robuste.
• Les tables de hachage échangent de la mémoire (O(n)) contre des recherches ultra-rapides en moyenne (O(1)).
• lower_bound et upper_bound sont indispensables pour gérer les doublons et implémenter une logique d’insertion fiable.
• La recherche exponentielle excelle lorsque les cibles se concentrent près du début de très grands tableaux triés.

— Editorial Team