Algorithme de recherche binaire - Binary search algorithm

Algorithme de recherche binaire
Recherche binaire Depiction.svg
Visualisation de l'algorithme de recherche binaire où 7 est la valeur cible
Classer Algorithme de recherche
Structure de données Déployer
Performances dans le pire des cas O (log n )
Le meilleur cas la performance O (1)
Performances moyennes O (log n )
Complexité spatiale dans le pire des cas O (1)

Dans l'informatique , la recherche binaire , également connu sous le nom recherche demi-intervalle , recherche logarithmique , ou côtelette binaire , est un algorithme de recherche qui trouve la position d'une valeur cible dans un tableau trié . La recherche binaire compare la valeur cible à l'élément central du tableau. S'ils ne sont pas égaux, la moitié dans laquelle la cible ne peut pas se trouver est éliminée et la recherche se poursuit sur la moitié restante, en prenant à nouveau l'élément du milieu à comparer à la valeur cible, et en répétant cette opération jusqu'à ce que la valeur cible soit trouvée. Si la recherche se termine avec la moitié restante vide, la cible n'est pas dans le tableau.

La recherche binaire s'exécute en temps logarithmique dans le pire des cas , en faisant des comparaisons, où est le nombre d'éléments dans le tableau. La recherche binaire est plus rapide que la recherche linéaire, sauf pour les petits tableaux. Cependant, le tableau doit d'abord être trié pour pouvoir appliquer la recherche binaire. Il existe des structures de données spécialisées conçues pour une recherche rapide, telles que des tables de hachage , qui peuvent être recherchées plus efficacement que la recherche binaire. Cependant, la recherche binaire peut être utilisée pour résoudre un plus large éventail de problèmes, tels que la recherche de l'élément le plus petit ou le plus grand suivant dans le tableau par rapport à la cible même s'il est absent du tableau.

Il existe de nombreuses variantes de la recherche binaire. En particulier, la cascade fractionnaire accélère les recherches binaires pour la même valeur dans plusieurs tableaux. La cascade fractionnaire résout efficacement un certain nombre de problèmes de recherche en géométrie computationnelle et dans de nombreux autres domaines. La recherche exponentielle étend la recherche binaire aux listes illimitées. L' arbre de recherche binaire et les structures de données de l' arbre B sont basés sur la recherche binaire.

Algorithme

La recherche binaire fonctionne sur des tableaux triés. La recherche binaire commence par comparer un élément au milieu du tableau avec la valeur cible. Si la valeur cible correspond à l'élément, sa position dans le tableau est renvoyée. Si la valeur cible est inférieure à l'élément, la recherche se poursuit dans la moitié inférieure du tableau. Si la valeur cible est supérieure à l'élément, la recherche se poursuit dans la moitié supérieure du tableau. En faisant cela, l'algorithme élimine la moitié dans laquelle la valeur cible ne peut pas se situer à chaque itération.

Procédure

