Recherche exponentielle - Exponential search

Dans la science informatique , une recherche exponentielle (aussi appelée recherche doubler ou galopant recherche ou recherche Struzik ) est un algorithme , créé par Jon Bentley et Andrew Chi-Chih Yao en 1976, pour la recherche triée, listes sans bornes / infinies. Il existe de nombreuses façons de l'implémenter, la plus courante étant de déterminer une plage dans laquelle réside la clé de recherche et d'effectuer une recherche binaire dans cette plage. Cela prend O (log  i ) où i est la position de la clé de recherche dans la liste, si la clé de recherche est dans la liste, ou la position où la clé de recherche devrait être, si la clé de recherche n'est pas dans la liste.

La recherche exponentielle peut également être utilisée pour rechercher dans des listes limitées. La recherche exponentielle peut même surpasser les recherches plus traditionnelles pour les listes bornées, telles que la recherche binaire, lorsque l'élément recherché est proche du début du tableau. En effet, la recherche exponentielle s'exécutera en temps O (log  i ), où i est l'index de l'élément recherché dans la liste, alors que la recherche binaire s'exécuterait en temps O (log  n ), où n est le nombre d'éléments dans la liste.

Algorithme

La recherche exponentielle permet de rechercher dans une liste triée et illimitée une valeur d'entrée spécifiée (la «clé» de recherche). L'algorithme se compose de deux étapes. La première étape détermine une plage dans laquelle la clé de recherche résiderait si elle était dans la liste. Dans un deuxième temps, une recherche binaire est effectuée sur cette plage. Dans la première étape, en supposant que la liste est triée par ordre croissant, l'algorithme recherche le premier exposant , j , où la valeur 2 ^j est supérieure à la clé de recherche. Cette valeur, 2 ^j devient la limite supérieure de la recherche binaire avec la puissance précédente de 2, 2 ^{j - 1} , étant la limite inférieure de la recherche binaire.

// Returns the position of key in the array arr of length size.
template <typename T>
int exponential_search(T arr[], int size, T key)
{
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;
    }

    return binary_search(arr, key, bound/2, min(bound + 1, size));
}

À chaque étape, l'algorithme compare la valeur de la clé de recherche avec la valeur de la clé à l'index de recherche actuel. Si l'élément de l'index actuel est plus petit que la clé de recherche, l'algorithme se répète, sautant à l'index de recherche suivant en le doublant, calculant la puissance suivante de 2. Si l'élément de l'index actuel est plus grand que la clé de recherche, le L'algorithme sait maintenant que la clé de recherche, si elle est contenue dans la liste, est située dans l'intervalle formé par l'index de recherche précédent, 2 ^{j - 1} , et l'index de recherche actuel, 2 ^j . La recherche binaire est alors effectuée avec le résultat soit d'un échec, si la clé de recherche n'est pas dans la liste, soit de la position de la clé de recherche dans la liste.

Performance

La première étape de l'algorithme prend un temps O (log  i ), où i est l'index où la clé de recherche se trouverait dans la liste. En effet, lors de la détermination de la limite supérieure de la recherche binaire, la boucle while est exécutée exactement fois. Puisque la liste est triée, après avoir doublé les temps d' index de recherche , l'algorithme sera à un index de recherche supérieur ou égal à i as . En tant que tel, la première étape de l'algorithme prend O (log  i ) temps. ${\ displaystyle \ lceil \ log (i) \ rceil}$${\ displaystyle \ lceil \ log (i) \ rceil}$${\ displaystyle 2 ^ {\ lceil \ log (i) \ rceil} \ geq i}$

La deuxième partie de l'algorithme prend également un temps O (log  i ). Comme la deuxième étape est simplement une recherche binaire, elle prend O (log  n ) où n est la taille de l'intervalle recherché. La taille de cet intervalle serait de 2 ^j - 2 ^{j - 1} où, comme vu ci-dessus, j = log  i . Cela signifie que la taille de l'intervalle recherché est de 2 ^{log i} - 2 ^{log i - 1} = 2 ^{log i - 1} . Cela nous donne un temps d'exécution de log (2 ^{log i - 1} ) = log ( i ) - 1 = O (log  i ).

Cela donne à l'algorithme un temps d'exécution total, calculé en additionnant les temps d'exécution des deux étapes, de O (log  i ) + O (log  i ) = 2 O (log  i ) = O (log  i ).

Alternatives

Bentley et Yao ont suggéré plusieurs variantes pour la recherche exponentielle. Ces variantes consistent à effectuer une recherche binaire, par opposition à une recherche unaire, lors de la détermination de la borne supérieure de la recherche binaire dans la deuxième étape de l'algorithme. Cela divise la première étape de l'algorithme en deux parties, faisant de l'algorithme un algorithme en trois étapes dans l'ensemble. La nouvelle première étape détermine une valeur , tout comme avant, qui est plus grande que la clé de recherche et inférieure à la clé de recherche. Auparavant, était déterminé de manière unaire en calculant la puissance suivante de 2 (c'est-à-dire en ajoutant 1 à j ). Dans la variante, il est proposé de doubler à la place (par exemple, sauter de 2 ² à 2 ⁴ au lieu de 2 ³ ). Le premier tel qui est supérieur à la clé de recherche forme une limite supérieure beaucoup plus grossière qu'auparavant. Une fois que cela est trouvé, l'algorithme passe à sa deuxième étape et une recherche binaire est effectuée sur l'intervalle formé par et , donnant l'exposant supérieur j plus précis . A partir de là, la troisième étape de l'algorithme effectue la recherche binaire sur l'intervalle 2 ^{j - 1} et 2 ^j , comme précédemment. La performance de cette variation est = O (log  i ). ${\ displaystyle j '}$${\ displaystyle 2 ^ {j '}}$${\ displaystyle 2 ^ {j '/ 2}}$${\ displaystyle j '}$${\ displaystyle j '}$${\ displaystyle j '}$${\ displaystyle 2 ^ {j '}}$${\ displaystyle j '}$${\ displaystyle j '/ 2}$${\ displaystyle j '}$${\ displaystyle \ lfloor \ log i \ rfloor +2 \ lfloor \ log (\ lfloor \ log i \ rfloor +1) \ rfloor +1}$

Bentley et Yao généralisent cette variation en une variante où n'importe quel nombre, k , de recherches binaires est effectué pendant la première étape de l'algorithme, donnant la variation de recherche binaire k- imbriquée. Le runtime asymptotique ne change pas pour les variations, s'exécutant en temps O (log  i ), comme avec l'algorithme de recherche exponentielle d'origine.

En outre, une structure de données avec une version étroite de la propriété de doigt dynamique peut être donnée lorsque le résultat ci-dessus de la recherche binaire imbriquée k est utilisé sur un tableau trié. En utilisant cela, le nombre de comparaisons effectuées lors d'une recherche est log ( d ) + log log ( d ) + ... + O (log  ^* d ), où d est la différence de rang entre le dernier élément auquel on a accédé et le élément en cours d'accès.

Voir également

• Recherche linéaire
• Recherche binaire
• Recherche d'interpolation
• Recherche ternaire
• Table de hachage

Les références