(9 امتیاز از 2 رای)
Loading...
الگوریتم جستجوی درونیابی (Interpolation Search)
در این بخش الگوریتم جستجوی درونیابی (Interpolation Search) را با یک مثال ساده بررسی خواهیم کرد. این الگوریتم به منظور جستجوی یک مقدار درون یک آرایه که با اندیس های عددی مرتب شده است، استفاده می شود.
مسئله
با توجه به آرایه مرتب داده شده (arr[])، تابعی بنویسید که عنصر x را در آرایه جستجو کند.
حل
الگوریتم جستجوی خطی، عنصر مورد نظر با پیچدگی زمانی O(n)، جستجوی پرشی با پیچدگی زمانی O(√ n) و جستجوی باینری با پیچدگی زمانی O(Log n) پیدا می کند.
جستجوی درونیابی، نوع بهبود یافته الگوریتم جستجوی باینری برای نمونه هایی است که در آن ها مقادیر آرایه مرتب و به طور یکنواخت توزیع شده اند. در جستحوی باینری همیشه جستجو از وسط مجموعه شروع می شود، اما در این الگوریتم ممکن است بر اساس مقدار مورد نظر (مقدار key)، جستجو از اندیس دیگری شروع شود.
برای پیدا کردن موقعیتی که جستجو باید از آن شروع شود، از فرمول زیر استفاده می کنیم:
1 2 3 4 5 6 7 8 | // 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++ را مشاهده می کنید:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | // 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; } |
خروجی:
1 | Element found at index 4 |
نکات
- پیچیدگی زمانی الگوریتم Interpolation Search در صورتی که عناصر به طور یکنواخت توزیع شده باشند، برابر با O (log log n)) و در بدترین حالت هم برابر با O(n) است.
- فضای موقت برابر با O(1) است.
هیچ نظری ثبت نشده است