Décoder l’algorithme de recherche binaire avec des exemples

Décodage de l'algorithme de recherche binaire avec des exemples

Introduction

Un algorithme de recherche binaire est une technique de recherche efficace pour localiser un objet spécifique dans un ensemble de données triées. Cet algorithme commence par déterminer la valeur médiane de l’ensemble de données. Il compare la valeur cible avec cette valeur médiane et peut effectuer l’une des trois actions possibles :

• S’ils correspondent, la recherche est réussie et l’indice de la valeur cible est renvoyé.
• Si la valeur cible dépasse l’élément central, la recherche se poursuit avec la moitié de l’ensemble de données.
• Si la valeur cible est plus petite, la moitié gauche est sélectionnée pour une exploration ultérieure.

La recherche binaire est très efficace, avec une complexité temporelle O(log n), où n est le nombre d’éléments dans l’ensemble de données. Cela en fait une méthode préférée pour les gros ensembles de données où une recherche linéaire serait impraticable. Cependant, cela nécessite que l’ensemble de données soit préalablement trié.

Qu’est-ce que la recherche binaire ?

La recherche binaire est un algorithme largement utilisé en informatique et en mathématiques pour localiser un élément spécifique dans un ensemble de données triées. Elle fonctionne en divisant continuellement l’ensemble de données en deux et en comparant la valeur cible avec la valeur médiane jusqu’à ce que la valeur cible soit découverte ou déterminée comme étant absente.

Comment fonctionne la recherche binaire ?

La recherche binaire fonctionne sur la base de trois concepts essentiels : les données triées, la stratégie de diviser pour régner et la réduction de la zone de recherche.

• Comment devenir un ingénieur en NLP ? Plan de carrière 2023
• VoAGI News, 13 septembre Démarrer avec SQL en 5 étapes • Introduction aux bases de données en science des données
• Évaluer l’égalité verte urbaine en utilisant le portail de données ouvertes de Vienne

Données triées

La recherche binaire nécessite que l’ensemble de données soit trié par ordre croissant ou décroissant. Le tri permet une comparaison systématique avec l’élément médian, ce qui permet à l’algorithme de déterminer si la valeur cible se situe à gauche ou à droite.

Diviser pour régner

La recherche binaire suit une stratégie de diviser pour régner. Elle commence par inspecter l’élément médian de l’ensemble de données et le divise en deux moitiés. Cet élément médian est ensuite comparé à la valeur cible.

• Si elles correspondent, la recherche est réussie.
• Si la valeur cible dépasse l’élément médian, la recherche se poursuit avec la moitié droite de l’ensemble de données, en ignorant la moitié gauche.
• Si la valeur cible est plus petite, la recherche se poursuit avec la moitié gauche de l’ensemble de données.

Analyse de la complexité temporelle

• À chaque étape de la recherche binaire, l’espace de recherche est réduit de moitié. Cela signifie que seule la moitié de l’ensemble de données doit être examinée après une étape.
• Avec chaque étape suivante, la zone de recherche est réduite de moitié.
• Cette méthode se poursuit jusqu’à ce que la valeur cible soit découverte ou que l’espace de recherche soit réduit à un ensemble de données vide, ce qui indique l’absence de l’élément cible.

La complexité temporelle de la recherche binaire peut être analysée comme suit :

• Après une étape, l’espace de recherche est N/2, où N est le nombre d’éléments.
• Après deux étapes, il est N/4.
• Après trois étapes, il est N/8, et ainsi de suite.

Implémentation de la recherche binaire

Pseudo-code pour la recherche binaire

BinarySearch(arr, target):
    left = 0
    right = longueur de arr - 1
    
    while left <= right:
        mid = (left + right) / 2
        if arr[mid] == target:
            return mid  // Valeur cible trouvée, renvoie son indice
        else if arr[mid] < target:
            left = mid + 1
        Else:
            right = mid - 1
    
    Return -1  // Valeur cible non trouvée.

Implémentation en Python

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) / 2
        if arr[mid] == target:
            return mid  # Valeur cible trouvée, renvoie son indice
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # Valeur cible non trouvée

