बाइनरी सर्च तकनीक के लिए, लिस्ट को समान भागों में विभाजित किया जाता है। इंटरपोलेशन खोज तकनीक के लिए, प्रक्रिया इंटरपोलेशन सूत्र का उपयोग करके सटीक स्थान का पता लगाने का प्रयास करेगी। अनुमानित स्थान मिलने के बाद, यह उस स्थान का उपयोग करके लिस्ट को विभाजित कर सकती है। चूंकि यह हर बार सटीक स्थान खोजने का प्रयास करता है, इसलिए खोज समय कम हो जाता है। यह तकनीक आइटम्स को आसानी से ढूंढ सकती है यदि आइटम्स समान रूप से वितरित हैं।
इंटरपोलेशन सर्च तकनीक की जटिलता
- समय जटिलता: औसत केस के लिए O(log₂(log₂ 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)
इनपुट - एक सॉर्टेड सरणी, प्रारंभ और अंत स्थान, और खोज कुंजी
आउटपुट: कुंजी का स्थान (यदि मिला), अन्यथा गलत स्थान।
Begin while start <= end AND key >= array[start] AND key <= array[end] do dist := key – array[start] valRange := array[end] – array[start] fraction := dist / valRange indexRange := end – start estimate := start + (fraction * indexRange) if array[estimate] = key then return estimate position if array[estimate] < key then start := estimate + 1 else end = estimate -1 done return invalid position End
उदाहरण
#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 << "Enter number of items: "; cin >> n; int arr[n]; //आकार n की सरणी बनाएं cout << "Enter items: " << endl; for(int i = 0; i< n; i++) { cin >> arr[i]; } cout << "Enter search key to search in the list: "; cin >> searchKey; if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0) cout << "Item found at location: " << loc << endl; else cout << "Item is not found in the list." << endl; }आउटपुट
Enter number of items: 20 Enter items: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 Enter search key to search in the list: 780 Item found at location: 16
