Recherche binaire en Python : guide complet pour une recherche efficace

De manière générale, un algorithme est une suite d'instructions précise qu'un ordinateur exécute pour accomplir une tâche ou résoudre un problème. Consultez notre article de blog What is an Algorithm pour découvrir les différents types d'algorithmes en machine learning.

Aperçu du concept

La recherche binaire est un algorithme puissant conçu pour retrouver efficacement une valeur dans un ensemble de données trié. Son idée clé est simple : au lieu de vérifier chaque élément un à un, comme dans une recherche linéaire, la recherche binaire réduit de moitié l'intervalle de recherche à chaque étape, ce qui accélère fortement le processus.

Voici son fonctionnement :

1. Commencez par comparer la valeur cible avec l'élément du milieu de l'ensemble. L'indice du milieu se calcule avec la formule : middle = (low + high) / 2, où low est l'indice du premier élément de la zone de recherche actuelle et high l'indice du dernier.
2. Comparez la valeur du milieu avec la cible. Si la valeur cible est égale à l'élément du milieu, vous avez trouvé l'indice et la recherche s'arrête. Si la cible est plus petite, poursuivez dans la moitié gauche de l'ensemble. Si elle est plus grande, poursuivez dans la moitié droite.
3. Répétez les étapes 1 et 2. L'intervalle de recherche est continuellement divisé par deux à chaque étape. Continuez jusqu'à trouver la cible ou jusqu'à ce que l'intervalle devienne vide.

Le processus de recherche binaire. Image de l'auteure

Ci-dessus, un exemple simplifié qui illustre le principe de la recherche binaire.

Cette division par deux rend la recherche binaire particulièrement efficace. Il est toutefois indispensable que l'ensemble de données soit trié pour qu'elle fonctionne correctement. Si ce n'est pas le cas, l'algorithme ne donnera pas les résultats escomptés. 

Consultez Data Structures: A Comprehensive Guide With Python Examples pour en savoir plus sur les différentes structures de données dans lesquelles vous pourriez effectuer des recherches.

Points clés à retenir

Les points suivants résument les principes de base de la recherche binaire.

Efficacité

La recherche binaire est nettement plus rapide que la recherche linéaire, surtout sur de grands volumes de données. Alors que la recherche linéaire a une complexité temporelle O(n) (elle peut devoir vérifier tous les éléments dans le pire des cas), la recherche binaire est plus efficace. Sa complexité est O(log n) : l'espace de recherche est réduit de moitié à chaque étape, ce qui diminue fortement le nombre de comparaisons nécessaires.

Pour une explication détaillée de l'évaluation des algorithmes, reportez-vous à notre Big O Notation and Time Complexity Guide: Intuition and Math. Vous pouvez aussi consulter notre tutoriel Analyzing Complexity of Code through Python.

Prérequis

Pour fonctionner, la recherche binaire exige un ensemble trié par ordre croissant ou décroissant. L'algorithme s'appuie sur cet ordre pour déterminer quelle moitié explorer ensuite. Si les données ne sont pas triées, la recherche binaire ne pourra pas localiser correctement la valeur cible.

Flexibilité

La recherche binaire peut s'implémenter de façon itérative ou récursive. La méthode itérative utilise des boucles pour réduire l'intervalle de recherche. La méthode récursive fait appel à la fonction elle-même avec un intervalle réduit. Cette flexibilité la rend adaptée à de nombreux cas d'usage.

Applications concrètes

La recherche binaire est un outil puissant. Sa capacité à restreindre rapidement l'espace de recherche la rend précieuse, en particulier sur de grands jeux de données où la performance est critique. Voyons quelques applications spécifiques et comparons-la à d'autres algorithmes.

Bases de données

Dans les bases de données, la recherche binaire sert souvent à localiser rapidement des enregistrements dans des champs triés, par exemple pour trouver un utilisateur spécifique dans une base triée par ID. Imaginez une base contenant des millions d'entrées : une recherche linéaire devrait les parcourir une à une, ce qui prendrait beaucoup de temps. À l'inverse, la recherche binaire réduit systématiquement de moitié l'espace de recherche et localise rapidement l'enregistrement voulu, avec bien moins de comparaisons.

Data science

Parcourir de grands ensembles triés est une tâche fréquente en data science. Par exemple, en analyse de séries temporelles, la recherche binaire permet de retrouver des horodatages précis dans une séquence triée d'événements. En machine learning, elle peut aider à optimiser des hyperparamètres en recherchant la meilleure valeur dans un intervalle.

Graphismes et rendu

En infographie, la recherche binaire intervient dans des algorithmes où précision et vitesse sont cruciales. Par exemple en lancer de rayons (ray tracing), une technique de rendu qui simule l'interaction de la lumière avec les objets, elle peut servir à trouver rapidement les points d'intersection entre rayons et surfaces.

Briques pour des algorithmes complexes