Gestion des cas particuliers et des scénarios spécifiques

• Tableau vide : Si le tableau d’entrée est vide, l’algorithme doit renvoyer -1 car il n’y a aucun élément à rechercher.
• Valeur cible non présente dans le tableau : Si la valeur cible n’est pas présente dans le tableau trié, l’algorithme renvoie -1.
• Valeurs en double : La recherche binaire fonctionne bien avec des valeurs en double. Elle renverra l’indice de la première occurrence de la valeur cible si des doublons existent.
• Tableau non trié : La recherche binaire suppose que le tableau d’entrée est trié. Si le tableau n’est pas trié, l’algorithme produit des résultats incorrects. Veillez à trier le tableau en premier.
• Dépassement d’entier : Dans certains langages de programmation (comme C++), l’utilisation de (left + right) / 2 pour calculer l’indice médian peut entraîner un dépassement d’entier pour des valeurs de left et right très grandes. L’utilisation de (left + (right-left)) / 2 peut aider à prévenir cela.
• Erreur de point flottant : Dans les langages qui utilisent l’arithmétique en virgule flottante (comme Python), l’utilisation de (left + right) / 2 peut ne pas être précise pour de grandes valeurs de left et right. Dans de tels cas, l’utilisation de left + (right-left) /2 garantit de meilleurs résultats.

Recherche binaire dans les tableaux

Effectuer une recherche binaire sur un tableau trié est une tâche courante en programmation. Voici les codes d’exemple pour les approches récursive et itérative pour effectuer une recherche binaire sur un tableau trié.

Code d’exemple : Recherche binaire itérative 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  # Target found, return its index

        elif arr[mid] < target:

            left = mid + 1

        else:

            right = mid - 1

    return -1  # Target not found

Code d’exemple : Recherche binaire récursive en Python

def binary_search_recursive(arr,target, left, right):

    if left <= right:

        mid = (left + right) / 2

        if arr[mid] == target:

            return mid  # Target found, return its index

        elif arr[mid] < target:

            return binary_search_recursive(arr, target, mid + 1, right)

        else:

            return binary_search_recursive(arr, target, left, mid - 1) 

    return -1  # Target not found

Explication

Approche itérative

• La recherche binaire itérative commence avec deux pointeurs, gauche et droite.
• Elle entre dans une boucle “while” qui continue tant que “gauche” est inférieure ou égale à “droite”.
• À l’intérieur de la boucle, elle calcule l’indice “milieu” et vérifie si la valeur à “milieu” est égale à la cible.
• Si la cible est trouvée, elle renvoie l’indice.
• Si la cible est inférieure à l’élément à “milieu”, elle met à jour “droite” à “milieu – 1”, rétrécissant ainsi la recherche à la moitié gauche du tableau.
• Si la cible est supérieure, elle met à jour “gauche” à “milieu + 1”, rétrécissant la recherche à la moitié droite.
• La boucle continue jusqu’à ce que la cible soit trouvée ou que “gauche” devienne supérieure à “droite”.

Approche récursive

• La recherche binaire récursive prend “gauche” et “droite” pour définir la plage de recherche actuelle.
• Elle vérifie si “gauche” est inférieure ou égale à “droite”.
• Elle calcule l’indice “milieu” et compare l’élément à “milieu” avec la cible.
• Si la cible est trouvée, elle renvoie l’indice.
• Si la cible est inférieure à l’élément à “milieu”, elle s’appelle récursivement avec une valeur “droite” mise à jour pour la moitié gauche.
• Si la cible est supérieure, elle s’appelle récursivement avec une valeur “gauche” mise à jour pour rechercher la moitié droite.
• La récursion continue jusqu’à ce que la cible soit trouvée ou que l’espace de recherche soit vide.

Recherche binaire dans d’autres structures de données

La recherche binaire est un algorithme de recherche efficace, mais son adaptation dépend de la structure de données.

ARB (Arbres de Recherche Binaire)

