Recherche sautée
Comme Recherche binaire Jump Search est un algorithme de recherche de tableaux triés. L'idée de base est de vérifier moins d'éléments (que recherche linéaire ) en avançant par étapes fixes ou en sautant certains éléments au lieu de rechercher tous les éléments.
Par exemple, supposons que nous ayons un tableau arr[] de taille n et un bloc (à sauter) de taille m. Ensuite on cherche dans les index arr[0] arr[m] arr[2m].....arr[km] et ainsi de suite. Une fois que nous avons trouvé l'intervalle (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Considérons le tableau suivant : (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). La longueur du tableau est de 16. La recherche Jump trouvera la valeur de 55 avec les étapes suivantes en supposant que la taille du bloc à sauter est de 4.
ÉTAPE 1 : Sauter de l'index 0 à l'index 4 ;
ÉTAPE 2 : Sauter de l'index 4 à l'index 8 ;
ÉTAPE 3 : Sauter de l'index 8 à l'index 12 ;
ÉTAPE 4 : Puisque l'élément à l'index 12 est supérieur à 55, nous allons revenir en arrière pour arriver à l'index 8.
ÉTAPE 5 : Effectuez une recherche linéaire à partir de l'index 8 pour obtenir l'élément 55.
Performances par rapport à la recherche linéaire et binaire :
Si nous le comparons à la recherche linéaire et binaire, il en ressort que c'est mieux que la recherche linéaire mais pas mieux que la recherche binaire.
L’ordre croissant de performance est le suivant :
recherche linéaire < jump search < binary search
Quelle est la taille de bloc optimale à ignorer ?
Dans le pire des cas, nous devons faire n/m sauts et si la dernière valeur vérifiée est supérieure à l'élément à rechercher, nous effectuons des comparaisons m-1 davantage pour une recherche linéaire. Par conséquent, le nombre total de comparaisons dans le pire des cas sera ((n/m) + m-1). La valeur de la fonction ((n/m) + m-1) sera minimale lorsque m = √n. Par conséquent, la meilleure taille de pas est m = √ n.
Étapes de l'algorithme
- Jump Search est un algorithme permettant de trouver une valeur spécifique dans un tableau trié en parcourant certaines étapes du tableau.
- Les étapes sont déterminées par le carré de la longueur du tableau.
- Voici un algorithme étape par étape pour la recherche par saut :
- Déterminez la taille du pas m en prenant le carré de la longueur du tableau n.
- Commencez par le premier élément du tableau et sautez m pas jusqu'à ce que la valeur à cette position soit supérieure à la valeur cible.
Une fois qu'une valeur supérieure à la cible est trouvée, effectuez une recherche linéaire en commençant à l'étape précédente jusqu'à ce que la cible soit trouvée ou qu'il soit clair que la cible n'est pas dans le tableau.
Si la cible est trouvée, renvoyez son index. Sinon, renvoyez -1 pour indiquer que la cible n'a pas été trouvée dans le tableau.
Exemple 1 :
C++ // C++ program to implement Jump Search #include using namespace std ; int jumpSearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int prev = 0 ; while ( arr [ min ( step n ) -1 ] < x ) { prev = step ; step += sqrt ( n ); if ( prev >= n ) return -1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == min ( step n )) return -1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return -1 ; } // Driver program to test function int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x n ); // Print the index where 'x' is located cout < < ' n Number ' < < x < < ' is at index ' < < index ; return 0 ; } // Contributed by nuclode
C #include #include int min ( int a int b ){ if ( b > a ) return a ; else return b ; } int jumpsearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int prev = 0 ; while ( arr [ min ( step n ) -1 ] < x ) { prev = step ; step += sqrt ( n ); if ( prev >= n ) return -1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == min ( step n )) return -1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return -1 ; } int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int index = jumpsearch ( arr x n ); if ( index >= 0 ) printf ( 'Number is at %d index' index ); else printf ( 'Number is not exist in the array' ); return 0 ; } // This code is contributed by Susobhan Akhuli
Java // Java program to implement Jump Search. public class JumpSearch { public static int jumpSearch ( int [] arr int x ) { int n = arr . length ; // Finding block size to be jumped int step = ( int ) Math . floor ( Math . sqrt ( n )); // Finding the block where element is // present (if it is present) int prev = 0 ; for ( int minStep = Math . min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . min ( step n ) - 1 ) { prev = step ; step += ( int ) Math . floor ( Math . sqrt ( n )); if ( prev >= n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == Math . min ( step n )) return - 1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return - 1 ; } // Driver program to test function public static void main ( String [ ] args ) { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x ); // Print the index where 'x' is located System . out . println ( 'nNumber ' + x + ' is at index ' + index ); } }
Python # Python3 code to implement Jump Search import math def jumpSearch ( arr x n ): # Finding block size to be jumped step = math . sqrt ( n ) # Finding the block where element is # present (if it is present) prev = 0 while arr [ int ( min ( step n ) - 1 )] < x : prev = step step += math . sqrt ( n ) if prev >= n : return - 1 # Doing a linear search for x in # block beginning with prev. while arr [ int ( prev )] < x : prev += 1 # If we reached next block or end # of array element is not present. if prev == min ( step n ): return - 1 # If element is found if arr [ int ( prev )] == x : return prev return - 1 # Driver code to test function arr = [ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ] x = 55 n = len ( arr ) # Find the index of 'x' using Jump Search index = jumpSearch ( arr x n ) # Print the index where 'x' is located print ( 'Number' x 'is at index' ' %.0f ' % index ) # This code is contributed by 'Sharad_Bhardwaj'.
C# // C# program to implement Jump Search. using System ; public class JumpSearch { public static int jumpSearch ( int [] arr int x ) { int n = arr . Length ; // Finding block size to be jumped int step = ( int ) Math . Sqrt ( n ); // Finding the block where the element is // present (if it is present) int prev = 0 ; for ( int minStep = Math . Min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . Min ( step n ) - 1 ) { prev = step ; step += ( int ) Math . Sqrt ( n ); if ( prev >= n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == Math . Min ( step n )) return - 1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return - 1 ; } // Driver program to test function public static void Main () { int [] arr = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x ); // Print the index where 'x' is located Console . Write ( 'Number ' + x + ' is at index ' + index ); } }
JavaScript < script > // Javascript program to implement Jump Search function jumpSearch ( arr x n ) { // Finding block size to be jumped let step = Math . sqrt ( n ); // Finding the block where element is // present (if it is present) let prev = 0 ; for ( int minStep = Math . Min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . Min ( step n ) - 1 ) { prev = step ; step += Math . sqrt ( n ); if ( prev >= n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == Math . min ( step n )) return - 1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return - 1 ; } // Driver program to test function let arr = [ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ]; let x = 55 ; let n = arr . length ; // Find the index of 'x' using Jump Search let index = jumpSearch ( arr x n ); // Print the index where 'x' is located document . write ( `Number ${ x } is at index ${ index } ` ); // This code is contributed by _saurabh_jaiswal < /script>
PHP // PHP program to implement Jump Search function jumpSearch ( $arr $x $n ) { // Finding block size to be jumped $step = sqrt ( $n ); // Finding the block where element is // present (if it is present) $prev = 0 ; while ( $arr [ min ( $step $n ) - 1 ] < $x ) { $prev = $step ; $step += sqrt ( $n ); if ( $prev >= $n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( $arr [ $prev ] < $x ) { $prev ++ ; // If we reached next block or end of // array element is not present. if ( $prev == min ( $step $n )) return - 1 ; } // If element is found if ( $arr [ $prev ] == $x ) return $prev ; return - 1 ; } // Driver program to test function $arr = array ( 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ); $x = 55 ; $n = sizeof ( $arr ) / sizeof ( $arr [ 0 ]); // Find the index of '$x' using Jump Search $index = jumpSearch ( $arr $x $n ); // Print the index where '$x' is located echo 'Number ' . $x . ' is at index ' . $index ; return 0 ; ?>
Sortir:
Number 55 is at index 10
Complexité temporelle : O(?n)
Espace auxiliaire : O(1)Avantages de la recherche sautée :
- Mieux qu'une recherche linéaire de tableaux où les éléments sont uniformément répartis.
- La recherche sautée a une complexité temporelle inférieure à celle d'une recherche linéaire de grands tableaux.
- Le nombre d'étapes effectuées dans la recherche par saut est proportionnel à la racine carrée de la taille du tableau, ce qui la rend plus efficace pour les grands tableaux.
- Il est plus facile à mettre en œuvre que d’autres algorithmes de recherche comme la recherche binaire ou la recherche ternaire.
- La recherche par saut fonctionne bien pour les tableaux où les éléments sont dans l'ordre et uniformément répartis, car elle peut accéder à une position plus proche dans le tableau à chaque itération.
Points importants :
- Fonctionne uniquement avec des tableaux triés.
- La taille optimale d'un bloc à sauter est (? n). Cela rend la complexité temporelle de Jump Search O(? n).
- La complexité temporelle de la recherche par saut se situe entre la recherche linéaire ((O(n)) et la recherche binaire (O(Log n)).
- La recherche binaire est meilleure que la recherche par saut, mais la recherche par saut a l'avantage de ne revenir en arrière qu'une seule fois (la recherche binaire peut nécessiter jusqu'à O (Log n) sauts, dans le cas où l'élément à rechercher est le plus petit élément ou juste plus grand que le plus petit). Ainsi, dans un système où la recherche binaire est coûteuse, nous utilisons Jump Search.
Références :
https://en.wikipedia.org/wiki/Jump_search
Si vous aimez GeeksforGeeks et souhaitez contribuer, vous pouvez également écrire un article en utilisant écrire.geeksforgeeks.org ou envoyez votre article à [email protected]. Consultez votre article apparaissant sur la page principale de GeeksforGeeks et aidez les autres Geeks. Veuillez écrire des commentaires si vous trouvez quelque chose d'incorrect ou si vous souhaitez partager plus d'informations sur le sujet abordé ci-dessus.
