Recherche binaire multiplicative - Multiplicative binary search
 Visualisation de l'algorithme de recherche binaire multiplicative où 7 est la valeur cible.
| |
| Classe | Algorithme de recherche |
|---|---|
| Structure de données | Tableau |
| Les pires performances des cas | O (log n ) |
| Meilleures performances | O (1) |
| Performance moyenne | O (log n ) |
| Complexité de l'espace dans le pire des cas | O (1) |
En informatique , la recherche binaire multiplicative est une variante de la recherche binaire qui utilise une permutation spécifique de clés dans un tableau au lieu de l'ordre trié utilisé par la recherche binaire ordinaire. La recherche binaire multiplicative a été décrite pour la première fois par Thomas Standish en 1980. Cet algorithme a été initialement proposé pour simplifier le calcul de l'indice médian sur de petits ordinateurs sans division efficace ni opérations de décalage. Sur le matériel moderne, la nature compatible avec le cache de la recherche binaire multiplicative la rend adaptée à la recherche hors cœur sur le stockage orienté bloc comme alternative aux arbres B et aux arbres B + . Pour des performances optimales, le facteur de branchement d'un arbre B ou d'un arbre B + doit correspondre à la taille de bloc du système de fichiers sur lequel il est stocké. La permutation utilisée par la recherche binaire multiplicative place le nombre optimal de clés dans le premier bloc ( racine ), quelle que soit la taille du bloc.
La recherche binaire multiplicative est utilisée par certains compilateurs d'optimisation pour implémenter des instructions switch .
Algorithme
La recherche binaire multiplicative fonctionne sur un tableau trié permuté. Les clés sont stockées dans le tableau dans l'ordre des niveaux de l' arbre de recherche binaire équilibré correspondant . Cela place le premier pivot d'une recherche binaire comme premier élément du tableau. Les seconds pivots sont placés aux deux positions suivantes.
Etant donné une matrice A de n éléments avec des valeurs A 0 ... A n -1 , et la valeur cible T , ce qui suit sous - programme utilise une recherche binaire multiplicatif pour trouver l'indice de T en A .
- Mettre i à 0
- si i ≥ n , la recherche se termine sans succès.
- si A i = T , la recherche est effectuée; retourner i .
- si A i < T , réglez i sur 2 × i + 1 et passez à l'étape 2.
- si A i > T , réglez i sur 2 × i + 2 et passez à l'étape 2.
Voir également
- Arborescence de recherche binaire - Structure de données sous forme d'arborescence triée pour une recherche rapide
- Méthodes de stockage des arbres binaires
- Ahnentafel - Système de numérotation généalogique pour lister les ancêtres directs d'une personne