तुलनाएँ
अब भी संभव
बाइनरी सर्च को चाहिए

  • लक्ष्य
  • अब भी संभव
  • तुलना में
  • ख़ारिज
  • मिला

एक्सपोनेंशियल सर्च के बारे में और

एक्सपोनेंशियल सर्च

एक्सपोनेंशियल सर्च सॉर्ट की हुई सूची में कोई मान दो चरणों में ढूँढता है। पहले यह स्थान 1, 2, 4, 8, 16 और आगे इसी तरह देखता है, हर बार दोगुना करते हुए, जब तक वहाँ का मान लक्ष्य से छोटा न रहे। फिर यह आख़िरी दो स्थानों के बीच के दायरे में बाइनरी सर्च करता है। खोजने के लिए मान चुनें और देखें कि शुरुआत के पास वाले लक्ष्य कुछ ही तुलनाओं में क्यों मिल जाते हैं। सर्च देखने के लिए चलाएँ दबाएँ, या एक-एक चरण बढ़ने के लिए आगे और पीछे दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। डैश वाली रेखा उस मान को दिखाती है जिसे आप खोज रहे हैं, और छायांकित हिस्सा वह है जहाँ वह अब भी हो सकता है। एक्सपोनेंशियल सर्च के लिए सॉर्ट की हुई सूची चाहिए, इसलिए बिना सॉर्ट की सूची पहले सॉर्ट की जाती है। मान और बार की संख्या चुनें, या अपनी संख्याएँ लिखें। बोर्ड चुना हो तो तीर कुंजियाँ एक-एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home व End शुरुआत और अंत पर ले जाते हैं।

यह कैसे काम करता है

  1. खोजने के लिए मान और बार की संख्या चुनें। या अपनी संख्याएँ लिखें: एक्सपोनेंशियल सर्च पहले उन्हें सॉर्ट करता है।
  2. चलाएँ दबाएँ, या एक-एक चरण बढ़ने के लिए आगे और पीछे का इस्तेमाल करें। सर्च में कहीं भी जाने के लिए चरण स्लाइडर खींचें।
  3. शुरुआत के पास का एक मान और अंत के पास का एक मान खोजें, और गिनती को बाइनरी सर्च को चाहिए से मिलाएँ।

एक्सपोनेंशियल सर्च कैसे काम करता है

स्थान 1 का मान देखें। अगर वह लक्ष्य से छोटा है, तो स्थान 2 देखें, फिर 4, 8, 16, हर बार दोगुना करते हुए। जैसे ही कोई मान छोटा न हो, रुक जाएँ: लक्ष्य सिर्फ़ पिछली बार देखे गए स्थान के बाद और इस स्थान से पहले हो सकता है। उस दायरे में बाइनरी सर्च करें। अगर दोगुना करते-करते सूची का अंत पार हो जाए, तो आख़िरी देखे गए स्थान से अंत तक बाइनरी सर्च करें।

शुरुआत के पास तेज़, और लंबाई की ज़रूरत नहीं

स्थान i पर मौजूद लक्ष्य तक पहुँचने के लिए दोगुना करने में लगभग log₂ i बार देखना पड़ता है, और मिले हुए दायरे में i से कम मान होते हैं, इसलिए बाइनरी सर्च में लगभग log₂ i और लगते हैं। कुल मिलाकर लगभग 2 log₂ i, जो इस पर निर्भर करता है कि लक्ष्य कहाँ है, न कि सूची कितनी लंबी है। शुरुआत के पास वाले लक्ष्य साधारण बाइनरी सर्च से जल्दी मिलते हैं; अंत के पास वाले लक्ष्यों में लगभग दोगुना तक लग सकता है। क्योंकि इसे कभी सूची की लंबाई नहीं चाहिए, यह उन सूचियों पर भी काम करता है जो मापने के लिए बहुत लंबी हैं या जिनका कोई ज्ञात अंत नहीं है।

अक्सर पूछे जाने वाले प्रश्न

एक्सपोनेंशियल सर्च कैसे काम करता है?

सॉर्ट की हुई सूची पर यह स्थान 1, 2, 4, 8 और आगे इसी तरह जाँचता है, जब तक वहाँ का मान लक्ष्य से छोटा न रहे। तब लक्ष्य सिर्फ़ आख़िरी जाँचे गए दो स्थानों के बीच हो सकता है, और उस दायरे में बाइनरी सर्च उसे ढूँढ लेता है।

क्या एक्सपोनेंशियल सर्च बाइनरी सर्च से तेज़ है?

जब लक्ष्य सूची की शुरुआत के पास हो, तो हाँ: स्थान i पर मौजूद लक्ष्य के लिए लगभग 2 log₂ i तुलनाएँ लगती हैं, सूची कितनी भी लंबी हो। जब लक्ष्य अंत के पास हो, तो साधारण बाइनरी सर्च तेज़ है, लगभग दोगुना तक।

इसका इस्तेमाल किसलिए होता है?

ऐसी सूचियों में खोजने के लिए जिनकी लंबाई अज्ञात या असीमित है, जैसे स्ट्रीम या अनंत अनुक्रम, और सॉर्ट किए हुए रन को मर्ज करने के लिए, जहाँ अगला मेल आमतौर पर पास ही होता है। Timsort का गैलपिंग मोड भी दोगुना करने के इसी विचार का इस्तेमाल करता है।

इसे एक्सपोनेंशियल क्यों कहते हैं?

क्योंकि जिन स्थानों को यह जाँचता है वे एक्सपोनेंशियल रूप से बढ़ते हैं: 1, 2, 4, 8, 16, हर एक पिछले का दोगुना। इसे डबलिंग सर्च या गैलपिंग सर्च भी कहते हैं।

क्या मेरी संख्याएँ कहीं भेजी जाती हैं?

नहीं। सर्च आपके ब्राउज़र में चलता है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिटर पर जाएँ