Les arbres de recherche binaire sont un type naturel pour la recherche binaire en raison de leur forme. Il s’agit d’un arbre où chaque nœud a deux enfants, et le sous-arbre gauche contient des nœuds avec des valeurs inférieures au nœud actuel, tandis que le sous-arbre droit contient des nœuds avec des valeurs supérieures au nœud actuel. La recherche binaire peut être adaptée aux ARB comme suit :

• Recherche dans un ARB : À partir du nœud racine, comparer la valeur cible avec la valeur du nœud actuel.
• Si elles correspondent, la recherche est réussie.
• Si la valeur cible est inférieure, continuer la recherche dans le sous-arbre gauche.
• Si la valeur cible est supérieure, continuer la recherche dans le sous-arbre droit.

Considérations particulières pour les ARB

• Lors de l’ajout ou de la suppression d’éléments dans un BST, il est important de respecter les propriétés du BST (gauche < courant < droite pour chaque nœud).
• Équilibrer l’arbre est essentiel pour s’assurer que l’arbre reste efficace. Un arbre déséquilibré peut se dégrader en listes chaînées, ce qui entraîne des temps de recherche médiocres.

Utilisations

Les BST sont utilisés dans diverses applications, notamment les dictionnaires, les bases de données et les tables de symboles.

Tableaux et listes

La recherche binaire peut être adaptée aux tableaux et aux listes lorsqu’ils sont triés :

Recherche dans un tableau ou une liste

Une recherche binaire dans un tableau ou une liste est l’exemple de base. Le tableau ou la liste est traité comme une séquence d’éléments, et l’algorithme se poursuit.

Considérations spéciales

• La structure de données doit être triée pour que la recherche binaire fonctionne correctement.
• Assurez-vous de ne pas accéder à des pointeurs qui sont hors limites.

Utilisations

La recherche binaire dans les tableaux ou les listes est utilisée dans diverses applications, notamment la recherche dans des bases de données triées, la recherche d’éléments dans des collections triées et l’optimisation d’algorithmes tels que le tri fusion et le tri rapide.

Gestion des doublons

La gestion des doublons dans la recherche binaire nécessite des stratégies spécifiques pour trouver la première, la dernière ou toutes les occurrences d’une valeur cible dans un ensemble de données trié. Pour trouver la première occurrence, effectuez une recherche binaire standard et renvoyez l’indice lorsque la cible est trouvée. Et pour trouver la dernière occurrence, modifiez la recherche binaire en continuant la recherche dans la moitié droite lorsque la cible est trouvée pour identifier la dernière occurrence à droite. Pour trouver toutes les occurrences, combinez les deux stratégies en trouvant la première ou la dernière occurrence et en prolongeant la recherche dans les deux directions pour collecter tous les pointeurs. Cela garantit une gestion complète des doublons dans la recherche binaire. Voici des exemples de code Python illustrant ces techniques pour trouver la première, la dernière ou toutes les occurrences :

Première occurrence

