बाइनरी सर्च तकनीक के लिए, सूचियों को समान भागों में विभाजित किया जाता है। इंटरपोलेशन सर्चिंग तकनीक के लिए, प्रक्रिया इंटरपोलेशन फॉर्मूला का उपयोग करके सटीक स्थिति का पता लगाने का प्रयास करेगी। अनुमानित स्थान ढूंढने के बाद, यह उस स्थान का उपयोग करके सूची को अलग कर सकता है। चूंकि यह हर बार सटीक स्थान खोजने का प्रयास करता है, इसलिए खोज समय कम हो जाता है। यह तकनीक आइटम्स को आसानी से ढूंढ सकती है यदि आइटम्स समान रूप से वितरित हैं।
इंटरपोलेशन सर्च तकनीक की जटिलता
समय जटिलता: औसत मामले के लिए O(log2(log2 n)), और सबसे खराब स्थिति के लिए O(n) (जब आइटम्स घातीय रूप से वितरित होते हैं)
स्पेस जटिलता: O(1)
इनपुट − डेटा की एक क्रमबद्ध सूची 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995। खोज कुंजी 780 आउटपुट − आइटम स्थान पर मिला: 16
एल्गोरिदम
interpolationSearch(array, start, end, key)
इनपुट: एक क्रमबद्ध सरणी, प्रारंभ और अंत स्थान, और खोज कुंजी
आउटपुट: कुंजी का स्थान (यदि मिला), अन्यथा गलत स्थान।
शुरुआत जब तक start <= end AND key >= array[start] AND key <= array[end] करें dist := key – array[start] valRange := array[end] – array[start] fraction := dist / valRange indexRange := end – start estimate := start + (fraction * indexRange) यदि array[estimate] = key तो estimate स्थिति वापस करें यदि array[estimate] < key तो start := estimate + 1 अन्यथा end = estimate -1 हो गया अमान्य स्थिति वापस करें अंत
उदाहरण कोड
#include<iostream> using namespace std; int interpolationSearch(int array[], int start, int end, int key) { int dist, valRange, indexRange, estimate; float fraction; while(start <= end && key >= array[start] && key <= array[end]) { dist = key - array[start]; valRange = array[end] - array[start]; //मान की सीमा fraction = dist / valRange; indexRange = end - start; estimate = start + (fraction * indexRange); //कुंजी की अनुमानित स्थिति if(array[estimate] == key) return estimate; if(array[estimate] < key) start = estimate +1; else end = estimate - 1; } return -1; } int main() { int n, searchKey, loc; cout << "आइटम की संख्या दर्ज करें: "; cin >> n; int arr[n]; //आकार n की एक सरणी बनाएं cout << "आइटम दर्ज करें: " << endl; for(int i = 0; i< n; i++) { cin >> arr[i]; } cout << "सूची में खोजने के लिए खोज कुंजी दर्ज करें: "; cin >> searchKey; if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0) cout << "आइटम स्थान पर मिला: " << loc << endl; else cout << "आइटम सूची में नहीं मिला." << endl; }
आउटपुट
आइटम की संख्या दर्ज करें: 20 आइटम दर्ज करें: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 खोज कुंजी दर्ज करें: 780 आइटम स्थान पर मिला: 16
