जंप सर्च तकनीक भी ऑर्डर्ड लिस्ट के लिए काम करती है। यह एक ब्लॉक बनाती है और उस ब्लॉक में एलिमेंट खोजने का प्रयास करती है। यदि आइटम ब्लॉक में नहीं है, तो यह पूरे ब्लॉक को शिफ्ट कर देती है। ब्लॉक आकार लिस्ट के आकार पर आधारित होता है। यदि लिस्ट का आकार n है तो ब्लॉक आकार √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 खोज कुंजी 356 आउटपुट: आइटम स्थान पर मिला: 11
एल्गोरिदम
jumpSearch(array, size, key)
इनपुट: एक सॉर्टेड सरणी, सरणी का आकार और खोज कुंजी
आउटपुट - कुंजी का स्थान (यदि मिला), अन्यथा गलत स्थान।
Begin blockSize := √size start := 0 end := blockSize while array[end] <= key AND end < size do start := end end := end + blockSize if end > size – 1 then end := size done for i := start to end -1 do if array[i] = key then return i done return invalid location End
उदाहरण
#include<iostream> #include<cmath> using namespace std; int jumpSearch(int array[], int size, int key) { int start = 0; int end = sqrt(size); //सरणी लंबाई का वर्गमूल while(array[end] <= key && end < size) { start = end; //यदि यह सही ब्लॉक नहीं है तो ब्लॉक शिफ्ट करें end += sqrt(size); if(end > size - 1) end = size; //यदि दायां सीमा पार करता है तो रेंज बांधें } for(int i = start; i= 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: 356 Item found at location: 11
