logo

TechCodeview

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 << 'nNumber ' << 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:

  1. Melhor do que uma busca linear por matrizes onde os elementos estão distribuídos uniformemente.
  2. A pesquisa de salto tem uma complexidade de tempo menor em comparação com uma pesquisa linear para grandes matrizes.
  3. O número de etapas executadas na pesquisa saltada é proporcional à raiz quadrada do tamanho do array, tornando-a mais eficiente para arrays grandes.
  4. É mais fácil de implementar em comparação com outros algoritmos de pesquisa, como pesquisa binária ou pesquisa ternária.
  5. 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.