La recherche binaire n'est pas seulement utile en soi ; elle sert aussi de fondation à des algorithmes et structures de données plus sophistiqués. Par exemple, les arbres de recherche, comme les arbres binaires de recherche (BST) et les arbres équilibrés (tels que les arbres AVL), reposent sur ses principes. Ces structures offrent des opérations de recherche, d'insertion et de suppression efficaces, idéales lorsque les données évoluent et sont consultées fréquemment. Pour en savoir plus, voir AVL Tree: Complete Guide With Python Implementation.

Recherche binaire vs autres algorithmes de recherche

Comparons la recherche binaire à deux autres algorithmes courants : la recherche linéaire et la recherche par hachage.

Recherche linéaire

La recherche linéaire parcourt chaque élément d'un ensemble séquentiellement. Elle est bien moins efficace que la recherche binaire, avec une complexité O(n). En revanche, elle ne nécessite pas que les données soient triées, ce qui peut être utile selon les contextes.

Table de hachage

La recherche via hachage est très efficace pour retrouver rapidement des valeurs associées à des clés uniques. Une fonction de hachage calcule l'indice où la valeur correspondante est stockée dans une table de hachage, permettant une récupération quasi instantanée, souvent en O(1). Toutefois, même si elle est très rapide pour trouver des éléments précis, elle requiert de la mémoire supplémentaire pour la table et n'est pas adaptée aux recherches sur un intervalle de valeurs—un cas où la recherche binaire est plus pertinente.

Implémenter la recherche binaire en Python

Voyons plusieurs façons d'implémenter une recherche binaire simple en Python. D'abord, définissons un petit ensemble de données trié et une valeur cible à rechercher :

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 56

Méthode itérative

La méthode itérative est sans doute la plus directe. On utilise une boucle while pour diviser l'intervalle de recherche en deux jusqu'à trouver la cible. Cette approche est souvent privilégiée pour sa clarté et son efficacité.

Voici une implémentation itérative de la recherche binaire :

def binary_search_iterative(arr, target):
    # Définir les bornes de recherche
    left, right = 0, len(arr) - 1  
    while left <= right:
        # Calculer l'index du milieu
        mid = left + (right - left) // 2  
        # Si l'élément du milieu est la cible, renvoyer son index
        if arr[mid] == target:
            return mid  
        # Si la cible est plus grande, restreindre la recherche à la moitié droite
        elif arr[mid] < target: 
            left = mid + 1  
        # Si la cible est plus petite, restreindre la recherche à la moitié gauche
        else: 
            right = mid - 1  
    # Renvoyer -1 si la cible est absente
    return -1 
    
# Exécuter la fonction itérative
result = binary_search_iterative(arr, target)
if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")

Analyse du code :

• On initialise les bornes « left » et « right » de l'espace de recherche. Au départ, left vaut 0 (début du tableau) et right vaut len(arr) - 1 (fin du tableau).

• À chaque itération, on calcule l'index du milieu, qui représente le centre de l'intervalle courant, avec la formule mid = left + (right - left) /2.

• On compare ensuite l'élément à mid avec la target :

• S'ils coïncident, la cible est trouvée et la fonction renvoie mid.

• Si l'élément à mid est inférieur à la cible, celle-ci se trouve dans la moitié droite ; on met donc left à mid + 1.

• Si l'élément à mid est supérieur à la cible, celle-ci se trouve dans la moitié gauche ; on met donc right à mid - 1.

• La boucle continue jusqu'à ce que la cible soit trouvée ou que left dépasse right, signe que la cible n'est pas présente.

Méthode récursive

La méthode récursive offre une autre implémentation : au lieu d'une boucle, la fonction s'appelle elle-même en ajustant les bornes jusqu'à trouver la cible ou conclure à son absence.

Voici une implémentation récursive :

def binary_search_recursive(arr, target, left, right):
    # Si les bornes se croisent, la cible n'est pas dans le tableau
    if left > right:  
        return -1
    # Calculer l'index du milieu
    mid = left + (right - left) // 2 
    # Si la valeur du milieu est la cible, renvoyer l'index
    if arr[mid] == target: 
        return mid  
    # Si la cible est plus grande, chercher dans la moitié droite
    elif arr[mid] < target: 
        return binary_search_recursive(arr, target, mid + 1, right)  
    # Si la cible est plus petite, chercher dans la moitié gauche
    else: 
        return binary_search_recursive(arr, target, left, mid - 1)  

# Exécuter la fonction récursive
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")

Analyse du code :

• La fonction récursive démarre avec les mêmes bornes left et right que la version itérative.

• Elle vérifie d'abord si left dépasse right. Si oui, elle renvoie -1, indiquant l'absence de la cible.

• Sinon, elle calcule l'index mid et compare la cible à l'élément en mid.

• Si la cible est égale à l'élément en mid, la fonction renvoie mid.

