جستجوی پرشی در جاوا (Jump Search in Java)

در این قسمت تیم کدگیت را با آموزش جستجوی پرشی در جاوا همراهی کنید. در ابتدا طبق روال آموزش‌های گذشته، توضیح کوتاهی در مورد جستجوی پرشی خواهیم داد و سپس با ذکر مثالی ساده الگوریتم جستجوی پرشی در جاوا را پیاده‌سازی خواهیم کرد. همچنین پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:

1. آشنایی با متد Static در جاوا
2. آشنایی با while در جاوا
3. آشنایی با آرایه در جاوا

جستجوی پرشی

همانند جستجوی دودویی، جستجوی پرشی نوعی الگوریتم جستجو برای آرایه های مرتب می‌باشد. اساس این الگوریتم بررسی تعداد کمتری از عنصرها ( کمتر از جستجوی خطی) به وسیله گام های ثابت یا رد کردن برخی عنصرها با پرش رو به جلو می باشد، به جای اینکه تمامی عنصرها را چک کنیم.

فرض کنید که یک آرایه [] به اندازه n وبلوکی( که ازش میپریم) به اندازه m داریم. حالا در فهرست های [0],[m],[2m],…[km] و … به جستجو می‌پردازیم. به محض اینکه فاصله ( [km] < x < [(k+1)m] ) را پیدا کردیم، عملیات جستجوی خطی را در فهرست   km  تا هنگامی که  عنصر 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 به 16؛
4. از آنجایی که عنصر اندیس 16 بزرگتر از 55 می‌باشد یک گام به عقب برمی‌گردیم تا به اندیس 9 برسیم.
5. از اندیس 9 جستجوی خطی را آغاز می‌کنیم تا به مقدار 55 برسیم.

حال سوال اینجاست مناسب ترین اندازه ای که یک بلوک جهت پرش می‌تواند داشته باشد چقدر است؟ از طریق ریاضی بهترین سایز بلوک n√ می‌باشد که در این آموزش به اثبات آن نمی‌پردازیم.

پیاده‌سازی جستجوی پرشی در جاوا

برای پیاده‌سازی جستجوی پرشی در جاوا یک متد به نام JumpSearch می‌نویسیم. با تعیین بلاک آرایه (متغیر Step در کد) به جستجوی [0],[m],[2m],…[km] که در قسمت قبل توضیح دادیم، می‌پردازیم (While اول در کد). در While دوم جستجوی خطی را انجام می‌دهیم و در آخر اندیس خانه مورد جستجو را بر‌می‌گردانیم. کد این الگوریتم به صورت زیر می‌باشد:

 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;

          while (arr[Math.min(step, n) - 1] < x) {

              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("Number " + x + " is at index " + index);

     }