جستجوی پرشی

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

توضیحات

این الگوریتم با چک کردن همه آیتم های L_km، جایی که 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
• Paul E. Black, jump search at the مؤسسه ملی فناوری و استانداردها Dictionary of Algorithms and Data Structures.
• Ben Shneiderman، Jump Searching: A Fast Sequential Search Technique، CACM، ۲۱(۱۰):۸۳۱-۸۳۴، October ۱۹۷۸.