ЈУМП СЕАРЦХ

Лике Бинарно претраживање Јумп Сеарцх је алгоритам за претраживање сортираних низова. Основна идеја је да се провери мање елемената (од линеарно претраживање ) скакањем унапред фиксним корацима или прескакањем неких елемената уместо претраживања свих елемената.
На пример, претпоставимо да имамо низ арр[] величине н и блок (који треба прескочити) величине м. Затим тражимо у индексима арр[0] арр[м] арр[2м].....арр[км] и тако даље. Када пронађемо интервал (арр[км]< x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Хајде да размотримо следећи низ: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Дужина низа је 16. Прескакање ће пронаћи вредност 55 са следећим корацима под претпоставком да је величина блока који треба прескочити 4.
КОРАК 1: Скок са индекса 0 на индекс 4;
КОРАК 2: Скок са индекса 4 на индекс 8;
КОРАК 3: Скок са индекса 8 на индекс 12;
КОРАК 4: Пошто је елемент са индексом 12 већи од 55, скочићемо корак уназад да бисмо дошли до индекса 8.
КОРАК 5: Извршите линеарну претрагу из индекса 8 да бисте добили елемент 55.

Учинак у поређењу са линеарном и бинарном претрагом:

Ако га упоредимо са линеарном и бинарном претрагом онда се испостави да је боље од линеарне претраге, али није боље од бинарне претраге.

Све већи редослед перформанси је:

линеарно претраживање < jump search < binary search

Која је оптимална величина блока коју треба прескочити?
У најгорем случају морамо да урадимо н/м скокове и ако је последња проверена вредност већа од елемента који треба да се тражи, вршимо м-1 поређења више за линеарну претрагу. Стога ће укупан број поређења у најгорем случају бити ((н/м) + м-1). Вредност функције ((н/м) + м-1) биће минимална када је м = √н. Стога је најбоља величина корака м = √ н.

Кораци алгоритма

Јумп Сеарцх је алгоритам за проналажење одређене вредности у сортираном низу скакањем кроз одређене кораке у низу.
Кораци су одређени скрт дужине низа.
Ево корак по корак алгоритма за претрагу скока:
Одредити величину корака м узимајући скрт дужине низа н.
Почните од првог елемента низа и прескачите м корака док вредност на тој позицији не буде већа од циљне вредности.
Када се пронађе вредност већа од циља, извршите линеарну претрагу почевши од претходног корака док се циљ не пронађе или док не буде јасно да циљ није у низу.
Ако је циљ пронађен, вратите његов индекс. Ако није, вратите -1 да бисте означили да циљ није пронађен у низу.

Пример 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; ?>

Излаз:

Number 55 is at index 10

Временска сложеност: О(?н)
Помоћни простор : О(1)

Предности Јумп Сеарцх:

Боље од линеарне претраге низова где су елементи равномерно распоређени.
Прескакање има мању временску сложеност у поређењу са линеарном претрагом за велике низове.
Број корака предузетих у претрази у скоку је пропорционалан квадратном корену величине низа што га чини ефикаснијим за велике низове.
Лакше је за имплементацију у поређењу са другим алгоритмима за претрагу као што су бинарна претрага или тернарна претрага.
Прескакање ради добро за низове у којима су елементи уредни и равномерно распоређени јер може скочити на ближу позицију у низу са сваком итерацијом.

Важне тачке:

Ради само са сортираним низовима.
Оптимална величина блока који треба прескочити је (? н). Ово чини временску сложеност Прескакања О(? н).
Временска сложеност скока претраге је између линеарне претраге ((О(н)) и бинарне претраге (О(Лог н)).
Бинарна претрага је боља од прескакања, али прескакање има предност у томе што се враћамо само једном (Бинарна претрага може захтевати до О(Лог н) скокова узмите у обзир ситуацију у којој је елемент који се тражи најмањи елемент или само већи од најмањег). Дакле, у систему где је бинарно претраживање скупо, користимо Јумп Сеарцх.

Референце:
хттпс://ен.википедиа.орг/вики/Јумп_сеарцх
Ако вам се свиђа ГеексфорГеекс и желите да допринесете, такође можете написати чланак користећи врите.геексфоргеекс.орг или пошаљите свој чланак на адресу ревиев-теам@геексфоргеекс.орг. Погледајте како се ваш чланак појављује на главној страници ГеексфорГеекс-а и помозите другим штреберцима. Молимо вас да напишете коментаре ако нађете нешто нетачно или желите да поделите више информација о теми о којој се расправљало изнад.