ПРЕСКАЧАНЕ НА ТЪРСЕНЕ

като Двоично търсене Jump Search е алгоритъм за търсене на сортирани масиви. Основната идея е да се проверяват по-малко елементи (от линейно търсене ) чрез прескачане напред с фиксирани стъпки или пропускане на някои елементи вместо търсене във всички елементи.
Да предположим например, че имаме масив arr[] с размер n и блок (за прескачане) с размер m. След това търсим в индексите arr[0] arr[m] arr[2m].....arr[km] и т.н. След като намерим интервала (arr[km] < 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

Какъв е оптималният размер на блока за пропускане?
В най-лошия случай трябва да направим n/m скокове и ако последната проверена стойност е по-голяма от елемента, който ще се търси, ние извършваме m-1 сравнения повече за линейно търсене. Следователно общият брой сравнения в най-лошия случай ще бъде ((n/m) + m-1). Стойността на функцията ((n/m) + m-1) ще бъде минимална, когато m = √n. Следователно най-добрият размер на стъпката е m = √ п.

Стъпки на алгоритъма

Jump Search е алгоритъм за намиране на конкретна стойност в сортиран масив чрез прескачане през определени стъпки в масива.
Стъпките се определят от sqrt на дължината на масива.
Ето алгоритъм стъпка по стъпка за преходно търсене:
Определете размера на стъпката m, като вземете sqrt от дължината на масива n.
Започнете от първия елемент на масива и прескочете m стъпки, докато стойността на тази позиция стане по-голяма от целевата стойност.
След като бъде намерена стойност, по-голяма от целта, извършете линейно търсене, започвайки от предишната стъпка, докато целта бъде намерена или стане ясно, че целта не е в масива.
Ако целта бъде намерена, върнете нейния индекс. Ако не, връща -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      < <     '  n  Number '      < <     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

Времева сложност: O(?n)
Помощно пространство: O(1)

Предимства на Jump Search:

По-добре от линейно търсене на масиви, където елементите са равномерно разпределени.
Прескачащото търсене има по-ниска времева сложност в сравнение с линейното търсене за големи масиви.
Броят стъпки, предприети при прескачащо търсене, е пропорционален на корен квадратен от размера на масива, което го прави по-ефективен за големи масиви.
По-лесно е за прилагане в сравнение с други алгоритми за търсене като двоично търсене или троично търсене.
Търсенето с прескачане работи добре за масиви, където елементите са подредени и равномерно разпределени, тъй като може да премине към по-близка позиция в масива с всяка итерация.

Важни точки:

Работи само със сортирани масиви.
Оптималният размер на блок за прескачане е (? n). Това прави времевата сложност на Jump Search O(? n).
Времевата сложност на Jump Search е между линейно търсене ((O(n)) и двоично търсене (O(Log n)).
Двоичното търсене е по-добро от Jump Search, но Jump Search има предимството, че преминаваме назад само веднъж (Binary Search може да изисква до O(Log n) скокове, като се има предвид ситуация, в която елементът, който трябва да се търси, е най-малкият елемент или просто по-голям от най-малкия). Така че в система, където двоичното търсене е скъпо, ние използваме Jump Search.

препратки:
https://en.wikipedia.org/wiki/Jump_search
Ако харесвате GeeksforGeeks и искате да допринесете, можете също да напишете статия, като използвате write.geeksforgeeks.org или изпратете статията си до [email protected]. Вижте вашата статия да се появява на главната страница на GeeksforGeeks и помогнете на други маниаци. Моля, пишете коментари, ако намерите нещо неправилно или искате да споделите повече информация относно темата, обсъдена по-горе.