Étant donné un tableau d' éléments avec des valeurs ou des enregistrements triés de telle sorte que , et une valeur cible , le sous-programme suivant utilise une recherche binaire pour trouver l'index de dans .

  1. Réglez sur et sur .
  2. Si , la recherche se termine comme un échec.
  3. Définissez (la position de l'élément du milieu) sur le plancher de , qui est le plus grand entier inférieur ou égal à .
  4. Si , réglez sur et passez à l'étape 2.
  5. Si , réglez sur et passez à l'étape 2.
  6. Maintenant , la recherche est terminée ; retour .

Cette procédure itérative garde une trace des limites de la recherche avec les deux variables et . La procédure peut être exprimée en pseudo-code comme suit, où les noms et types de variables restent les mêmes que ci-dessus, est la fonction étage, et fait référence à une valeur spécifique qui traduit l'échec de la recherche. floorunsuccessful

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

Alternativement, l'algorithme peut prendre le plafond de . Cela peut modifier le résultat si la valeur cible apparaît plusieurs fois dans le tableau.

Procédure alternative

Dans la procédure ci-dessus, l'algorithme vérifie si l'élément du milieu ( ) est égal à la cible ( ) à chaque itération. Certaines implémentations omettent cette vérification à chaque itération. L'algorithme effectuerait cette vérification uniquement lorsqu'un élément est laissé (quand ). Cela se traduit par une boucle de comparaison plus rapide, car une comparaison est éliminée par itération. Cependant, cela nécessite une itération de plus en moyenne.

Hermann Bottenbruch a publié la première implémentation pour omettre ce contrôle en 1962.

  1. Réglez sur et sur .
  2. Tandis que ,
    1. Définir (la position de l'élément du milieu) au plafond de , qui est le plus petit entier supérieur ou égal à .
    2. Si , définissez sur .
    3. Sinon, ; réglé sur .
  3. Maintenant , la recherche est terminée. Si , revenez . Sinon, la recherche se termine comme un échec.

ceilest la fonction plafond, le pseudocode pour cette version est :

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

Éléments en double

La procédure peut renvoyer n'importe quel index dont l'élément est égal à la valeur cible, même s'il y a des éléments en double dans le tableau. Par exemple, si le tableau à rechercher était et que la cible était , il serait alors correct que l'algorithme renvoie le 4e (index 3) ou le 5e (index 4) élément. La procédure normale renverrait le 4e élément (index 3) dans ce cas. Il ne renvoie pas toujours le premier doublon (considérez qui renvoie toujours le 4ème élément). Cependant, il est parfois nécessaire de trouver l'élément le plus à gauche ou le plus à droite pour une valeur cible qui est dupliquée dans le tableau. Dans l'exemple ci-dessus, le 4ème élément est l'élément le plus à gauche de la valeur 4, tandis que le 5ème élément est l'élément le plus à droite de la valeur 4. La procédure alternative ci-dessus renverra toujours l'index de l'élément le plus à droite si un tel élément existe.

Procédure pour trouver l'élément le plus à gauche

Pour trouver l'élément le plus à gauche, la procédure suivante peut être utilisée :

  1. Réglez sur et sur .
  2. Tandis que ,
    1. Définissez (la position de l'élément du milieu) sur le plancher de , qui est le plus grand entier inférieur ou égal à .
    2. Si , définissez sur .
    3. Sinon, ; réglé sur .
  3. Retour .

Si et , alors est l'élément le plus à gauche qui est égal à . Même si n'est pas dans le tableau, est le rang de dans le tableau, ou le nombre d'éléments dans le tableau qui sont inférieurs à .

floorest la fonction floor, le pseudocode pour cette version est :

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Procédure pour trouver l'élément le plus à droite

Pour trouver l'élément le plus à droite, la procédure suivante peut être utilisée :

  1. Réglez sur et sur .
  2. Tandis que ,
    1. Définissez (la position de l'élément du milieu) sur le plancher de , qui est le plus grand entier inférieur ou égal à .
    2. Si , définissez sur .
    3. Sinon, ; réglé sur .
  3. Retour .

Si et , alors est l'élément le plus à droite qui est égal à . Même si n'est pas dans le tableau, est le nombre d'éléments dans le tableau qui sont supérieurs à .

floorest la fonction floor, le pseudocode pour cette version est :

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Correspondances approximatives

La recherche binaire peut être adaptée pour calculer des correspondances approximatives. Dans l'exemple ci-dessus, le rang, le prédécesseur, le successeur et le voisin le plus proche sont affichés pour la valeur cible , qui n'est pas dans le tableau.

La procédure ci-dessus n'effectue que des correspondances exactes , en trouvant la position d'une valeur cible. Cependant, il est trivial d'étendre la recherche binaire pour effectuer des correspondances approximatives car la recherche binaire fonctionne sur des tableaux triés. Par exemple, la recherche binaire peut être utilisée pour calculer, pour une valeur donnée, son rang (le nombre d'éléments plus petits), son prédécesseur (élément le plus petit suivant), son successeur (élément le plus grand suivant) et son voisin le plus proche . Les requêtes de plage recherchant le nombre d'éléments entre deux valeurs peuvent être effectuées avec deux requêtes de rang.

  • Les requêtes de classement peuvent être effectuées avec la procédure de recherche de l'élément le plus à gauche . Le nombre d'éléments inférieur à la valeur cible est renvoyé par la procédure.
  • Les requêtes de prédécesseurs peuvent être effectuées avec des requêtes de classement. Si le rang de la valeur cible est , son prédécesseur est  .
  • Pour les requêtes de successeur, la procédure de recherche de l'élément le plus à droite peut être utilisée. Si le résultat de l'exécution de la procédure pour la valeur cible est , le successeur de la valeur cible est  .
  • Le voisin le plus proche de la valeur cible est son prédécesseur ou son successeur, selon le plus proche.
  • Les requêtes de plage sont également simples. Une fois les rangs des deux valeurs connus, le nombre d'éléments supérieur ou égal à la première valeur et inférieur à la seconde est la différence des deux rangs. Ce nombre peut être augmenté ou diminué de un selon que les points de terminaison de la plage doivent être considérés comme faisant partie de la plage et si le tableau contient des entrées correspondant à ces points de terminaison.

Performance

Un arbre représentant la recherche binaire. Le tableau recherché ici est , et la valeur cible est .
Le pire des cas est atteint lorsque la recherche atteint le niveau le plus profond de l'arbre, tandis que le meilleur des cas est atteint lorsque la valeur cible est l'élément du milieu.

En termes de nombre de comparaisons, les performances de la recherche binaire peuvent être analysées en visualisant le déroulement de la procédure sur un arbre binaire. Le nœud racine de l'arbre est l'élément central du tableau. L'élément du milieu de la moitié inférieure est le nœud enfant gauche de la racine, et l'élément du milieu de la moitié supérieure est le nœud enfant droit de la racine. Le reste de l'arbre est construit de la même manière. En partant du nœud racine, les sous-arbres gauche ou droit sont parcourus selon que la valeur cible est inférieure ou supérieure au nœud considéré.

Dans le pire des cas, la recherche binaire effectue des itérations de la boucle de comparaison, où la notation désigne la fonction plancher qui donne le plus grand entier inférieur ou égal à l'argument, et est le logarithme binaire . En effet, le pire des cas est atteint lorsque la recherche atteint le niveau le plus profond de l'arbre, et il y a toujours des niveaux dans l'arbre pour toute recherche binaire.

Le pire des cas peut également être atteint lorsque l'élément cible n'est pas dans le tableau. Si est un de moins qu'une puissance de deux, alors c'est toujours le cas. Sinon, la recherche peut effectuer des itérations si la recherche atteint le niveau le plus profond de l'arbre. Cependant, il peut effectuer des itérations, ce qui est un de moins que le pire des cas, si la recherche se termine au deuxième niveau le plus profond de l'arbre.

En moyenne, en supposant que chaque élément est également susceptible d'être recherché, la recherche binaire effectue des itérations lorsque l'élément cible est dans le tableau. Ceci est approximativement égal aux itérations. Lorsque l'élément cible n'est pas dans le tableau, la recherche binaire effectue des itérations en moyenne, en supposant que la plage entre et en dehors des éléments est également susceptible d'être recherchée.

Dans le meilleur des cas, où la valeur cible est l'élément central du tableau, sa position est renvoyée après une itération.

En termes d'itérations, aucun algorithme de recherche qui fonctionne uniquement en comparant des éléments ne peut présenter de meilleures performances moyennes et pires que la recherche binaire. L'arbre de comparaison représentant la recherche binaire a le moins de niveaux possible car chaque niveau au-dessus du niveau le plus bas de l'arbre est complètement rempli. Sinon, l'algorithme de recherche peut éliminer quelques éléments dans une itération, augmentant le nombre d'itérations requises dans le cas moyen et le pire. C'est le cas pour d'autres algorithmes de recherche basés sur des comparaisons, car même s'ils peuvent fonctionner plus rapidement sur certaines valeurs cibles, les performances moyennes sur tous les éléments sont pires que la recherche binaire. En divisant le tableau en deux, la recherche binaire garantit que la taille des deux sous-tableaux est aussi similaire que possible.

Complexité spatiale

La recherche binaire nécessite trois pointeurs vers des éléments, qui peuvent être des indices de tableau ou des pointeurs vers des emplacements mémoire, quelle que soit la taille du tableau. Par conséquent, la complexité spatiale de la recherche binaire réside dans le modèle de calcul de la RAM .

Dérivation du cas moyen

Le nombre moyen d'itérations effectuées par recherche binaire dépend de la probabilité que chaque élément soit recherché. Le cas moyen est différent pour les recherches réussies et les recherches infructueuses. On supposera que chaque élément est également susceptible d'être recherché pour des recherches réussies. Pour les recherches infructueuses, on supposera que les intervalles entre et à l'extérieur des éléments sont également susceptibles d'être recherchés. Le cas moyen de recherches réussies est le nombre d'itérations nécessaires pour rechercher chaque élément exactement une fois, divisé par , le nombre d'éléments. Le cas moyen pour les recherches infructueuses est le nombre d'itérations nécessaires pour rechercher un élément dans chaque intervalle exactement une fois, divisé par les intervalles.

Recherches réussies

Dans la représentation de l'arbre binaire, une recherche réussie peut être représentée par un chemin de la racine au nœud cible, appelé chemin interne . La longueur d'un chemin est le nombre d'arêtes (connexions entre les nœuds) que le chemin traverse. Le nombre d'itérations effectuées par une recherche, étant donné que le chemin correspondant a une longueur , compte l'itération initiale. La longueur du chemin interne est la somme des longueurs de tous les chemins internes uniques. Puisqu'il n'y a qu'un seul chemin de la racine à un seul nœud, chaque chemin interne représente une recherche d'un élément spécifique. S'il y a des éléments, qui est un entier positif, et que la longueur du chemin interne est , alors le nombre moyen d'itérations pour une recherche réussie , avec une itération ajoutée pour compter l'itération initiale.

Étant donné que la recherche binaire est l'algorithme optimal pour la recherche avec des comparaisons, ce problème se réduit au calcul de la longueur de chemin interne minimale de tous les arbres binaires avec des nœuds, qui est égale à :

Par exemple, dans un tableau à 7 éléments, la racine nécessite une itération, les deux éléments sous la racine nécessitent deux itérations et les quatre éléments ci-dessous nécessitent trois itérations. Dans ce cas, la longueur du chemin interne est :

Le nombre moyen d'itérations serait basé sur l'équation du cas moyen. La somme pour peut être simplifiée comme suit :

Substituer l'équation pour dans l'équation pour :

Pour integer , cela équivaut à l'équation du cas moyen sur une recherche réussie spécifiée ci-dessus.

Recherches infructueuses

Les recherches infructueuses peuvent être représentées en augmentant l'arbre avec des nœuds externes , ce qui forme un arbre binaire étendu . Si un nœud interne, ou un nœud présent dans l'arbre, a moins de deux nœuds enfants, alors des nœuds enfants supplémentaires, appelés nœuds externes, sont ajoutés de sorte que chaque nœud interne ait deux enfants. Ce faisant, une recherche infructueuse peut être représentée comme un chemin vers un nœud externe, dont le parent est l'élément unique qui reste au cours de la dernière itération. Un chemin externe est un chemin de la racine à un nœud externe. La longueur du chemin externe est la somme des longueurs de tous les chemins externes uniques. S'il y a des éléments, qui est un entier positif, et que la longueur du chemin externe est , alors le nombre moyen d'itérations pour une recherche infructueuse , avec une itération ajoutée pour compter l'itération initiale. La longueur du chemin externe est divisée par au lieu de parce qu'il existe des chemins externes, représentant les intervalles entre et en dehors des éléments du tableau.

Ce problème peut également être réduit à la détermination de la longueur de chemin externe minimale de tous les arbres binaires avec des nœuds. Pour tous les arbres binaires, la longueur du chemin externe est égale à la longueur du chemin interne plus . Substituer l'équation pour :

En remplaçant l'équation pour dans l'équation pour , le cas moyen des recherches infructueuses peut être déterminé :

Exécution de la procédure alternative

Chaque itération de la procédure de recherche binaire définie ci-dessus effectue une ou deux comparaisons, en vérifiant si l'élément du milieu est égal à la cible à chaque itération. En supposant que chaque élément est également susceptible d'être recherché, chaque itération effectue 1,5 comparaison en moyenne. Une variante de l'algorithme vérifie si l'élément du milieu est égal à la cible à la fin de la recherche. En moyenne, cela élimine la moitié d'une comparaison à chaque itération. Cela réduit légèrement le temps pris par itération sur la plupart des ordinateurs. Cependant, il garantit que la recherche prend le nombre maximum d'itérations, ajoutant en moyenne une itération à la recherche. Étant donné que la boucle de comparaison n'est effectuée que des fois dans le pire des cas, la légère augmentation de l'efficacité par itération ne compense pas l'itération supplémentaire pour tous mais est très grande .

Temps d'exécution et utilisation du cache

Lors de l'analyse des performances de la recherche binaire, une autre considération est le temps nécessaire pour comparer deux éléments. Pour les entiers et les chaînes, le temps requis augmente linéairement à mesure que la longueur de codage (généralement le nombre de bits ) des éléments augmente. Par exemple, comparer une paire d'entiers non signés de 64 bits nécessiterait de comparer jusqu'au double des bits comme comparer une paire d'entiers non signés de 32 bits. Le pire des cas est atteint lorsque les nombres entiers sont égaux. Cela peut être important lorsque les longueurs de codage des éléments sont grandes, comme avec de grands types entiers ou de longues chaînes, ce qui rend la comparaison des éléments coûteuse. De plus, la comparaison de valeurs à virgule flottante (la représentation numérique la plus courante des nombres réels ) est souvent plus coûteuse que la comparaison d'entiers ou de chaînes courtes.

Sur la plupart des architectures informatiques, le processeur dispose d'un cache matériel distinct de la RAM . Comme ils sont situés dans le processeur lui-même, les caches sont beaucoup plus rapides d'accès mais stockent généralement beaucoup moins de données que la RAM. Par conséquent, la plupart des processeurs stockent les emplacements mémoire auxquels on a accédé récemment, ainsi que les emplacements mémoire proches. Par exemple, lorsqu'un élément de tableau est accédé, l'élément lui-même peut être stocké avec les éléments qui sont stockés à proximité de lui dans la RAM, ce qui accélère l'accès séquentiel aux éléments de tableau qui sont proches les uns des autres ( localité de référence ) . Sur un tableau trié, la recherche binaire peut sauter vers des emplacements de mémoire distants si le tableau est volumineux, contrairement aux algorithmes (tels que la recherche linéaire et le sondage linéaire dans les tables de hachage ) qui accèdent aux éléments en séquence. Cela augmente légèrement le temps d'exécution de la recherche binaire pour les grands tableaux sur la plupart des systèmes.

Recherche binaire par rapport à d'autres schémas

Les tableaux triés avec recherche binaire sont une solution très inefficace lorsque les opérations d'insertion et de suppression sont entrelacées avec la récupération, prenant du temps pour chacune de ces opérations. De plus, les tableaux triés peuvent compliquer l'utilisation de la mémoire, en particulier lorsque des éléments sont souvent insérés dans le tableau. Il existe d'autres structures de données qui prennent en charge une insertion et une suppression beaucoup plus efficaces. La recherche binaire peut être utilisée pour effectuer une correspondance exacte et définir l'appartenance (déterminer si une valeur cible se trouve dans une collection de valeurs). Il existe des structures de données qui prennent en charge une correspondance exacte plus rapide et une appartenance définie. Cependant, contrairement à de nombreux autres schémas de recherche, la recherche binaire peut être utilisée pour une correspondance approximative efficace, effectuant généralement de telles correspondances dans le temps, quel que soit le type ou la structure des valeurs elles-mêmes. De plus, certaines opérations, telles que la recherche du plus petit et du plus grand élément, peuvent être effectuées efficacement sur un tableau trié.

Recherche linéaire

La recherche linéaire est un algorithme de recherche simple qui vérifie chaque enregistrement jusqu'à ce qu'il trouve la valeur cible. La recherche linéaire peut être effectuée sur une liste chaînée, ce qui permet une insertion et une suppression plus rapides qu'un tableau. La recherche binaire est plus rapide que la recherche linéaire pour les tableaux triés, sauf si le tableau est court, bien que le tableau doive être trié au préalable. Tous les algorithmes de tri basés sur la comparaison d'éléments, tels que quicksort et merge sort , nécessitent au moins des comparaisons dans le pire des cas. Contrairement à la recherche linéaire, la recherche binaire peut être utilisée pour une correspondance approximative efficace. Il existe des opérations telles que la recherche du plus petit et du plus grand élément qui peuvent être effectuées efficacement sur un tableau trié mais pas sur un tableau non trié.

Des arbres

Les arbres de recherche binaire sont recherchés à l'aide d'un algorithme similaire à la recherche binaire.

Un arbre de recherche binaire est une structure de données d' arbre binaire qui fonctionne sur le principe de la recherche binaire. Les enregistrements de l'arbre sont classés par ordre de tri, et chaque enregistrement de l'arbre peut être recherché à l'aide d'un algorithme similaire à la recherche binaire, en prenant un temps logarithmique moyen. L'insertion et la suppression nécessitent également un temps logarithmique moyen dans les arbres de recherche binaires. Cela peut être plus rapide que l'insertion et la suppression en temps linéaire de tableaux triés, et les arbres binaires conservent la capacité d'effectuer toutes les opérations possibles sur un tableau trié, y compris les requêtes de plage et d'approximation.

Cependant, la recherche binaire est généralement plus efficace pour la recherche car les arbres de recherche binaire seront très probablement imparfaitement équilibrés, ce qui entraînera des performances légèrement inférieures à celles de la recherche binaire. Cela s'applique même aux arbres de recherche binaires équilibrés , arbres de recherche binaires qui équilibrent leurs propres nœuds, car ils produisent rarement l'arbre avec le moins de niveaux possibles. À l'exception des arbres de recherche binaires équilibrés, l'arbre peut être gravement déséquilibré avec peu de nœuds internes avec deux enfants, ce qui entraîne un temps de recherche moyen et le pire des cas approchant les comparaisons. Les arbres de recherche binaires prennent plus de place que les tableaux triés.

Les arbres de recherche binaires se prêtent à une recherche rapide dans la mémoire externe stockée sur les disques durs, car les arbres de recherche binaires peuvent être efficacement structurés dans les systèmes de fichiers. Le B-tree généralise cette méthode d'organisation arborescente. Les arbres B sont fréquemment utilisés pour organiser le stockage à long terme, comme les bases de données et les systèmes de fichiers .

Hachage

Pour implémenter des tableaux associatifs , les tables de hachage , une structure de données qui mappe les clés aux enregistrements à l' aide d'une fonction de hachage , sont généralement plus rapides que la recherche binaire sur un tableau trié d'enregistrements. La plupart des implémentations de table de hachage ne nécessitent en moyenne qu'un temps constant amorti . Cependant, le hachage n'est pas utile pour les correspondances approximatives, telles que le calcul de la clé suivante la plus petite, la suivante la plus grande et la plus proche, car la seule information donnée sur une recherche échouée est que la cible n'est présente dans aucun enregistrement. La recherche binaire est idéale pour de telles correspondances, en les effectuant en temps logarithmique. La recherche binaire prend également en charge les correspondances approximatives. Certaines opérations, comme trouver le plus petit et le plus grand élément, peuvent être effectuées efficacement sur des tableaux triés mais pas sur des tables de hachage.

Définir des algorithmes d'appartenance

Un problème connexe à la recherche est l' appartenance définie . Tout algorithme qui effectue une recherche, comme la recherche binaire, peut également être utilisé pour l'appartenance à un ensemble. Il existe d'autres algorithmes plus spécifiquement adaptés à l'appartenance à un ensemble. Un tableau de bits est le plus simple, utile lorsque la plage de clés est limitée. Il stocke de manière compacte une collection de bits , chaque bit représentant une seule clé dans la plage de clés. Les tableaux de bits sont très rapides, ne nécessitant que du temps. Le type Judy1 du tableau Judy gère efficacement les clés 64 bits.

Pour des résultats approximatifs, les filtres de Bloom , une autre structure de données probabiliste basée sur le hachage, stockent un ensemble de clés en codant les clés à l'aide d'un tableau de bits et de plusieurs fonctions de hachage. Les filtres Bloom sont beaucoup plus économes en espace que les tableaux de bits dans la plupart des cas et pas beaucoup plus lents : avec les fonctions de hachage, les requêtes d'appartenance ne nécessitent que du temps. Cependant, les filtres Bloom souffrent de faux positifs .

Autres structures de données

Il existe des structures de données qui peuvent améliorer la recherche binaire dans certains cas pour la recherche et d'autres opérations disponibles pour les tableaux triés. Par exemple, les recherches, correspondances approximatives, et les opérations disponibles aux tableaux triés peuvent être effectués de manière plus efficace que la recherche binaire sur les structures de données spécialisées telles que les arbres van Emde Boas , arbres de fusion , essais , et des tableaux de bits . Ces structures de données spécialisées ne sont généralement plus rapides que parce qu'elles tirent parti des propriétés des clés avec un certain attribut (généralement des clés qui sont de petits entiers), et prendront donc du temps ou de l'espace pour les clés dépourvues de cet attribut. Tant que les clés peuvent être ordonnées, ces opérations peuvent toujours être effectuées au moins efficacement sur un tableau trié quelles que soient les clés. Certaines structures, telles que les tableaux de Judy, utilisent une combinaison d'approches pour atténuer cela tout en conservant l'efficacité et la capacité d'effectuer une correspondance approximative.

Variantes

Recherche binaire uniforme

La recherche binaire uniforme stocke la différence entre l'élément central actuel et les deux éléments intermédiaires possibles au lieu de limites spécifiques.

La recherche binaire uniforme stocke, au lieu des limites inférieure et supérieure, la différence d'index de l'élément du milieu de l'itération actuelle à l'itération suivante. Une table de correspondance contenant les différences est calculée au préalable. Par exemple, si le tableau à rechercher est [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] , l'élément du milieu ( ) serait 6 . Dans ce cas, l'élément central du sous-tableau gauche ( [1, 2, 3, 4, 5] ) est 3 et l'élément central du sous-tableau droit ( [7, 8, 9, 10, 11] ) est 9 . La recherche binaire uniforme stockerait la valeur de 3 car les deux indices diffèrent de 6 de la même quantité. Pour réduire l'espace de recherche, l'algorithme ajoute ou soustrait ce changement de l'index de l'élément du milieu. La recherche binaire uniforme peut être plus rapide sur les systèmes où il est inefficace de calculer le point médian, comme sur les ordinateurs décimaux .

Recherche exponentielle

Visualisation de la recherche exponentielle trouvant la borne supérieure pour la recherche binaire suivante

La recherche exponentielle étend la recherche binaire aux listes illimitées. Il commence par trouver le premier élément avec un indice qui est à la fois une puissance de deux et supérieur à la valeur cible. Ensuite, il définit cet index comme limite supérieure et passe à la recherche binaire. Une recherche prend des itérations avant le démarrage de la recherche binaire et au plus des itérations de la recherche binaire, où est la position de la valeur cible. La recherche exponentielle fonctionne sur des listes limitées, mais devient une amélioration par rapport à la recherche binaire uniquement si la valeur cible se situe près du début du tableau.

Recherche d'interpolation

Visualisation de la recherche d'interpolation par interpolation linéaire. Dans ce cas, aucune recherche n'est nécessaire car l'estimation de l'emplacement de la cible dans le réseau est correcte. D'autres implémentations peuvent spécifier une autre fonction pour estimer l'emplacement de la cible.

Au lieu de calculer le point médian, la recherche par interpolation estime la position de la valeur cible, en prenant en compte les éléments les plus bas et les plus hauts du tableau ainsi que la longueur du tableau. Cela fonctionne sur la base que le point médian n'est pas la meilleure estimation dans de nombreux cas. Par exemple, si la valeur cible est proche de l'élément le plus élevé du tableau, elle est susceptible d'être située près de la fin du tableau.

Une fonction d'interpolation courante est l'interpolation linéaire . Si est le tableau, sont respectivement les limites inférieure et supérieure et est la cible, alors la cible est estimée se situer à peu près entre et . Lorsque l'interpolation linéaire est utilisée et que la distribution des éléments du tableau est uniforme ou presque uniforme, la recherche par interpolation effectue des comparaisons.

En pratique, la recherche par interpolation est plus lente que la recherche binaire pour les petits tableaux, car la recherche par interpolation nécessite des calculs supplémentaires. Sa complexité temporelle augmente plus lentement que la recherche binaire, mais cela ne fait que compenser le calcul supplémentaire pour les grands tableaux.

Cascade fractionnée

Dans la cascade fractionnaire , chaque tableau a des pointeurs vers chaque deuxième élément d'un autre tableau, donc une seule recherche binaire doit être effectuée pour rechercher tous les tableaux.

La cascade fractionnaire est une technique qui accélère les recherches binaires pour le même élément dans plusieurs tableaux triés. La recherche de chaque tableau séparément nécessite du temps, où est le nombre de tableaux. La cascade fractionnée réduit cela en stockant des informations spécifiques dans chaque tableau sur chaque élément et sa position dans les autres tableaux.

La cascade fractionnée a été développée à l'origine pour résoudre efficacement divers problèmes de géométrie computationnelle . La cascade fractionnée a été appliquée ailleurs, comme dans l'exploration de données et le routage de protocole Internet .

Généralisation aux graphes

La recherche binaire a été généralisée pour fonctionner sur certains types de graphiques, où la valeur cible est stockée dans un sommet au lieu d'un élément de tableau. Les arbres de recherche binaires sont l'une de ces généralisations : lorsqu'un sommet (nœud) de l'arbre est interrogé, l'algorithme apprend soit que le sommet est la cible, soit dans quel sous-arbre la cible serait située. Cependant, cela peut être encore généralisé comme suit : étant donné un graphe pondéré positivement non orienté et un sommet cible, l'algorithme apprend lors de l'interrogation d'un sommet qu'il est égal à la cible, ou il reçoit une arête incidente qui se trouve sur le chemin le plus court entre le sommet interrogé et la cible. L'algorithme de recherche binaire standard est simplement le cas où le graphe est un chemin. De même, les arbres de recherche binaires sont le cas où les arêtes des sous-arbres gauche ou droit sont données lorsque le sommet interrogé est différent de la cible. Pour tous les graphes non orientés et pondérés positivement, il existe un algorithme qui trouve le sommet cible dans les requêtes dans le pire des cas.

Recherche binaire bruyante

Dans la recherche binaire bruyante, il existe une certaine probabilité qu'une comparaison soit incorrecte.

Les algorithmes de recherche binaire bruyants résolvent le cas où l'algorithme ne peut pas comparer de manière fiable les éléments du tableau. Pour chaque couple d'éléments, il existe une certaine probabilité que l'algorithme fasse la mauvaise comparaison. La recherche binaire bruyante peut trouver la position correcte de la cible avec une probabilité donnée qui contrôle la fiabilité de la position produite. Chaque procédure de recherche binaire bruyante doit faire au moins des comparaisons en moyenne, où est la fonction d'entropie binaire et est la probabilité que la procédure donne la mauvaise position. Le problème de recherche binaire bruyant peut être considéré comme un cas du jeu Rényi-Ulam , une variante de Twenty Questions où les réponses peuvent être fausses.

Recherche binaire quantique

Les ordinateurs classiques sont limités au pire des cas d' itérations exactes lors de l'exécution d'une recherche binaire. Les algorithmes quantiques pour la recherche binaire sont toujours limités à une proportion de requêtes (représentant des itérations de la procédure classique), mais le facteur constant est inférieur à un, ce qui permet une complexité temporelle moindre sur les ordinateurs quantiques . Toute procédure de recherche binaire quantique exacte, c'est-à-dire une procédure qui donne toujours le résultat correct, nécessite au moins des requêtes dans le pire des cas, où est le logarithme népérien . Il existe une procédure de recherche binaire quantique exacte qui s'exécute dans les requêtes dans le pire des cas. En comparaison, l'algorithme de Grover est l'algorithme quantique optimal pour rechercher une liste non ordonnée d'éléments, et il nécessite des requêtes.

Histoire

L'idée de trier une liste d'éléments pour permettre une recherche plus rapide remonte à l'Antiquité. Le premier exemple connu était la tablette Inakibit-Anu de Babylone datant de c.  200 avant notre ère . La tablette contenait environ 500 nombres sexagésimaux et leurs réciproques triés par ordre lexicographique , ce qui facilitait la recherche d'une entrée spécifique. De plus, plusieurs listes de noms triés par leur première lettre ont été découvertes sur les îles de la mer Égée . Catholicon , un dictionnaire latin terminé en 1286 de notre ère, a été le premier ouvrage à décrire les règles de tri des mots par ordre alphabétique, par opposition aux premières lettres.

En 1946, John Mauchly a fait la première mention de la recherche binaire dans le cadre des Moore School Lectures , un cours universitaire fondamental et fondamental en informatique. En 1957, William Wesley Peterson a publié la première méthode de recherche par interpolation. Chaque algorithme de recherche binaire publié ne fonctionnait que pour les tableaux dont la longueur est inférieure à une puissance de deux jusqu'en 1960, lorsque Derrick Henry Lehmer a publié un algorithme de recherche binaire qui fonctionnait sur tous les tableaux. En 1962, Hermann Bottenbruch a présenté une implémentation ALGOL 60 de la recherche binaire qui plaçait la comparaison d'égalité à la fin , augmentant le nombre moyen d'itérations d'un, mais réduisant à un le nombre de comparaisons par itération. La recherche binaire uniforme a été développée par AK Chandra de l'Université de Stanford en 1971. En 1986, Bernard Chazelle et Leonidas J. Guibas ont introduit la cascade fractionnaire comme méthode pour résoudre de nombreux problèmes de recherche en géométrie computationnelle .

Problèmes de mise en œuvre

Bien que l'idée de base de la recherche binaire soit relativement simple, les détails peuvent être étonnamment délicats

Lorsque Jon Bentley a assigné la recherche binaire comme un problème dans un cours pour programmeurs professionnels, il a constaté que 90 % n'avaient pas réussi à fournir une solution correcte après plusieurs heures de travail, principalement parce que les implémentations incorrectes ne s'exécutaient pas ou renvoyaient une mauvaise réponse dans de rares cas. cas de bord . Une étude publiée en 1988 montre qu'un code précis ne se trouve que dans cinq manuels sur vingt. De plus, la propre implémentation de Bentley de la recherche binaire, publiée dans son livre de 1986 Programming Pearls , contenait une erreur de débordement qui n'a pas été détectée pendant plus de vingt ans. L' implémentation de la bibliothèque de langage de programmation Java de la recherche binaire a eu le même bogue de débordement pendant plus de neuf ans.

Dans une implémentation pratique, les variables utilisées pour représenter les indices seront souvent de taille fixe (entiers), ce qui peut entraîner un débordement arithmétique pour les très grands tableaux. Si le point médian de l'étendue est calculé comme , la valeur de peut dépasser la plage d'entiers du type de données utilisé pour stocker le point médian, même si et se trouvent dans la plage. Si et ne sont pas négatifs, cela peut être évité en calculant le point médian comme .

Une boucle infinie peut se produire si les conditions de sortie de la boucle ne sont pas définies correctement. Une fois dépassé , la recherche a échoué et doit traduire l'échec de la recherche. De plus, la boucle doit être terminée lorsque l'élément cible est trouvé, ou dans le cas d'une implémentation où cette vérification est déplacée à la fin, des vérifications pour savoir si la recherche a réussi ou échoué à la fin doivent être en place. Bentley a découvert que la plupart des programmeurs qui ont mal implémenté la recherche binaire ont fait une erreur en définissant les conditions de sortie.

Prise en charge de la bibliothèque

Les bibliothèques standard de nombreux langages incluent des routines de recherche binaire :

  • C fournit la fonction bsearch() dans sa bibliothèque standard , qui est généralement implémentée via une recherche binaire, bien que la norme officielle ne l'exige pas.
  • C ++ de Standard Template Library fournit les fonctions binary_search(), lower_bound(), upper_bound()et equal_range().
  • La bibliothèque standard Phobos de D , dans le std.rangemodule, fournit un type SortedRange(renvoyé par sort()et les assumeSorted()fonctions) avec les méthodes contains(), equaleRange(), lowerBound()et trisect(), qui utilisent des techniques de recherche binaire par défaut pour les plages qui offrent un accès aléatoire.
  • COBOL fournit le SEARCH ALLverbe pour effectuer des recherches binaires sur des tables ordonnées COBOL.
  • Le sortpackage de bibliothèque standard de Go contient les fonctions Search, SearchInts, SearchFloat64set SearchStrings, qui implémentent la recherche binaire générale, ainsi que des implémentations spécifiques pour la recherche de tranches d'entiers, de nombres à virgule flottante et de chaînes, respectivement.
  • Java propose un ensemble de méthodes statiques surchargées binarySearch() dans les classes Arrayset Collectionsdans le java.utilpackage standard pour effectuer des recherches binaires sur les tableaux Java et sur Lists, respectivement.
  • Microsoft de .NET Framework statique offre 2.0 générique versions de l'algorithme de recherche binaire dans ses classes de base de collecte. Un exemple serait System.Arrayla méthode de BinarySearch<T>(T[] array, T value).
  • Pour Objective-C , le framework Cocoa fournit la NSArray -indexOfObject:inSortedRange:options:usingComparator:méthode dans Mac OS X 10.6+. Le framework Core Foundation C d' Apple contient également une CFArrayBSearchValues()fonction.
  • Python fournit le bisectmodule.
  • La classe Array de Ruby inclut une bsearchméthode avec une correspondance approximative intégrée.

Voir également

  • Méthode de bissection  - Algorithme pour trouver le zéro d'une fonction - la même idée utilisée pour résoudre des équations dans les nombres réels
  • Recherche binaire multiplicative  – Variation de la recherche binaire avec calcul simplifié du point médian

Notes et références

Cet article a été soumis à WikiJournal of Science pour une évaluation externe par des pairs universitaires en 2018 ( rapports des évaluateurs ). Le contenu mis à jour a été réintégré dans la page Wikipedia sous une licence CC-BY-SA-3.0 ( 2019 ). La version du dossier telle qu'elle a été examinée est : Anthony Lin ; et al. (2 juillet 2019). "Algorithme de recherche binaire" (PDF) . WikiJournal des sciences . 2 (1) : 5. doi : 10.15347/WJS/2019.005 . ISSN  2470-6345 . Wikidata  Q81434400 .

Remarques

Citations

Sources

Liens externes