Salt de cerca
M'agrada Cerca binària Jump Search és un algorisme de cerca per a matrius ordenades. La idea bàsica és comprovar menys elements (que cerca lineal ) saltant endavant amb passos fixos o saltant alguns elements en lloc de cercar tots els elements.
Per exemple, suposem que tenim una matriu arr[] de mida n i un bloc (per saltar) de mida m. Després busquem als índexs arr[0] arr[m] arr[2m].....arr[km] i així successivament. Un cop trobem l'interval (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Considerem la matriu següent: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). La longitud de la matriu és 16. La cerca Jump trobarà el valor de 55 amb els passos següents assumint que la mida del bloc que s'ha de saltar és 4.
PAS 1: Saltar de l'índex 0 a l'índex 4;
PAS 2: Saltar de l'índex 4 a l'índex 8;
PAS 3: saltar de l'índex 8 a l'índex 12;
PAS 4: com que l'element de l'índex 12 és superior a 55, farem un salt enrere per arribar a l'índex 8.
PAS 5: feu una cerca lineal des de l'índex 8 per obtenir l'element 55.
Rendiment en comparació amb la cerca lineal i binària:
Si ho comparem amb la cerca lineal i binària, llavors surt, és millor que la cerca lineal però no millor que la cerca binària.
L'ordre creixent de rendiment és:
cerca lineal < jump search < binary search
Quina és la mida de bloc òptima per saltar-se?
En el pitjor dels casos hem de fer n/m salts i si l'últim valor comprovat és superior a l'element a cercar fem m-1 comparacions més per a la cerca lineal. Per tant, el nombre total de comparacions en el pitjor dels casos serà ((n/m) + m-1). El valor de la funció ((n/m) + m-1) serà mínim quan m = √n. Per tant, la millor mida del pas és m = √ n.
Passos de l'algorisme
- Jump Search és un algorisme per trobar un valor específic en una matriu ordenada saltant per determinats passos de la matriu.
- Els passos estan determinats pel quadrat quadrat de la longitud de la matriu.
- Aquí teniu un algorisme pas a pas per a la cerca de salt:
- Determineu la mida del pas m prenent el quadrat quadrat de la longitud de la matriu n.
- Comença des del primer element de la matriu i salta m passos fins que el valor en aquesta posició sigui superior al valor objectiu.
Un cop trobat un valor superior a l'objectiu, feu una cerca lineal a partir del pas anterior fins que es trobi l'objectiu o quedi clar que l'objectiu no es troba a la matriu.
Si es troba l'objectiu, retorna el seu índex. Si no, torneu -1 per indicar que l'objectiu no s'ha trobat a la matriu.
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 ; ?>
Sortida:
Number 55 is at index 10
Complexitat temporal: O(?n)
Espai auxiliar: O(1)Avantatges de Jump Search:
- Millor que una cerca lineal de matrius on els elements es distribueixen uniformement.
- La cerca de salt té una complexitat temporal més baixa en comparació amb una cerca lineal per a matrius grans.
- El nombre de passos realitzats en la cerca de salt és proporcional a l'arrel quadrada de la mida de la matriu, fent-la més eficient per a matrius grans.
- És més fàcil d'implementar en comparació amb altres algorismes de cerca com la cerca binària o la cerca ternària.
- La cerca de salt funciona bé per a matrius on els elements estan en ordre i distribuïts uniformement, ja que pot saltar a una posició més propera a la matriu amb cada iteració.
Punts importants:
- Només funciona amb matrius ordenades.
- La mida òptima d'un bloc a saltar és (? n). Això fa que la complexitat temporal de Jump Search sigui O(? n).
- La complexitat temporal de Jump Search es troba entre la cerca lineal ((O(n)) i la cerca binària (O(Log n)).
- La cerca binària és millor que Jump Search, però Jump Search té l'avantatge que només retrocedim una vegada (la cerca binària pot requerir fins a O(Log n) salts, considerant una situació en què l'element que s'ha de cercar és l'element més petit o només més gran que el més petit). Per tant, en un sistema on la cerca binària és costosa, fem servir Jump Search.
Referències:
https://en.wikipedia.org/wiki/Jump_search
Si t'agrada GeeksforGeeks i vols contribuir també pots escriure un article utilitzant write.geeksforgeeks.org o envia el teu article a [email protected]. Vegeu el vostre article que apareix a la pàgina principal de GeeksforGeeks i ajudeu altres Geeks. Si us plau, escriviu comentaris si trobeu alguna cosa incorrecta o voleu compartir més informació sobre el tema tractat anteriorment.
