एक्सपोनेंशियल सर्च को डबलिंग या गैलोपिंग सर्च के रूप में भी जाना जाता है। यह तंत्र उस रेंज को खोजने के लिए उपयोग किया जाता है जहां खोज कुंजी मौजूद हो सकती है। यदि L और U लिस्ट की निचली और ऊपरी सीमा हैं, तो L और U दोनों 2 की घात हैं। अंतिम खंड के लिए, U लिस्ट की अंतिम स्थिति है। इस कारण से, इसे एक्सपोनेंशियल के रूप में जाना जाता है।
विशिष्ट रेंज मिलने के बाद, यह खोज कुंजी के सटीक स्थान को खोजने के लिए बाइनरी सर्च तकनीक का उपयोग करता है।
एक्सपोनेंशियल सर्च तकनीक की जटिलता
- समय जटिलता: बेस्ट केस के लिए O(1)। औसत या वर्स्ट केस के लिए O(log₂ i)। जहां i वह स्थान है जहां खोज कुंजी मौजूद है।
- स्पेस जटिलता: O(1)
इनपुट और आउटपुट
इनपुट: सॉर्टेड डेटा की सूची: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 खोज कुंजी 780 आउटपुट: आइटम स्थान पर मिला: 16
एल्गोरिदम
binarySearch(array, start, end, key)
इनपुट: एक सॉर्टेड सरणी, प्रारंभ और अंत स्थान, और खोज कुंजी
आउटपुट - कुंजी का स्थान (यदि मिला), अन्यथा गलत स्थान।
Begin if start <= end then mid := start + (end - start) /2 if array[mid] = key then return mid location if array[mid] > key then call binarySearch(array, mid+1, end, key) else when array[mid] < key then call binarySearch(array, start, mid-1, key) else return invalid location End
exponentialSearch(array, start, end, key)
इनपुट: एक सॉर्टेड सरणी, प्रारंभ और अंत स्थान, और खोज कुंजी
आउटपुट: कुंजी का स्थान (यदि मिला), अन्यथा गलत स्थान।
Begin if (end – start) <= 0 then return invalid location i := 1 while i < (end - start) do if array[i] < key then i := i * 2 //i को 2 की घात के रूप में बढ़ाएं else terminate the loop done call binarySearch(array, i/2, i, key) End
उदाहरण
#include<iostream> using namespace std; int binarySearch(int array[], int start, int end, int key) { if(start <= end) { int mid = (start + (end - start) /2); //लिस्ट का मिड स्थान if(array[mid] == key) return mid; if(array[mid] > key) return binarySearch(array, start, mid-1, key); return binarySearch(array, mid+1, end, key); } return -1; } int exponentialSearch(int array[], int start, int end, int key){ if((end - start) <= 0) return -1; int i = 1; // as 2^0 = 1 while(i < (end - start)){ if(array[i] < key) i *= 2; //i 2 की घात के रूप में बढ़ेगा else break; //जब array[i] कुंजी एलिमेंट को पार करता है } return binarySearch(array, i/2, i, key); //छोटी रेंज में आइटम खोजें } 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 = exponentialSearch(arr, 0, n, 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
