logo

TechCodeview

Pārlēkt meklēšanu

Patīk Binārā meklēšana Jump Search ir sakārtotu masīvu meklēšanas algoritms. Pamatideja ir pārbaudīt mazāk elementu (nekā lineārā meklēšana ), pārlecot uz priekšu pa fiksētiem soļiem vai izlaižot dažus elementus visu elementu meklēšanas vietā.
Piemēram, pieņemsim, ka mums ir masīvs arr[], kura izmērs ir n, un bloks (jāpārlec) ar izmēru m. Tad meklējam indeksos arr[0] arr[m] arr[2m].....arr[km] un tā tālāk. Kad esam atraduši intervālu (arr[km]< x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Apskatīsim šādu masīvu: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Masīva garums ir 16. Pārlēkšanas meklēšana atradīs vērtību 55, veicot šādas darbības, pieņemot, ka pārlecamā bloka izmērs ir 4. 
1. SOLIS: pārejiet no indeksa 0 uz indeksu 4; 
2. SOLIS: pārejiet no indeksa 4 uz indeksu 8; 
3. SOLIS: pārejiet no indeksa 8 uz indeksu 12; 
4. SOLIS. Tā kā elements indeksā 12 ir lielāks par 55, mēs pāriesim soli atpakaļ, lai nonāktu pie indeksa 8. 
5. SOLIS. Veiciet lineāro meklēšanu no indeksa 8, lai iegūtu elementu 55.

Veiktspēja salīdzinājumā ar lineāro un bināro meklēšanu:

Ja salīdzinām to ar lineāro un bināro meklēšanu, tad tā ir labāka par lineāro meklēšanu, bet ne labāka par bināro meklēšanu.



Pieaugošā izpildes secība ir:

lineārā meklēšana  <  jump search  <  binary search


Kāds ir optimālais bloka izmērs, ko izlaist?  
Sliktākajā gadījumā ir jāveic n/m lēcieni un, ja pēdējā pārbaudītā vērtība ir lielāka par meklējamo elementu, lineārajai meklēšanai vairāk veicam m-1 salīdzinājumus. Tāpēc kopējais salīdzinājumu skaits sliktākajā gadījumā būs ((n/m) + m-1). Funkcijas vērtība ((n/m) + m-1) būs minimāla, ja m = √n. Tāpēc labākais pakāpiena izmērs ir m = √ n.



Algoritma soļi

  • Pārlēkta meklēšana ir algoritms noteiktas vērtības atrašanai sakārtotā masīvā, pārejot cauri noteiktiem soļiem masīvā.
  • Soļus nosaka masīva garuma kvadrāts. 
  • Šeit ir soli pa solim algoritms lēciena meklēšanai:
  • Nosakiet soļa lielumu m, ņemot masīva n garuma kvadrātu.
  • Sāciet ar pirmo masīva elementu un pārejiet m soļus, līdz vērtība šajā pozīcijā ir lielāka par mērķa vērtību.
    Kad ir atrasta vērtība, kas ir lielāka par mērķi, veiciet lineāro meklēšanu, sākot no iepriekšējās darbības, līdz tiek atrasts mērķis vai ir skaidrs, ka mērķis nav masīvā.
    Ja mērķis ir atrasts, atgrieziet tā indeksu. Ja ne, atgrieziet -1, lai norādītu, ka mērķis masīvā nav atrasts. 

1. piemērs:

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

Izvade: 
 

Number 55 is at index 10


Laika sarežģītība: O(?n) 
Palīgtelpa: O(1)

Pārlēktās meklēšanas priekšrocības:

  1. Labāk nekā lineāra masīvu meklēšana, kur elementi ir vienmērīgi sadalīti.
  2. Pārlēciena meklēšanai ir mazāka laika sarežģītība, salīdzinot ar lineāro meklēšanu lieliem masīviem.
  3. Pārlēkšanas meklēšanā veikto darbību skaits ir proporcionāls masīva lieluma kvadrātsaknei, padarot to efektīvāku lieliem masīviem.
  4. To ir vieglāk ieviest salīdzinājumā ar citiem meklēšanas algoritmiem, piemēram, bināro meklēšanu vai trīskāršo meklēšanu.
  5. Pārlēkšanas meklēšana labi darbojas masīviem, kur elementi ir sakārtoti un vienmērīgi sadalīti, jo tā var pāriet uz tuvāku pozīciju masīvā ar katru iterāciju.

Svarīgi punkti:  
 



  • Darbojas tikai ar sakārtotiem masīviem.
  • Optimālais pārlecamā bloka izmērs ir (? n). Tas padara Jump Search O(? n) laika sarežģītību.
  • Jump Search laika sarežģītība ir starp lineāro meklēšanu ((O(n)) un bināro meklēšanu (O(Log n)).
  • Binārā meklēšana ir labāka par lēcienu meklēšanu, taču lēciena meklēšanai ir tā priekšrocība, ka mēs šķērsojam atpakaļ tikai vienu reizi (binārā meklēšana var prasīt līdz pat O(Log n), ņemot vērā situāciju, kad meklējamais elements ir mazākais elements vai tikai lielāks par mazāko). Tātad sistēmā, kurā binārā meklēšana ir dārga, mēs izmantojam Jump Search.


Atsauces:  
https://en.wikipedia.org/wiki/Jump_search
Ja jums patīk GeeksforGeeks un vēlaties sniegt savu ieguldījumu, varat arī uzrakstīt rakstu, izmantojot write.geeksforgeeks.org vai nosūtiet savu rakstu uz [email protected]. Skatiet savu rakstu GeeksforGeeks galvenajā lapā un palīdziet citiem Geeks.Lūdzu, rakstiet komentārus, ja atrodat kaut ko nepareizu vai vēlaties dalīties ar plašāku informāciju par iepriekš apspriesto tēmu.