Recherche par sauts
La recherche par sauts, c'est chercher une page dans un livre sans table des matières : vous avancez d'un paquet de pages à la fois en jetant un œil aux numéros, et une fois allé trop loin, vous feuilletez en arrière le dernier paquet. Dans une liste triée, elle demande bien moins de comparaisons que de vérifier chaque valeur.
L'idée
Dans une liste triée, la dernière valeur d'un bloc vous indique si la cible peut se trouver dans ce bloc ou non : si elle est plus petite que la cible, toutes les valeurs du bloc le sont aussi. Inutile donc de regarder à l'intérieur. Vérifiez tour à tour la dernière valeur de chaque bloc, en sautant des blocs entiers, jusqu'à en trouver une qui n'est pas plus petite que la cible. La cible ne peut alors être que dans ce bloc : parcourez-le depuis son début.
Un exemple
Cherchons 23 dans 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, avec des blocs de 3. Le premier bloc se termine par 8, plus petit : on le saute. Le deuxième se termine par 23, qui n'est pas plus petit, donc 23 ne peut être que dans 12, 16, 23. Le parcourir donne 12, 16 puis 23 : trouvé en 5 comparaisons, là où la recherche linéaire en demande 6 et la recherche dichotomique 3. Si l'on cherche 40, les fins de bloc 8, 23 et 72 mènent au bloc 38, 56, 72 ; 38 est plus petit et 56 déjà plus grand, donc 40 n'y est pas : là encore 5 comparaisons.
Pourquoi √n
Avec des blocs de m valeurs, trouver le bon bloc demande au plus environ n/m comparaisons, et le parcourir au plus m. Peu de sauts longs rendent le parcours long ; beaucoup de sauts courts rendent les sauts longs. La somme n/m + m est minimale quand les deux parties sont égales, pour m = √n, où elle vaut environ 2√n. Pour 40 valeurs, cela donne des blocs de 6 et au plus 13 comparaisons ; pour un million de valeurs, des blocs de 1 000 et environ 2 000 comparaisons.
Où elle a sa place
La recherche dichotomique demande moins de comparaisons, environ log₂ n. Mais elle saute d'un bout à l'autre de la liste, alors que la recherche par sauts ne fait qu'avancer et ne recule qu'une fois, jusqu'au début d'un bloc. Elle était donc intéressante pour des données sur bande ou dans une structure chaînée, où revenir en arrière est lent. Ben Shneiderman l'a décrite sous le nom de « jump searching » en 1978. La même idée de découper en blocs de √n, souvent appelée décomposition en racine carrée, se retrouve dans bien d'autres algorithmes.
À vous d'essayer
Ouvrez l'application, choisissez une valeur dans Rechercher, puis appuyez sur Étape. Chaque saut met en évidence la dernière valeur d'un bloc ; les blocs sautés s'estompent, et le bloc qui peut contenir la cible est ombré pendant qu'il est parcouru. Avec 40 barres, passez la Taille du saut de √n à 2 ou 8 et regardez l'équilibre entre sauts et parcours se déplacer.
Questions fréquemment posées
Quelle est la complexité en temps de la recherche par sauts ?
O(√n) avec des blocs de √n valeurs : au plus environ 2√n comparaisons. Elle demande une mémoire supplémentaire en O(1) et une liste triée.
Quelle est la différence entre la recherche par sauts et la recherche dichotomique ?
La recherche dichotomique divise par deux la partie restante à chaque fois et demande environ log₂ n comparaisons, mais fait des allers-retours. La recherche par sauts avance par pas fixes et parcourt un bloc, demande environ 2√n comparaisons, et ne recule qu'une fois.
Peut-on parcourir le dernier bloc avec une recherche dichotomique ?
Oui. Chercher dans le bloc par recherche dichotomique fait passer le parcours de m comparaisons à environ log₂ m. Les sauts coûtent toujours n/m, donc des blocs plus grands deviennent alors rentables.
La recherche par sauts exige-t-elle une liste triée ?
Oui. Sauter un bloc n'est sûr que parce qu'une dernière valeur plus petite signifie que toutes ses valeurs sont plus petites. L'application trie d'abord une liste non triée.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer la recherche par sauts