Pesquisa de salto
Como Pesquisa binária Jump Search é um algoritmo de busca para matrizes classificadas. A ideia básica é verificar menos elementos (do que pesquisa linear ) avançando em etapas fixas ou pulando alguns elementos em vez de pesquisar todos os elementos.
Por exemplo, suponha que temos um array arr[] de tamanho n e um bloco (a ser saltado) de tamanho m. Depois buscamos nos índices arr[0] arr[m] arr[2m].....arr[km] e assim por diante. Assim que encontrarmos o intervalo (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Vamos considerar a seguinte matriz: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). O comprimento da matriz é 16. A pesquisa Jump encontrará o valor 55 com as etapas a seguir assumindo que o tamanho do bloco a ser saltado é 4.
PASSO 1: Salte do índice 0 para o índice 4;
PASSO 2: Salte do índice 4 para o índice 8;
PASSO 3: Salte do índice 8 para o índice 12;
PASSO 4: Como o elemento no índice 12 é maior que 55, retrocederemos um passo para chegar ao índice 8.
PASSO 5: Execute uma pesquisa linear a partir do índice 8 para obter o elemento 55.
Desempenho em comparação com pesquisa linear e binária:
Se compararmos com a pesquisa linear e binária, então descobrimos que é melhor que a pesquisa linear, mas não melhor que a pesquisa binária.
A ordem crescente de desempenho é:
pesquisa linear < jump search < binary search
Qual é o tamanho ideal do bloco a ser ignorado?
Na pior das hipóteses temos que fazer saltos n/m e se o último valor verificado for maior que o elemento a ser pesquisado realizamos mais comparações m-1 para pesquisa linear. Portanto o número total de comparações no pior caso será ((n/m) + m-1). O valor da função ((n/m) + m-1) será mínimo quando m = √n. Portanto, o melhor tamanho de passo é m = √ n.
Etapas do algoritmo
- Jump Search é um algoritmo para encontrar um valor específico em uma matriz classificada, saltando por certas etapas da matriz.
- As etapas são determinadas pelo sqrt do comprimento da matriz.
- Aqui está um algoritmo passo a passo para a pesquisa de salto:
- Determine o tamanho do passo m tomando o sqrt do comprimento da matriz n.
- Comece no primeiro elemento da matriz e pule m passos até que o valor naquela posição seja maior que o valor alvo.
Assim que um valor maior que o alvo for encontrado, execute uma pesquisa linear começando na etapa anterior até que o alvo seja encontrado ou fique claro que o alvo não está na matriz.
Se o alvo for encontrado, retorne seu índice. Caso contrário, retorne -1 para indicar que o destino não foi encontrado no array.
Exemplo 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 ; ?>
Saída:
Number 55 is at index 10
Complexidade de tempo: O (?n)
Espaço Auxiliar: O(1)Vantagens da pesquisa de salto:
- Melhor do que uma busca linear por matrizes onde os elementos estão distribuídos uniformemente.
- A pesquisa de salto tem uma complexidade de tempo menor em comparação com uma pesquisa linear para grandes matrizes.
- O número de etapas executadas na pesquisa saltada é proporcional à raiz quadrada do tamanho do array, tornando-a mais eficiente para arrays grandes.
- É mais fácil de implementar em comparação com outros algoritmos de pesquisa, como pesquisa binária ou pesquisa ternária.
- A pesquisa por salto funciona bem para arrays onde os elementos estão em ordem e distribuídos uniformemente, pois pode saltar para uma posição mais próxima no array a cada iteração.
Pontos importantes:
- Funciona apenas com matrizes classificadas.
- O tamanho ideal de um bloco a ser saltado é (? n). Isso torna a complexidade de tempo do Jump Search O (? n).
- A complexidade de tempo da Jump Search está entre a Pesquisa Linear ((O(n)) e a Pesquisa Binária (O(Log n)).
- A pesquisa binária é melhor que a pesquisa por salto, mas a pesquisa por salto tem a vantagem de retroceder apenas uma vez (a pesquisa binária pode exigir até O (Log n) saltos, considerando uma situação em que o elemento a ser pesquisado é o menor elemento ou apenas maior que o menor). Portanto, em um sistema onde a pesquisa binária é cara, usamos o Jump Search.
Referências:
https://en.wikipedia.org/wiki/Jump_search
Se você gosta de GeeksforGeeks e gostaria de contribuir, você também pode escrever um artigo usando escreva.geeksforgeeks.org ou envie seu artigo para [email protected]. Veja seu artigo que aparece na página principal do GeeksforGeeks e ajude outros Geeks. Escreva comentários se encontrar algo incorreto ou quiser compartilhar mais informações sobre o tópico discutido acima.
