جستجوی درون‌یابی در جاوا (Interpolation Search)

در این قسمت تیم کدگیت را با آموزش جستجوی درون‌یابی در جاوا همراهی کنید. ابتدای این آموزش جستجوی درونیابی را توضیح می‌دهیم سپس به پیاده‌سازی کد این الگوریتم می‌پردازیم. همچنین پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:

  1. متد static در جاوا
  2. حلقه while در جاوا
  3. آرایه در جاوا

جستجوی درون‌یابی

جستجوی درون یابی نوعی الگوریتم جستجو می‌باشد. این الگوریتم نسبت به جستجوی دودویی عملکرد بهتری دارد. بخصوص در مواقعی که مقادیر در یک آرایه مرتب (SORTED ARRAY)، به طور یکسان توزیع شده اند.

جستجوی دودویی برای بررسی به سراغ عنصر میانی مقادیر مراجعه می‌کند. از طرفی جستجوی درون یابی با توجه به مقدار کلیدی که در حال جستجوی آن می‌باشد به نقاط متفاوتی مراجعه می‌کند. یعنی اگر به فرض مقدار کلید به آخرین عنصر نزدیکتر باشد جستجوی درون یابی، جستجو را از سمت آخر شروع می‌کند.

برای یافتن نقطه مناسب جستجو از فرمول زیر استفاده می‌شود(در این آموزش به آن pos می‌گوییم):

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

متغیر lo اندیس شروع آرایه و متغیر hi اندیس پایان آرایه می‌باشد. X عنصر مورد جستجوی ما است.

الگوریتم جستجوی درون یابی به صورت زیر است:

  1. مقدار pos را با استفاده از فرمول بالا محاسبه کنید.
  2. درصورتی که عنصر درون خانه pos با کلید مورد جستجو مطابق بود اندیس را برگردانید.
  3. در صورتی که کلید از مقدار عنصر [pos] کمتر بود، زیرآرایه سمت چپ را بررسی کنید. در غیر این صورت زیرآرایه سمت راست را محاسبه کنید.
  4. تا زمانی که یک تطابق پیدا شود و یا آرایه میانی به صفر برسد ادامه دهید.

پیاده‌سازی جستجوی درون‌یابی در جاوا

برای پیاده سازی یک متد به نام interpolationSearch می‌نویسیم که در ورودی تابع خود مقدار x را دریافت می‌کند. سپس درون یک حلقه while الگوریتم را پیاده‌سازی می‌کنیم. ابتدا مقدار pos را درون هر دور از حلقه بدست آورده و در صورت یافتن عنصر مورد جستجو الگوریتم را پایان می‌دهیم. اگر عنصر x کوچکتر از خانه pos در آرایه باشد مقدار lo و hi را طوری تغییر می‌دهیم که زیرآرایه سمت چپ pos را جستجو کنیم و برعکس زیرآرایه سمت راست. در پایان اگر عنصر x درون آرایه نباشد مقدار -1 را بر‌می‌گردانیم.

کد این الگوریتم به صورت زیر می‌باشد:

خروجی کد بالا به صورت زیر است:

Element found at index 4

پسورد: www.codegate.ir

دسته : java, جاوا, ساختمان داده در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz