Comparaisons
Encore possibles
La recherche dichotomique demanderait

  • Valeur cherchée
  • Encore possibles
  • Comparées
  • Écartées
  • Trouvées

En savoir plus sur la recherche exponentielle

Recherche exponentielle

La recherche exponentielle trouve une valeur dans une liste triée en deux phases. D'abord, elle regarde les positions 1, 2, 4, 8, 16 et ainsi de suite, en doublant à chaque fois, jusqu'à une valeur qui n'est pas plus petite que la valeur cherchée. Puis elle cherche par dichotomie dans l'intervalle entre les deux dernières positions. Choisissez la valeur à chercher et voyez pourquoi les valeurs proches du début sont trouvées en quelques comparaisons seulement. Appuyez sur Lecture pour regarder la recherche, ou sur Étape et Retour pour avancer d'une étape à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. La ligne pointillée marque la valeur cherchée, et la partie ombrée montre où elle peut encore se trouver. La recherche exponentielle exige une liste triée, donc une liste non triée est d'abord triée. Choisissez la valeur, le nombre de barres, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Choisissez la valeur à chercher et le nombre de barres. Ou saisissez vos propres nombres : la recherche exponentielle les trie d'abord.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une étape à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans la recherche.
  3. Cherchez une valeur proche du début, puis une proche de la fin, et comparez le nombre avec « La recherche dichotomique demanderait ».

Comment fonctionne la recherche exponentielle

Regardez la valeur à la position 1. Si elle est plus petite que la valeur cherchée, regardez la position 2, puis 4, 8, 16, en doublant à chaque fois. Dès qu'une valeur n'est pas plus petite, arrêtez : la valeur cherchée ne peut se trouver qu'après la position regardée juste avant, et avant celle-ci. Cherchez par dichotomie dans cet intervalle. Si le doublement dépasse la fin de la liste, cherchez par dichotomie de la dernière position regardée jusqu'à la fin.

Rapide près du début, sans connaître la longueur

Pour atteindre une valeur à la position i, le doublement demande environ log₂ i étapes, et l'intervalle trouvé contient moins de i valeurs, donc la recherche dichotomique en demande environ log₂ i de plus. Cela fait environ 2 log₂ i en tout, ce qui dépend de la position de la valeur cherchée, pas de la longueur de la liste. Les valeurs proches du début sont trouvées plus vite qu'avec une simple recherche dichotomique ; celles proches de la fin coûtent jusqu'à environ deux fois plus. Comme elle n'a jamais besoin de la longueur de la liste, elle fonctionne aussi sur des listes trop longues pour être mesurées ou sans fin connue.

Questions fréquemment posées

Comment fonctionne la recherche exponentielle ?

Sur une liste triée, elle vérifie les positions 1, 2, 4, 8 et ainsi de suite jusqu'à une valeur qui n'est pas plus petite que la valeur cherchée. La valeur cherchée ne peut alors se trouver qu'entre les deux dernières positions vérifiées, et une recherche dichotomique dans cet intervalle la trouve.

La recherche exponentielle est-elle plus rapide que la recherche dichotomique ?

Quand la valeur cherchée est près du début de la liste, oui : elle demande environ 2 log₂ i comparaisons pour une valeur à la position i, quelle que soit la longueur de la liste. Quand elle est près de la fin, la simple recherche dichotomique est plus rapide, jusqu'à environ deux fois.

À quoi sert-elle ?

À chercher dans des listes de longueur inconnue ou illimitée, comme un flux ou une suite infinie, et à fusionner des séquences triées, où la correspondance suivante est souvent proche. Le mode galop de Timsort utilise la même idée de doublement.

Pourquoi l'appelle-t-on exponentielle ?

Parce que les positions vérifiées croissent de façon exponentielle : 1, 2, 4, 8, 16, chacune le double de la précédente. On l'appelle aussi recherche par doublement ou recherche galopante.

Mes nombres sont-ils envoyés quelque part ?

Non. La recherche s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

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

Aller à l'éditeur