الگوریتم جستجوی درونیابی (Interpolation Search)

  • چهارشنبه ۲۴ مهر ۱۳۹۸
  • بازدید ۷۹ نفر

interpolation search algorithm 7303 تصویر

الگوریتم جستجوی درونیابی (Interpolation Search)

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

مسئله

با توجه به آرایه مرتب داده شده (arr[])، تابعی بنویسید که عنصر x را در آرایه جستجو کند.

حل

الگوریتم جستجوی خطی، عنصر مورد نظر با پیچدگی زمانی O(n)، جستجوی پرشی با پیچدگی زمانی O(√ n) و جستجوی باینری با پیچدگی زمانی O(Log n) پیدا می کند.

جستجوی درونیابی، نوع بهبود یافته الگوریتم جستجوی باینری برای نمونه هایی است که در آن ها مقادیر آرایه مرتب و به طور یکنواخت توزیع شده اند. در جستحوی باینری همیشه جستجو از وسط مجموعه شروع می شود، اما در این الگوریتم ممکن است بر اساس مقدار مورد نظر (مقدار key)، جستجو از اندیس دیگری شروع شود.

برای پیدا کردن موقعیتی که جستجو باید از آن شروع شود، از فرمول زیر استفاده می کنیم:

  • گام اول: در یک حلقه مقدار pos را با استفاده از فرمول فوق پیدا می کنیم.
  • گام دوم: اگر مقدار arr[pos] برابر با مقدار مورد نظر بود، اندیس آن را باز میگردانیم (همان pos).
  • گام سوم: اگر مقدار مورد نظر کمتر از arr[pos] بود، مقدار pos را برای زیر آرایه سمت چپ محاسبه می کنیم. اگر بزرگتر بود، مقدار pos را برای زیر آرایه سمت راست محاسبه می کنیم.
  • گام چهارم: این کار تا زمان رسیدن به عنصر مورد نظر یا به اتمام رسیدن آرایه، ادامه می یابد.

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

امتحان کنید

خروجی:

نکات

  • پیچیدگی زمانی الگوریتم Interpolation Search در صورتی که عناصر به طور یکنواخت توزیع شده باشند، برابر با O (log log n)) و در بدترین حالت هم برابر با O(n) است.
  • فضای موقت برابر با O(1) است.
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

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