Recherche exponentielle

La recherche dichotomique doit savoir où finit la liste avant de regarder au milieu. Pas la recherche exponentielle : elle avance au galop, par pas de plus en plus grands, jusqu'à dépasser la valeur cherchée, puis cherche par dichotomie dans le dernier pas. Elle est donc idéale pour les listes de longueur inconnue, et rapide pour les valeurs proches du début.

Une rangée de barres triées avec des sauts dont la longueur double au-dessus des positions 1, 2, 4 et 8, et l'intervalle entre les deux derniers sauts ombré
Une rangée de barres triées avec des sauts dont la longueur double au-dessus des positions 1, 2, 4 et 8, et l'intervalle entre les deux derniers sauts ombré

L'idée

Vérifiez la valeur à la position 1, puis 2, 4, 8, 16 et ainsi de suite, chaque position valant le double de la précédente. Tant que la valeur trouvée est plus petite que la valeur cherchée, celle-ci est forcément plus loin. Dès qu'une valeur n'est pas plus petite, la valeur cherchée est piégée : elle se trouve après la position vérifiée juste avant, et pas plus loin que celle-ci. Cet intervalle est trié, donc une recherche dichotomique trouve la valeur cherchée, ou montre qu'elle est absente.

Un exemple

Cherchez 23 dans 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. La position 1 contient 2, la position 2 contient 5, la position 4 contient 12, toutes plus petites. La position 8 contient 56, qui est plus grand, donc 23 ne peut être qu'aux positions 5 à 7. La recherche dichotomique vérifie le milieu, la position 6, et trouve 23 : 5 comparaisons, là où la simple recherche dichotomique en demande 3. Chercher 12 dans la même liste s'arrête à la position 4 après 3 comparaisons, une de moins que la recherche dichotomique, et 2 est trouvé à la position 1 en une seule comparaison.

Combien de comparaisons

Pour une valeur à la position i, le doublement s'arrête après environ log₂ i étapes et laisse un intervalle de moins de i positions, que la recherche dichotomique parcourt en environ log₂ i de plus. La recherche coûte donc environ 2 log₂ i comparaisons, quelle que soit la longueur de la liste. Quand la valeur cherchée est près du début, c'est mieux que la recherche dichotomique, qui paie toujours environ log₂ n. Quand elle est près de la fin, la recherche exponentielle paie jusqu'à environ deux fois plus. Pour 40 valeurs, l'application fait en moyenne environ 3 comparaisons pour les cinq premières positions et environ 9 pour les cinq dernières, contre environ 4,6 pour la recherche dichotomique.

Longueur inconnue et galop

Jon Bentley et Andrew Yao ont décrit cette stratégie de doublement en 1976 pour la recherche non bornée : trouver une valeur dans une suite triée sans fin connue, comme une liste infinie ou un flux qu'on ne peut que sonder. La même idée accélère la fusion. Quand l'une de deux séquences triées gagne sans cesse, Timsort passe en mode galop : il regarde 1, 2, 4, 8 positions plus loin dans l'autre séquence pour trouver où va la valeur suivante, au lieu d'avancer d'une position à la fois.

À vous de jouer

Ouvrez l'application, choisissez une valeur dans Rechercher et appuyez sur Étape. Chaque vérification des positions 1, 2, 4, 8 et ainsi de suite est mise en évidence ; dès qu'une valeur n'est pas plus petite, l'intervalle entre les deux dernières positions est ombré et la recherche dichotomique prend le relais. Cherchez une petite valeur puis une grande, et comparez le nombre avec la tuile de la recherche dichotomique.

Questions fréquemment posées

Quelle est la complexité en temps de la recherche exponentielle ?

O(log i) pour une valeur à la position i, donc au plus O(log n) pour une liste de n valeurs. Elle demande O(1) de mémoire supplémentaire et une liste triée.

Quelle est la différence entre recherche exponentielle et recherche dichotomique ?

La recherche dichotomique part de la liste entière et a besoin de sa longueur. La recherche exponentielle trouve d'abord, en doublant, un intervalle qui contient la valeur cherchée, puis cherche par dichotomie dans cet intervalle seulement. Elle est plus rapide quand la valeur cherchée est près du début et fonctionne sans connaître la longueur.

Pourquoi doubler le pas plutôt qu'ajouter une valeur fixe ?

Ajouter un pas fixe, c'est la recherche par sauts : pour traverser la liste, elle doit vérifier environ n divisé par le pas positions. Doubler atteint la position i en environ log₂ i vérifications, et l'intervalle restant n'est jamais plus de deux fois trop grand, donc la recherche dichotomique qui suit reste courte.

Où utilise-t-on la recherche exponentielle ?

Pour chercher dans des données triées non bornées ou très longues, pour fusionner des séquences triées (le galop de Timsort), et pour trouver la première position où une condition devient vraie quand aucune limite supérieure n'est connue.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer la recherche exponentielle