जंप सर्च
जंप सर्च वैसा ही है जैसे बिना विषय-सूची वाली किताब में कोई पेज ढूँढना: एक बार में कई पन्ने आगे पलटें, पेज नंबर पर नज़र डालें, और आगे निकल जाने पर आख़िरी हिस्से में पीछे की ओर पन्ने पलटें। सॉर्ट की हुई सूची पर इसमें हर मान जाँचने से बहुत कम तुलनाएँ लगती हैं।
मूल विचार
सॉर्ट की हुई सूची में, किसी ब्लॉक का आख़िरी मान बता देता है कि लक्ष्य उस ब्लॉक में हो भी सकता है या नहीं: अगर वह लक्ष्य से छोटा है, तो ब्लॉक का हर मान भी छोटा है। इसलिए अंदर देखने की ज़रूरत नहीं। हर ब्लॉक का आख़िरी मान बारी-बारी से जाँचें और पूरे ब्लॉक छोड़ते जाएँ, जब तक कोई मान लक्ष्य से छोटा न हो। तब लक्ष्य सिर्फ़ उसी ब्लॉक में हो सकता है: उसे शुरुआत से स्कैन करें।
एक उदाहरण
2, 5, 8, 12, 16, 23, 38, 56, 72, 91 में 23 खोजें, 3 मानों के ब्लॉकों के साथ। पहला ब्लॉक 8 पर ख़त्म होता है, जो छोटा है, इसलिए उसे छोड़ दें। दूसरा ब्लॉक 23 पर ख़त्म होता है, जो छोटा नहीं है, इसलिए 23 सिर्फ़ 12, 16, 23 में हो सकता है। इसे स्कैन करने पर 12, 16 और फिर 23 मिलता है: 5 तुलनाओं के बाद मिला, जबकि लीनियर सर्च को 6 और बाइनरी सर्च को 3 चाहिए। 40 खोजने पर, ब्लॉकों के आख़िरी मान 8, 23 और 72 ब्लॉक 38, 56, 72 तक ले जाते हैं; 38 छोटा है और 56 पहले ही बड़ा है, इसलिए 40 वहाँ नहीं है: फिर से 5 तुलनाएँ।
√n ही क्यों
m मानों के ब्लॉकों के साथ, सही ब्लॉक ढूँढने में ज़्यादा से ज़्यादा लगभग n/m तुलनाएँ लगती हैं और उसे स्कैन करने में ज़्यादा से ज़्यादा m। कम और लंबे जंप से स्कैन लंबा होता है; ज़्यादा और छोटे जंप से जंप करना लंबा होता है। जोड़ n/m + m तब सबसे कम होता है जब दोनों हिस्से बराबर हों, यानी m = √n पर, जहाँ यह लगभग 2√n होता है। 40 मानों के लिए इसका मतलब है 6 के ब्लॉक और ज़्यादा से ज़्यादा 13 तुलनाएँ; दस लाख मानों के लिए 1,000 के ब्लॉक और लगभग 2,000 तुलनाएँ।
यह कहाँ काम आता है
बाइनरी सर्च को कम तुलनाएँ चाहिए, लगभग log₂ n। लेकिन बाइनरी सर्च पूरी सूची में आगे-पीछे कूदता है, जबकि जंप सर्च सिर्फ़ आगे बढ़ता है और एक ही बार पीछे जाता है, एक ब्लॉक की शुरुआत तक। इसी वजह से यह टेप पर रखे डेटा या लिंक्ड संरचना वाले डेटा के लिए आकर्षक था, जहाँ पीछे जाना धीमा होता है। Ben Shneiderman ने 1978 में इसे jump searching के नाम से बताया। √n ब्लॉकों में बाँटने का यही विचार, जिसे अक्सर स्क्वायर-रूट डीकंपोज़िशन कहते हैं, कई दूसरे एल्गोरिदम में भी आता है।
ख़ुद आज़माएँ
ऐप खोलें, खोजें में कोई मान चुनें, और आगे दबाएँ। हर जंप किसी ब्लॉक के आख़िरी मान को हाइलाइट करता है; छोड़े गए ब्लॉक फीके पड़ जाते हैं, और जिस ब्लॉक में लक्ष्य हो सकता है, वह स्कैन के दौरान छायांकित रहता है। 40 बार के साथ जंप साइज़ को √n से 2 या 8 करें, और देखें कि जंप और स्कैन के बीच संतुलन कैसे बदलता है।
अक्सर पूछे जाने वाले प्रश्न
जंप सर्च की टाइम कॉम्प्लेक्सिटी क्या है?
√n मानों के ब्लॉकों के साथ O(√n): ज़्यादा से ज़्यादा लगभग 2√n तुलनाएँ। इसे O(1) अतिरिक्त मेमोरी और सॉर्ट की हुई सूची चाहिए।
जंप सर्च और बाइनरी सर्च में क्या अंतर है?
बाइनरी सर्च हर बार बचे हुए हिस्से को आधा करता है और लगभग log₂ n तुलनाएँ लेता है, पर आगे-पीछे चलता है। जंप सर्च तय कदमों में आगे कूदता है और एक ब्लॉक स्कैन करता है, लगभग 2√n तुलनाएँ लेता है, और सिर्फ़ एक बार पीछे जाता है।
क्या आख़िरी ब्लॉक के स्कैन में बाइनरी सर्च इस्तेमाल हो सकता है?
हाँ। ब्लॉक को बाइनरी सर्च से खोजने पर स्कैन m तुलनाओं से घटकर लगभग log₂ m रह जाता है। जंप में अब भी n/m लगती हैं, इसलिए तब बड़े ब्लॉक फ़ायदेमंद होते हैं।
क्या जंप सर्च के लिए सॉर्ट की हुई सूची चाहिए?
हाँ। ब्लॉक छोड़ना सिर्फ़ इसलिए सुरक्षित है क्योंकि उसका आख़िरी मान छोटा होने का मतलब है कि उसका हर मान छोटा है। ऐप बिना सॉर्ट की सूची को पहले सॉर्ट करता है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
जंप सर्च आज़माएँ