در این قسمت تیم کدگیت را با آموزش جستجوی درونیابی در جاوا همراهی کنید. ابتدای این آموزش جستجوی درونیابی را توضیح می‌دهیم سپس به پیاده‌سازی کد این الگوریتم می‌پردازیم. همچنین پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:
جستجوی درونیابی
جستجوی درون یابی نوعی الگوریتم جستجو می‌باشد. این الگوریتم نسبت به جستجوی دودویی عملکرد بهتری دارد. بخصوص در مواقعی که مقادیر در یک آرایه مرتب (SORTED ARRAY)، به طور یکسان توزیع شده اند.
جستجوی دودویی برای بررسی به سراغ عنصر میانی مقادیر مراجعه می‌کند. از طرفی جستجوی درون یابی با توجه به مقدار کلیدی که در حال جستجوی آن می‌باشد به نقاط متفاوتی مراجعه می‌کند. یعنی اگر به فرض مقدار کلید به آخرین عنصر نزدیکتر باشد جستجوی درون یابی، جستجو را از سمت آخر شروع می‌کند.
برای یافتن نقطه مناسب جستجو از فرمول زیر استفاده می‌شود(در این آموزش به آن pos می‌گوییم):
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]
متغیر lo اندیس شروع آرایه و متغیر hi اندیس پایان آرایه می‌باشد. X عنصر مورد جستجوی ما است.
الگوریتم جستجوی درون یابی به صورت زیر است:
- مقدار pos را با استفاده از فرمول بالا محاسبه کنید.
- درصورتی که عنصر درون خانه pos با کلید مورد جستجو مطابق بود اندیس را برگردانید.
- در صورتی که کلید از مقدار عنصر [pos] کمتر بود، زیرآرایه سمت چپ را بررسی کنید. در غیر این صورت زیرآرایه سمت راست را محاسبه کنید.
- تا زمانی که یک تطابق پیدا شود و یا آرایه میانی به صفر برسد ادامه دهید.
پیاده‌سازی جستجوی درونیابی در جاوا
برای پیاده سازی یک متد به نام interpolationSearch می‌نویسیم که در ورودی تابع خود مقدار x را دریافت می‌کند. سپس درون یک حلقه while الگوریتم را پیاده‌سازی می‌کنیم. ابتدا مقدار pos را درون هر دور از حلقه بدست آورده و در صورت یافتن عنصر مورد جستجو الگوریتم را پایان می‌دهیم. اگر عنصر x کوچکتر از خانه pos در آرایه باشد مقدار lo و hi را طوری تغییر می‌دهیم که زیرآرایه سمت چپ pos را جستجو کنیم و برعکس زیرآرایه سمت راست. در پایان اگر عنصر x درون آرایه نباشد مقدار -1 را بر‌می‌گردانیم.
کد این الگوریتم به صورت زیر می‌باشد:
public class interpolation_Search {
static int arr[] = new int[] { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
static int interpolationSearch(int x) {
// Find indexes of two corners
int lo = 0, hi = (arr.length - 1);
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
int pos = lo + (((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));
// Condition of target found
if (arr[pos] == x)
return pos;
// If x is larger, x is in upper part
if (arr[pos] < x)
lo = pos + 1;
// If x is smaller, x is in the lower part
else
hi = pos - 1;
}
return -1;
}
public static void main(String[] args) {
int x = 18; // Element to be searched
int index = interpolationSearch(x);
// If element was found
if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found.");
}
}
خروجی کد بالا به صورت زیر است:
Element found at index 4
