जाँचें
अब भी संभव
बाइनरी सर्च को चाहिए

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

इंटरपोलेशन सर्च के बारे में और

इंटरपोलेशन सर्च

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

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

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

इंटरपोलेशन सर्च कैसे काम करता है

सॉर्ट की हुई सूची के उस हिस्से का पहला और आख़िरी मान देखें जिसमें लक्ष्य अब भी हो सकता है। अगर लक्ष्य, मान लीजिए, पहले मान से आख़िरी मान तक के रास्ते के 40% पर है, तो उस हिस्से में 40% आगे वाला स्थान जाँचें। अगर वहाँ का मान ही लक्ष्य है, तो काम पूरा। अगर वह छोटा है, तो सिर्फ़ उसके बाद के स्थान बचते हैं; अगर बड़ा है, तो सिर्फ़ उसके पहले के। बचे हुए हिस्से में फिर से अनुमान लगाएँ। अगर लक्ष्य पहले मान से छोटा या आख़िरी मान से बड़ा है, तो वह सूची में नहीं है।

अनुमान कब काम करता है

अगर मान बराबर फैले हों, जैसे 10, 20, 30 वगैरह, तो पहला अनुमान ठीक लक्ष्य पर या उसके बहुत पास पड़ता है, और औसतन लगभग log₂(log₂ n) जाँचें लगती हैं: एक अरब मानों के लिए लगभग 5, जबकि बाइनरी सर्च को 30 चाहिए। अगर मान एक जगह जमा हों, जैसे 1, 2, 3, 4, 1000, तो अनुमान बार-बार ग़लत जगह पड़ते हैं और हर जाँच शायद सिर्फ़ एक मान हटाए, इसलिए सबसे ख़राब स्थिति में n जाँचें लगती हैं। बाइनरी सर्च कभी लगभग log₂ n से बुरा नहीं करता।

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

इंटरपोलेशन सर्च कैसे काम करता है?

सॉर्ट की हुई सूची पर यह बचे हुए हिस्से के पहले और आख़िरी मान से अनुमान लगाता है कि लक्ष्य कहाँ होना चाहिए, उस स्थान को जाँचता है, और सिर्फ़ सही तरफ़ का हिस्सा रखता है। यह बाइनरी सर्च जैसा है, बस बीच के बजाय ज़्यादा समझदारी भरा अनुमान लगाता है।

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

बराबर फैले मानों पर, हाँ: औसतन लगभग log₂ n के बजाय लगभग log₂(log₂ n) जाँचें। असमान रूप से फैले मानों पर यह बहुत धीमा हो सकता है, n जाँचों तक, जबकि बाइनरी सर्च को कभी लगभग log₂ n से ज़्यादा नहीं चाहिए।

यह धीमा क्यों हो सकता है?

क्योंकि अनुमान मानता है कि मान बराबर बढ़ते हैं। अगर ज़्यादातर मान छोटे हों और कुछ बहुत बड़े, तो छोटे लक्ष्य का अनुमान बार-बार शुरुआत के पास पड़ता है और हर बार सिर्फ़ एक-दो मान हटाता है।

इंटरपोलेशन सर्च कहाँ इस्तेमाल होता है?

जहाँ कुंजियाँ लगभग बराबर फैली हों और जाँच महँगी हो, जैसे डिस्क पर संख्यात्मक ID या हैश से रिकॉर्ड खोजना। कई सिस्टम सबसे ख़राब स्थिति को ठीक रखने के लिए इसे बाइनरी सर्च के साथ मिलाते हैं।

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

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

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

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

एडिटर पर जाएँ