• Si la cible est supérieure à mid, la fonction s'appelle récursivement avec des bornes mises à jour pour chercher à droite.

• Si la cible est inférieure à mid, elle cherche à gauche.

• La récursion continue jusqu'à trouver la cible ou épuiser l'espace de recherche.

Pour en savoir plus sur les fonctions récursives, consultez Understanding Recursive Functions in Python.

Utiliser le module intégré bisect de Python

La bibliothèque standard de Python inclut le module bisect, qui fournit des fonctions de recherche binaire prêtes à l'emploi. Ce module est très performant et fait souvent gagner du temps par rapport à une implémentation maison.

Voici comment utiliser bisect pour retrouver la cible dans notre tableau :

# Importer le module bisect
import bisect 

# Appeler la fonction en fournissant le tableau et la valeur cible
index = bisect.bisect_left(arr, target) 

# Afficher les résultats
if index < len(arr) and arr[index] == target:
    print(f"Bisect: Target found at index {index}")
else:
    print("Bisect: Target not found")

Analyse du code :

• La fonction bisect_left renvoie l'indice où insérer la cible pour conserver l'ordre du tableau. Si la cible se trouve à cet indice, c'est qu'elle est présente.

• Cette méthode est particulièrement utile avec des tableaux triés et permet aussi d'insérer des éléments tout en maintenant l'ordre.

• Le module bisect propose également bisect_right et insort pour trouver des points d'insertion ou insérer directement des éléments.

Complexités en temps et en espace

Pour discuter de l'efficacité d'un algorithme, on utilise souvent la notation Big O, notée O(x), pour décrire comment le temps d'exécution ou l'espace mémoire évoluent avec la taille de l'entrée. Pour la recherche binaire, la complexité en temps est généralement O(log n). Cela signifie que, lorsque l'ensemble de données grandit, le nombre d'opérations nécessaires augmente de manière logarithmique, ce qui reste efficace même à grande échelle.

La méthode itérative a une complexité O(log n) car l'intervalle de recherche est divisé par deux à chaque itération. Sa complexité en espace est O(1), puisqu'elle n'utilise qu'une quantité constante de mémoire pour suivre les bornes et l'élément du milieu.

La méthode récursive a aussi une complexité en temps O(log n) pour la même raison. En revanche, sa complexité en espace est O(log n) en raison de la pile d'appels nécessaire à chaque appel récursif. La profondeur de récursion est proportionnelle au nombre de divisions par deux, donc logarithmique par rapport à la taille des données.

Les deux méthodes sont efficaces en temps, mais l'approche itérative est plus économe en mémoire. C'est pourquoi le module bisect utilise une approche itérative en interne. Personnellement, je la privilégie aussi pour cette raison. Cela dit, la version récursive peut paraître plus intuitive pour certaines personnes et parfois nécessiter moins de lignes de code.

Pièges courants et comment les éviter

Avec la recherche binaire, quelques écueils classiques sont à surveiller. Ils peuvent nuire à la justesse et à la performance de l'algorithme, d'où l'importance de les connaître.

D'abord, la recherche binaire suppose des données triées. Si ce n'est pas le cas, elle ne fonctionnera pas correctement : elle peut renvoyer de mauvais résultats ou échouer. Il faut donc trier l'ensemble avant de l'appliquer. Si le tri n'est pas envisageable, la recherche binaire n'est pas l'outil approprié.

Un problème fréquent est l'erreur d'unité (off-by-one). De légères imprécisions dans les calculs d'indices peuvent conduire à des boucles infinies ou à manquer la valeur cible. Cela arrive si le calcul du milieu ou l'ajustement des bornes ne sont pas traités avec précision. Pour l'éviter, assurez-vous que le calcul de l'index central est correct et que les bornes sont mises à jour proprement après chaque comparaison. Rappelez-vous que les indices en Python commencent à 0, pas à 1.

Autre point d'attention si vous utilisez la version récursive : la profondeur de récursion. Python limite le nombre d'appels récursifs pour éviter une consommation mémoire excessive. Sur de très grands ensembles, une récursion trop profonde peut dépasser cette limite et provoquer un dépassement de pile. Pour y remédier, préférez l'approche itérative, insensible à cette contrainte. Si la récursion est souhaitée ou nécessaire, vous pouvez éventuellement augmenter la limite avec sys.setrecursionlimit(), mais faites-le avec prudence pour éviter d'autres problèmes potentiels.

Conclusion

La recherche binaire est un algorithme puissant et efficace qui devrait faire partie de la boîte à outils de tout développeur Python. Qu'elle soit implémentée de manière itérative ou récursive, elle offre un net avantage sur la recherche linéaire, surtout sur de grands volumes de données. Pour aller plus loin, découvrez le parcours de compétences Python Programming de DataCamp ou le cours interactif Software Engineering Principles in Python.