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

jump search algorithm 7277 تصویر

الگوریتم جستجوی پرشی (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 است.

امتحان کنید

خروجی:

نکات مهم

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

هیچ نظری ثبت نشده است