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

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

الگوریتم جستجوی پرشی (Jump Search) یا Block Search مانند الگوریتم جستجوی باینری، فقط برای جستجو در مجموعه های مرتب شده، مورد استفاده قرار می گرد. روش کار الگوریتم جستجوی پرشی به این شکل است که آرایه را بر اساس طول آن به چند بلوک تقسیم می کند و آخرین عنصر هر بلوک را با مقدار مورد نظر مقایسه می کند. اگر مقدار آخرین عنصر بلوک جاری از مقدار مورد نظر بزرگتر باشد، جستجو از بلوک بعدی ادامه می یابد. اما اگر مقدار آخرین عنصر بلوک جاری از مقدار مورد نظر کوچکتر باشد، یک بلوک به عقب باز میگردیم و جستجو را در آن بلوک ادامه می دهیم.

مثال

برای نمونه فرض کنید ما یک آرایه به طول n و اندازه بلوک m داریم. جستجو از اندیس های arr[0]، arr[m]، arr[2m]، … arr[km] ادامه می یابد. هنگامی که مشخص شد عنصر مورد نظر در کدام بلوک قرار دارد (arr[km] < x < arr[(k+1)m])، آن بلوک را با استفاده از الگوریتم جستجوی خطی (Linear Search) جستجو می کنیم.

آرایه مرتب (۰, ۱, ۱, ۲, ۳, ۵, ۸, ۱۳, ۲۱, ۳۴, ۵۵, ۸۹, ۱۴۴, ۲۳۳, ۳۷۷, ۶۱۰) را در نظر بگیرید. طول این آرایه ۱۶ است و عنصر مورد نظر ما برای جستجو مقدار ۵۵ است. فرض کنید طول هر بلوک ۴ است:

• گام اول: پرش از اندیس ۰ به اندیس ۴
• گام دوم: پرش از اندیس ۴ به اندیس ۸
• گام سوم: پرش از اندیس ۸ به اندیس ۱۲
• گام چهارم: چون مقدار عنصر موجود در اندیس ۱۲ از مقدار مورد نظر ما (۵۵) بیشتر است، پس یک بلوک به عقب باز میگردیم.
• گام پنجم: از اندیس ۸ یک جستجوی خطی را انجام می دهیم تا عنصر مورد نظر را پیدا کنیم.

اندازه بلوک های جستجو

در بدترین حالت ما باید n/m پرش انجام دهیم و اگر  آخرین مقدار چک شده بزرگتر از عنصر مورد نظر باشد، باید m-1 مقایسه را انجام دهیم. بنابراین تعداد مقایسه ها در بدترین حالت برابر با ((n/m) + m-1) خواهد بود. اگر مقدار m = √n باشد، تابع ((n/m) + m-1) کمترین مقدار را خواهد داشت. در نتیجه بهترین حالت برای الگوریتم جستجوی پرشی، m = √n است.

// C++ program to implement Jump Search
#include <bits/stdc++.h>
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;
}

امتحان کنید

خروجی:

Number 55 is at index 10

نکات مهم

• پیچیدگی زمانی این الگوریتم برابر با O(√n) است.
• فقط بر روی آرایه های مرتب کار می کند.
• طول بلوک ها به صورت √n مشخص می شود.
• پیچیدگی زمانی این الگوریتم بین الگوریتم های Linear Search و Binary Search است.
• جستجوی پرشی بهتر از جستجوی خطی و بدتر از جستجوی باینری است.

نوشته الگوریتم جستجوی پرشی (Jump Search) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.