در این قسمت تیم کدگیت را با آموزش جستجوی درونیابی در سی پلاس پلاس همراهی کنید. ابتدای این آموزش جستجوی درونیابی را توضیح میدهیم سپس به پیادهسازی کد این الگوریتم میپردازیم. همچنین پیشنهاد میکنیم قبل از مطالعه این جلسه، آموزشهای زیر را مطالعه کنید:
جستجوی درونیابی
جستجوی درون یابی نوعی الگوریتم جستجو میباشد. این الگوریتم نسبت به جستجوی دودویی عملکرد بهتری دارد. بخصوص در مواقعی که مقادیر در یک آرایه مرتب (SORTED ARRAY) ، به طور یکسان توزیع شده اند.
جستجوی دودویی برای بررسی به سراغ عنصر میانی مقادیر مراجعه میکند. از طرفی جستجوی درون یابی با توجه به مقدار کلیدی که در حال جستجوی آن میباشد به نقاط متفاوتی مراجعه میکند. یعنی اگر به فرض مقدار کلید به آخرین عنصر نزدیکتر باشد جستجوی درون یابی، جستجو را از سمت آخر شروع میکند.
برای یافتن نقطه مناسب جستجو از فرمول زیر استفاده میشود(در این آموزش به آن pos میگوییم):
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]
متغیر low اندیس شروع آرایه و متغیر hi اندیس پایان آرایه میباشد. X عنصر مورد جستجوی ما است.
الگوریتم جستجوی درون یابی به صورت زیر است:
- مقدار pos را با استفاده از فرمول بالا محاسبه کنید:
- درصورتی که عنصر درون خانه pos با کلید مورد جستجو مطابق بود اندیس را برگردانید.
- در صورتی که کلید از مقدار عنصر [pos] کمتر بود، زیرآرایه سمت چپ را بررسی کنید. در غیر این صورت زیرآرایه سمت راست را محاسبه کنید.
- تا زمانی که یک تطابق پیدا شود و یا آرایه میانی به صفر برسد ادامه دهید.
پیادهسازی جستجوی درونیابی در سی پلاس پلاس
برای پیاده سازی یک تابع به نام interpolationSearch مینویسیم که در ورودی تابع خود مقدار x را دریافت میکند. سپس درون یک حلقه while الگوریتم را پیادهسازی میکنیم. ابتدا مقدار pos را درون هر دور از حلقه بدست آورده و در صورت یافتن عنصر مورد جستجو الگوریتم را پایان میدهیم. اگر عنصر x کوچکتر از خانه pos در آرایه باشد مقدار low و hi را طوری تغییر میدهیم که زیرآرایه سمت چپ pos را جستجو کنیم و برعکس زیرآرایه سمت راست. در پایان اگر عنصر x درون آرایه نباشد مقدار -1 را برمیگردانیم.
کد این الگوریتم به صورت زیر میباشد:
int interpolationSearch(int arr[], int n, int x) {
int lo = 0, hi = (n - 1);
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
int pos = lo
+ (((double) (hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
int main() {
int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 18;
int index = interpolationSearch(arr, n, x);
if (index != -1)
cout <<"Element found at index: " << index << endl;
else
cout<<"Element not found."<< endl;
return 0;
}
خروجی کد بالا به صورت زیر است:
Element found at index 4
