الگوریتم جستجوی نمایی (Exponential Search)

exponential search algorithm 7305 تصویر

الگوریتم جستجوی نمایی (Exponential Search)

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

جستجوی نمایی شامل مراحل زیر است:

  • پیدا کردن رنجی که عنصر مورد نظر در آن قرار دارد.
  • انجام جستجوی باینری بر روی رنج پیدا شده.

چگونگه رنجی که عنصر مورد نظر ممکن است در آن باشد را پیدا کنیم؟

روش کار به این شکل است که ابتدا از یک زیر آرایه به طول ۱ شروع می کنیم و عنصر مورد نظر را با آخرین عنصر آن مقایسه می کنیم، سپس طول آرایه ۲، ۴ و … همینطور اضافه می شود تا زمانی که آخرین عنصر زیر آرایه از مقدار مورد جستجوی ما بزرگتر نباشد. زمانی که اندیس i را پیدا کردیم، می داینم که عنصر مورد نظر باید بین i/2 و i باشد.

پیاده سازی الگوریتم جستجوی نمایی با استفاده از زبان C++:

امتحان کنید

خروجی:

نکات

  • پیچیدگی زمانی این الگوریتم برابر با O(Log n) است.
  • فضای موقت در جستجوی باینری فوق برابر با O(Log n) زیرا به صورت بازگشتی پیاده سازی شده است. در صورتی که به صورت عادی پیاده سازی شود، برابر با O(1) خواهد بود.

کاربرد

  • جستجوی نمایی برای جستجوهای محدود نشده، مثلا آرایه ای که اندازه نامحدود دارد، مفید است.
  • جستجوی نمایی برای جستجو در آرایه های محدود و همچنین زمانی که عنصر مورد نظر به عنصر اول نزدیکتر باشد، بهتر از جستجوی باینری کار می کند.
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

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