- Valeur cherchée
- Bloc en cours
- Comparées
- Écartées
- Trouvées
Recherche par sauts
La recherche par sauts se situe entre la recherche linéaire et la recherche dichotomique. Elle avance dans une liste triée par sauts de m positions, en ne vérifiant que la dernière valeur de chaque bloc, jusqu'à atteindre un bloc dont la dernière valeur n'est pas plus petite que la cible. Elle parcourt alors ce bloc depuis le début. Choisissez la valeur et la taille du saut, et regardez combien de comparaisons demandent les sauts et le parcours. Appuyez sur Lecture pour regarder la recherche, ou sur Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. La ligne pointillée marque la valeur cherchée, et la zone ombrée est le bloc en cours. La recherche par sauts exige une liste triée : une liste non triée est donc d'abord triée. Choisissez la valeur, la taille du saut, 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
- Choisissez la valeur à chercher, la taille du saut et le nombre de barres. Ou saisissez vos propres nombres : la recherche par sauts les trie d'abord.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans la recherche.
- Essayez une taille de saut de 2 puis de 8 sur 40 barres, et comparez le nombre de comparaisons avec celui de √n.
Comment fonctionne la recherche par sauts
Découpez la liste triée en blocs de m valeurs. Regardez la dernière valeur du premier bloc. Si elle est plus petite que la cible, la cible ne peut se trouver nulle part dans ce bloc : sautez à la fin du bloc suivant et regardez à nouveau. Dès que la dernière valeur d'un bloc n'est pas plus petite, la cible ne peut être que dans ce bloc : revenez à son début et vérifiez ses valeurs une par une jusqu'à trouver la cible ou la dépasser.
Choisir la taille du saut
Avec n valeurs, les sauts demandent jusqu'à n/m comparaisons et le parcours jusqu'à m. De petits sauts rendent le parcours court mais les sauts nombreux ; de grands sauts font l'inverse. Le total n/m + m est minimal pour m = √n, ce qui donne environ 2√n comparaisons : au plus 13 pour 40 valeurs, contre 40 pour la recherche linéaire et 6 pour la recherche dichotomique. La recherche par sauts ne recule jamais de plus d'un bloc, ce qui aide quand revenir en arrière dans les données est lent.
Questions fréquemment posées
Comment fonctionne la recherche par sauts ?
Dans une liste triée, elle avance par sauts de m positions et vérifie la dernière valeur de chaque bloc. Dès que cette valeur n'est plus inférieure à la cible, la cible ne peut être que dans ce bloc, qu'elle parcourt alors depuis le début.
Quelle est la meilleure taille de saut ?
√n, arrondi. Les sauts coûtent jusqu'à n/m comparaisons et le parcours jusqu'à m, et leur somme est minimale quand les deux sont égaux, pour m = √n. Cela donne environ 2√n comparaisons dans le pire cas.
La recherche par sauts est-elle plus rapide que la recherche dichotomique ?
Non, la recherche dichotomique demande moins de comparaisons : environ log₂ n contre environ 2√n. La recherche par sauts peut tout de même l'emporter quand revenir en arrière dans les données coûte cher, car elle ne recule qu'une seule fois, jusqu'au début d'un bloc.
Quelle correspondance trouve-t-elle quand des valeurs se répètent ?
La première. Chaque bloc sauté se termine par une valeur plus petite que la cible, donc aucun bloc précédent ne peut contenir de correspondance, et le parcours commence au début du bloc.
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