एक्सपोनेंशियल सर्च
बाइनरी सर्च को बीच में देखने से पहले यह जानना होता है कि सूची कहाँ ख़त्म होती है। एक्सपोनेंशियल सर्च को नहीं: यह लगातार बड़े होते क़दमों में आगे दौड़ता है जब तक लक्ष्य से आगे न निकल जाए, फिर आख़िरी क़दम में बाइनरी सर्च करता है। इसी वजह से यह अज्ञात लंबाई वाली सूचियों के लिए आदर्श है, और शुरुआत के पास वाले मानों के लिए तेज़।
मूल विचार
स्थान 1 का मान जाँचें, फिर 2, 4, 8, 16 और आगे इसी तरह, हर स्थान पिछले का दोगुना। जब तक वहाँ का मान लक्ष्य से छोटा है, लक्ष्य और आगे होना चाहिए। पहली बार जब कोई मान छोटा नहीं होता, लक्ष्य घिर जाता है: वह पिछली बार जाँचे गए स्थान के बाद है और इस स्थान से आगे नहीं। वह दायरा सॉर्ट है, इसलिए बाइनरी सर्च लक्ष्य को ढूँढ लेता है, या दिखा देता है कि वह नहीं है।
एक उदाहरण
2, 5, 8, 12, 16, 23, 38, 56, 72, 91 में 23 खोजें। स्थान 1 पर 2 है, स्थान 2 पर 5, स्थान 4 पर 12, सभी छोटे। स्थान 8 पर 56 है, जो बड़ा है, इसलिए 23 सिर्फ़ स्थान 5 से 7 तक हो सकता है। बाइनरी सर्च उनके बीच का स्थान 6 जाँचता है और 23 पाता है: 5 तुलनाएँ, जबकि साधारण बाइनरी सर्च को 3 चाहिए। उसी सूची में 12 खोजने पर सर्च 3 तुलनाओं के बाद स्थान 4 पर रुकता है, बाइनरी सर्च से एक कम, और 2 स्थान 1 पर सिर्फ़ एक तुलना में मिल जाता है।
कितनी तुलनाएँ
स्थान i पर मौजूद लक्ष्य के लिए, दोगुना करना लगभग log₂ i चरणों के बाद रुकता है, और i से कम स्थानों का दायरा छोड़ता है, जिसे बाइनरी सर्च लगभग log₂ i और चरणों में पूरा करता है। इसलिए सर्च में लगभग 2 log₂ i तुलनाएँ लगती हैं, सूची कितनी भी लंबी हो। लक्ष्य शुरुआत के पास हो तो यह बाइनरी सर्च से बेहतर है, जिसमें हमेशा लगभग log₂ n लगती हैं। अंत के पास हो तो एक्सपोनेंशियल सर्च में लगभग दोगुना तक लगता है। 40 मानों के लिए ऐप में पहले पाँच स्थानों पर औसतन लगभग 3 तुलनाएँ और आख़िरी पाँच पर लगभग 9 लगती हैं, जबकि बाइनरी सर्च में लगभग 4.6।
अज्ञात लंबाई, और गैलपिंग
Jon Bentley और Andrew Yao ने 1976 में अनबाउंडेड सर्च के लिए दोगुना करने की यह रणनीति बताई: ऐसे सॉर्ट किए हुए अनुक्रम में मान ढूँढना जिसका कोई ज्ञात अंत नहीं, जैसे अनंत सूची या ऐसी स्ट्रीम जिसे आप सिर्फ़ एक-एक स्थान पर जाँच सकते हैं। यही विचार मर्ज को भी तेज़ करता है। जब दो सॉर्ट किए हुए रन में से एक लगातार जीतता रहता है, तो Timsort गैलपिंग पर चला जाता है: अगला मान कहाँ जाएगा यह जानने के लिए वह एक-एक स्थान बढ़ने के बजाय दूसरे रन में 1, 2, 4, 8 स्थान आगे देखता है।
ख़ुद आज़माएँ
ऐप खोलें, खोजें में कोई मान चुनें, और आगे दबाएँ। स्थान 1, 2, 4, 8 और आगे के हर स्थान को देखते समय हाइलाइट किया जाता है; जैसे ही कोई मान छोटा नहीं होता, आख़िरी दो स्थानों के बीच का दायरा छायांकित हो जाता है और बाइनरी सर्च काम सँभाल लेता है। पहले कोई छोटा मान खोजें और फिर कोई बड़ा, और गिनती को बाइनरी सर्च टाइल से मिलाएँ।
अक्सर पूछे जाने वाले प्रश्न
एक्सपोनेंशियल सर्च की टाइम कॉम्प्लेक्सिटी क्या है?
स्थान i पर मौजूद लक्ष्य के लिए O(log i), इसलिए n मानों की सूची के लिए ज़्यादा से ज़्यादा O(log n)। इसे O(1) अतिरिक्त मेमोरी और सॉर्ट की हुई सूची चाहिए।
एक्सपोनेंशियल सर्च और बाइनरी सर्च में क्या अंतर है?
बाइनरी सर्च पूरी सूची से शुरू होता है और उसे सूची की लंबाई चाहिए। एक्सपोनेंशियल सर्च पहले दोगुना करके ऐसा दायरा ढूँढता है जिसमें लक्ष्य हो, फिर सिर्फ़ उसी दायरे में बाइनरी सर्च करता है। लक्ष्य शुरुआत के पास हो तो यह तेज़ है, और लंबाई जाने बिना काम करता है।
क़दम को दोगुना क्यों करें, कोई तय मात्रा क्यों न जोड़ें?
तय क़दम जोड़ना जंप सर्च है, जिसमें सूची पार करने के लिए लगभग n को क़दम से भाग देने जितनी बार देखना पड़ता है। दोगुना करने से लगभग log₂ i बार देखने में स्थान i तक पहुँच जाते हैं, और जो दायरा बचता है वह ज़रूरत के दोगुने से बड़ा कभी नहीं होता, इसलिए बाद का बाइनरी सर्च छोटा रहता है।
एक्सपोनेंशियल सर्च का इस्तेमाल कहाँ होता है?
असीमित या बहुत लंबे सॉर्ट किए हुए डेटा में खोजने में, सॉर्ट किए हुए रन को मर्ज करने में (Timsort में गैलपिंग), और ऊपरी सीमा पता न होने पर वह पहला स्थान ढूँढने में जहाँ कोई शर्त सच हो जाती है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एक्सपोनेंशियल सर्च आज़माएँ