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

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

1. آشنایی با if
2. آشنایی با while
3. آشنایی با آرایه
4. آشنایی با توابع

جستجوی پرشی

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

فرض کنید که یک آرایه [] به اندازه 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 دوم جستجوی خطی را انجام می‌دهیم و در آخر اندیس خانه مورد جستجو را بر‌می‌گردانیم. کد این الگوریتم به صورت زیر می‌باشد:

int jumpSearch(int arr[], int x, int n) {
     int step = sqrt(n); 
     int prev = 0; 
     while (arr[min(step, n) - 1] < x) { 
          prev = step; 
          step += sqrt(n); 
          if (prev >= n) 
              return -1; 
     } 
     while (arr[prev] < x) { 
          prev++; 
          if (prev == min(step, n)) 
              return -1; 
     } 
     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); 
     cout << "\nNumber " << x << " is at index " << index; 
     return 0; 
 }