קפיצה חיפוש

כְּמוֹ חיפוש בינארי 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.
התחל באלמנט הראשון של המערך וקפוץ מ' שלבים עד שהערך במיקום זה גדול מערך היעד.
ברגע שנמצא ערך גדול מהמטרה בצעו חיפוש ליניארי החל מהשלב הקודם עד למציאת המטרה או שברור שהיעד לא נמצא במערך.
אם היעד נמצא החזר את המדד שלו. אם לא החזירו -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 יש את היתרון שאנחנו עוברים אחורה רק פעם אחת (חיפוש בינארי עשוי לדרוש קפיצות של עד O(Log n) קחו בחשבון מצב שבו האלמנט שיש לחפש הוא האלמנט הקטן ביותר או פשוט גדול מהקטן ביותר). אז במערכת שבה חיפוש בינארי יקר אנו משתמשים ב-Jump Search.

הפניות:
https://en.wikipedia.org/wiki/Jump_search
אם אתה אוהב GeeksforGeeks ותרצה לתרום אתה יכול גם לכתוב מאמר באמצעות write.geeksforgeeks.org או שלח את המאמר שלך לכתובת [email protected]. ראה את המאמר שלך מופיע בעמוד הראשי של GeeksforGeeks ועזור לגיקים אחרים. אנא כתוב הערות אם אתה מוצא משהו שגוי או שאתה רוצה לשתף מידע נוסף על הנושא שנדון לעיל.