JUMP SEARCH

Pitää Binäärihaku Jump Search on lajiteltujen taulukoiden hakualgoritmi. Perusideana on tarkistaa vähemmän elementtejä (kuin lineaarinen haku ) hyppäämällä eteenpäin kiinteillä askelilla tai ohittamalla joitain elementtejä kaikkien elementtien etsimisen sijaan.
Oletetaan esimerkiksi, että meillä on taulukko arr[], jonka koko on n, ja lohko (hypättävä), jonka koko on m. Sitten etsitään hakemistoista arr[0] arr[m] arr[2m].....arr[km] ja niin edelleen. Kun olemme löytäneet intervallin (arr[km]< x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Tarkastellaan seuraavaa taulukkoa: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Taulukon pituus on 16. Hyppyhaku löytää arvon 55 seuraavilla vaiheilla olettaen, että hypättävä lohkokoko on 4.
VAIHE 1: Hyppää indeksistä 0 indeksiin 4;
VAIHE 2: Hyppää indeksistä 4 indeksiin 8;
VAIHE 3: Hyppää indeksistä 8 indeksiin 12;
VAIHE 4: Koska indeksin 12 elementti on suurempi kuin 55, hyppäämme askeleen taaksepäin päästäksemme indeksiin 8.
VAIHE 5: Suorita lineaarinen haku indeksistä 8 saadaksesi elementin 55.

Suorituskyky verrattuna lineaariseen ja binaarihakuun:

Jos vertaamme sitä lineaariseen ja binaarihakuun, niin se tulee ulos, niin se on parempi kuin lineaarinen haku, mutta ei parempi kuin binäärihaku.

Kasvava suoritusjärjestys on:

lineaarinen haku < jump search < binary search

Mikä on optimaalinen ohitettavan lohkon koko?
Pahimmassa tapauksessa joudumme tekemään n/m hyppyjä ja jos viimeksi tarkistettu arvo on suurempi kuin haettava elementti, suoritamme m-1 vertailuja enemmän lineaariselle haulle. Siksi vertailujen kokonaismäärä pahimmassa tapauksessa on ((n/m) + m-1). Funktion arvo ((n/m) + m-1) on pienin, kun m = √n. Siksi paras askelkoko on m = √ n.

Algoritmin vaiheet

Jump Search on algoritmi tietyn arvon löytämiseksi lajitetusta taulukosta hyppäämällä taulukon tiettyjen vaiheiden läpi.
Vaiheet määräytyvät taulukon pituuden sqrt:n mukaan.
Tässä on vaiheittainen algoritmi hyppyhakuun:
Määritä askelkoko m ottamalla taulukon n pituuden sqrt.
Aloita taulukon ensimmäisestä elementistä ja hyppää m askelta, kunnes arvo kyseisessä paikassa on suurempi kuin tavoitearvo.
Kun kohdetta suurempi arvo on löydetty, suorita lineaarinen haku alkaen edellisestä vaiheesta, kunnes kohde löytyy tai on selvää, että kohde ei ole taulukossa.
Jos kohde löytyy, palauta sen indeksi. Jos ei, palauta -1 osoittamaan, että kohdetta ei löydy taulukosta.

Esimerkki 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

#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# 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; ?>

Lähtö:

Number 55 is at index 10

Aika monimutkaisuus: O(?n)
Aputila: O(1)

Jump Searchin edut:

Parempi kuin lineaarinen haku taulukoille, joissa elementit ovat jakautuneet tasaisesti.
Hyppyhaulla on pienempi aikamonimutkaisuus verrattuna lineaariseen hakuun suurille taulukoille.
Hyppyhaun vaiheiden määrä on verrannollinen taulukon koon neliöjuureen, mikä tekee siitä tehokkaamman suurille taulukoille.
Se on helpompi toteuttaa verrattuna muihin hakualgoritmeihin, kuten binäärihakuun tai kolmihakuun.
Hyppyhaku toimii hyvin taulukoissa, joissa elementit ovat järjestyksessä ja tasaisesti jakautuneita, koska se voi hypätä lähempään kohtaan taulukossa jokaisen iteroinnin yhteydessä.

Tärkeitä kohtia:

Toimii vain lajiteltujen taulukoiden kanssa.
Hyppyttävän lohkon optimaalinen koko on (? n). Tämä tekee hyppyhaun aikamonimutkaisuuden O(? n).
Pikahaun aikamonimutkaisuus on lineaarihaun ((O(n)) ja binaarihaun (O(Log n)) välillä.
Binäärihaku on parempi kuin hyppyhaku, mutta hyppyhaulla on se etu, että kuljemme taaksepäin vain kerran (binäärihaku voi vaatia jopa O(Log n) hyppyä, kun otetaan huomioon tilanne, jossa haettava elementti on pienin elementti tai vain suurempi kuin pienin). Joten järjestelmässä, jossa binäärihaku on kallista, käytämme Jump Searchia.

Viitteet:
https://en.wikipedia.org/wiki/Jump_search
Jos pidät GeeksforGeeksistä ja haluat osallistua, voit myös kirjoittaa artikkelin käyttämällä write.geeksforgeeks.org tai lähetä artikkelisi osoitteeseen [email protected]. Katso artikkelisi ilmestyvän GeeksforGeeks-pääsivulle ja auta muita nörtejä. Kirjoita kommentteja, jos huomaat jotain väärin tai haluat jakaa lisätietoja yllä käsitellystä aiheesta.