جستجوی پرشی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

جستجوی پرشی (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
    abbb + ⌊√n
    if an then
      return nothing
  while La <s do
    aa + 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
       {
   {

جستارهای وابسته[ویرایش]

منابع[ویرایش]