جستجوی پرشی

جستجوی پرشی (block search یا jump search) در علم کامپیوتر٬ نام یک الگوریتم برای پیدا کردن یک کلید در یک آرایه مرتب است.

توضیحات 
این الگوریتم با چک کردن همه آیتم های Lkm، جایی که l آرایه است و k عضو اعداد طبیعی و m اندازه بلوکی هست که در آن کلید را جستجو میکند و این الگوریتم ادامه میدهد این جستجو را تا زمانی که یک آیتم پیدا شود که از کلید جستجو بزرگتر باشد. در آن صورت از یک مرحله قبلش به اندازه m یکی یکی چک میکند و در صورت وجود کلید آن را پیدا میکند.

مقدار بهینه m رادیکال n است، جایی که n اندازه آرایه l است. در هر دو مرحله الگوریتم به اندازه n√ پیش میرود پس این الگوریتم در (O(√n اجرا میشود که این الگوریتم از الگوریتم خطی بهتر و از الگوریتم دو دویی بدتر است. اما مزیت این الگوریتم به الگوریتم دودویی این است که در این الگوریتم فقط یک بار به عقب بر میگردد ولی در الگوریتم دودویی میتواند تا log n بار به عقب برگردد و این در مواقعی که برگشت به عقب مؤثر تر است از به جلو پیش رفتن خیلی اهمیت دارد.

کد سودو 
 الگویتم جسنجو پرشی
   ورودی: یک لیست مرتب L, که طول آن آرایه n و کلید مورد نظر s است.
   خروجی: محل قرار گرفتن s در L, یا هیچی اگر s موجود نباشد در L.

   a ← 0
   ⌋b ← ⌊√n

   while Lmin(b,n)-1 <s do
     a ← b
     ⌋b ← b + ⌊√n
     if a ≥ n then
       return nothing

   while La <s do
     a ← a + 1
     (if a = min(b,n
       return nothing

   if La = s then
     return a
   else
     return nothing

کد به زبان C 
//اجرا میشود این الگوریتم برای آرایه "arr[]" به طول "len" برای یافتن کلید "key".
    }(int jumpsearch(int arr[], int len, int key
        ;int a = 0
        ;((int b = (int)floor(sqrt(len
        
      }(while (arr[(b <len ? b : len)-1] <key
            ;a = b
            ;((b = b + (int)floor(sqrt(len
            }(if (a>= len
                ;return -1
           {
        {
        
        }(while (arr[a] <key
            ;++a
            }((if (a == (b <len ? b : len
                ;return -1
            {
        {
        
        }(if (arr[a] == key
            ;return a
        } else {
            ;return -1
        {
    {

جستارهای وابسته 
 لیست پرشی
 جستجو الحاقی
 جستجو خطی - اجرا میشود در زمان O(n)، فقط به جلو پیش میرود.
 جستجو دودویی - اجرا میشود در زمان O(log n)، به جلو و عقب پیش میرود.

منابع 

 http://en.wikipedia.org/wiki/Jump_search
 
 Ben Shneiderman، Jump Searching: A Fast Sequential Search Technique، CACM، ۲۱(۱۰):۸۳۱-۸۳۴، October ۱۹۷۸.

الگوریتم‌های جستجو
مقاله‌های ایجاد شده توسط ایجادگر