def trouver_premiere_occurrence(arr, cible):
    gauche, droite = 0, len(arr) - 1
    resultat = -1  # Initialiser le résultat à -1 au cas où la cible n'est pas trouvée
    
    while gauche <= droite:
        milieu = (gauche + droite) // 2  # Utiliser une division entière pour trouver le point milieu
        if arr[milieu] == cible:
            resultat = milieu
            droite = milieu - 1  # Continuer la recherche dans la moitié gauche pour la première occurrence
        elif arr[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    
    return resultat

Dernière occurrence

def trouver_derniere_occurrence(arr, cible):
    gauche, droite = 0, len(arr) - 1
    resultat = -1  # Initialiser le résultat à -1 au cas où la cible n'est pas trouvée
    
    while gauche <= droite:
        milieu = (gauche + droite) // 2  # Utiliser une division entière pour trouver le point milieu
        if arr[milieu] == cible:
            resultat = milieu
            gauche = milieu + 1  # Continuer la recherche dans la moitié droite pour la dernière occurrence
        elif arr[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    
    return resultat

Toutes les occurrences

def trouver_toutes_les_occurrences(arr, cible):
    premiere_occurrence = trouver_premiere_occurrence(arr, cible)
    derniere_occurrence = trouver_derniere_occurrence(arr, cible)
    
    if premiere_occurrence == -1:
        return []  # Cible non trouvée
    else:
        return [i for i in range(premiere_occurrence, derniere_occurrence + 1)]

Variante de recherche binaire

• La recherche ternaire divise l’espace de recherche en trois éléments en évaluant la cible avec les éléments situés à deux points médians également espacés. Cela peut être plus efficace lorsqu’il s’agit de fonctions avec un seul maximum ou minimum, réduisant ainsi le nombre de comparaisons.
• La recherche exponentielle est bénéfique pour les listes non bornées. Elle commence par de petits pas et augmente de manière exponentielle la plage jusqu’à ce qu’une limite soit trouvée, puis applique la recherche binaire dans cette plage.

Optimisation de la recherche binaire

L’optimisation des algorithmes de recherche binaire implique d’améliorer leur croissance et leurs performances globales. Les stratégies incluent la recherche par saut, qui combine les recherches linéaire et binaire en sautant à l’avance par pas fixes, réduisant ainsi les comparaisons pour les tableaux énormes. La recherche par interpolation est une autre méthode qui estime la position de la cible principalement en fonction de la distribution des données, ce qui permet une convergence plus rapide, notamment pour les données uniformément distribuées.

Le benchmarking et le profilage sont essentiels pour optimiser la recherche binaire sur de grands ensembles de données. Les outils de profilage identifient les goulots d’étranglement, ce qui permet d’affiner le code. Les tests de référence comparent le temps d’exécution de l’algorithme dans différentes situations, ce qui guide les optimisations. Ces techniques garantissent que la recherche binaire fonctionne de manière optimale dans des situations diverses, des bases de données au développement de jeux, où l’efficacité et la rapidité sont importantes.

Erreurs courantes et pièges de la recherche binaire

• Ne pas vérifier si les données sont triées : ne pas s’assurer que les données sont triées avant une recherche binaire peut conduire à des résultats incorrects. Vérifiez toujours d’abord si les données sont triées.
• Calcul incorrect du point milieu : utiliser (gauche + droite) / 2 pour le calcul du point milieu peut également provoquer un dépassement d’entier ou des problèmes de précision dans certains langages. Utilisez (gauche + (droite-gauche)) / 2 pour éviter ces problèmes.
• Boucles infinies : ne pas remplacer correctement les pointeurs (gauche et droite) dans la boucle peut entraîner des boucles infinies. Assurez-vous de les mettre à jour régulièrement.

Applications du monde réel

La recherche binaire est omniprésente en informatique et au-delà. Elle est utilisée dans les moteurs de recherche comme Google et Yahoo pour une récupération instantanée des pages Web, dans les bases de données pour une interrogation efficace et dans les systèmes de fichiers pour une récupération rapide des données. Les compagnies aériennes l’utilisent pour optimiser la réservation de sièges, et elle joue un rôle essentiel dans les algorithmes de compression de données.

Bibliothèques et modules de recherche binaire

De nombreux langages de programmation populaires proposent des bibliothèques ou des modules intégrés qui offrent des implémentations efficaces de recherche binaire. En Python, le module “bisect” fournit des fonctions telles que “bisect_left”, “bisect_right” et “bisect” pour rechercher et insérer des éléments dans des listes triées.

Ces fonctions de bibliothèque sont optimisées pour les performances et peuvent faire gagner du temps et des efforts dans la création d’algorithmes de recherche binaire personnalisés.

Conclusion

La recherche binaire est un algorithme flexible et efficace pour trouver rapidement des éléments dans des structures de données triées. Elle offre une base pour optimiser des applications diverses, des moteurs de recherche comme Google et Yahoo au développement de jeux. En comprenant ses principes et en tenant compte des variations et des bibliothèques, les développeurs peuvent utiliser la puissance de la recherche binaire pour résoudre avec succès et rapidement des problèmes complexes.

Si vous souhaitez en savoir plus sur de tels algorithmes, nos cours et nos blogs gratuits peuvent beaucoup vous aider.

Questions fréquemment posées

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!