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

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

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

مسئله

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

حل

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

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

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

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]
arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

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

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

// C++ program to implement interpolation search
#include<bits/stdc++.h>
using namespace std;
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int n, int x)
{
    // Find indexes of two corners
    int lo = 0, hi = (n - 1);
    // Since array is sorted, an element present
    // in array must be in range defined by corner
    while (lo <= hi && x >= arr[lo] && x <= arr[hi])
    {
        if (lo == hi)
        {
            if (arr[lo] == x) return lo;
            return -1;
        }
        // Probing the position with keeping
        // uniform distribution in mind.
        int pos = lo + (((double)(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;
}
// Driver Code
int main()
{
    // Array of items on which search will
    // be conducted.
    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; // Element to be searched
    int index = interpolationSearch(arr, n, x);
    // If element was found
    if (index != -1)
        cout << "Element found at index " << index;
    else
        cout << "Element not found.";
    return 0;
}

امتحان کنید

خروجی:

Element found at index 4

نکات

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

نوشته الگوریتم جستجوی درونیابی (Interpolation Search) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.