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

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

बाइनरी सर्च के बारे में और

बाइनरी सर्च

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

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

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

बाइनरी सर्च कैसे काम करता है

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

यह इतना तेज़ क्यों है

हर तुलना बचे हुए हिस्से को आधा कर देती है। n मानों से शुरू करें तो k तुलनाओं के बाद ज़्यादा से ज़्यादा लगभग n/2ᵏ बचते हैं, इसलिए सर्च ज़्यादा से ज़्यादा ⌊log₂ n⌋ + 1 तुलनाओं में पूरा हो जाता है: 40 मानों के लिए 6, 1,000 के लिए 10, दस लाख के लिए 20। लीनियर सर्च को हर मान देखना पड़ सकता है। शर्त यह है कि सूची सॉर्ट हो, और उसे सॉर्ट रखने या पहले सॉर्ट करने की भी अपनी लागत है।

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

बाइनरी सर्च कैसे काम करता है?

यह लक्ष्य की तुलना सॉर्ट की हुई सूची के उस हिस्से के बीच वाले मान से करता है जिसमें लक्ष्य अब भी हो सकता है। बराबर हो तो मिल गया; वरना जिस आधे में लक्ष्य नहीं हो सकता, वह हटा दिया जाता है, और सर्च दूसरे आधे में तब तक चलता है जब तक लक्ष्य मिल न जाए या कुछ न बचे।

बाइनरी सर्च को कितनी तुलनाएँ चाहिए?

n मानों की सूची के लिए ज़्यादा से ज़्यादा ⌊log₂ n⌋ + 1: 40 के लिए 6, 1,000 के लिए 10, दस लाख के लिए 20। हर तुलना बचे हुए हिस्से को आधा कर देती है।

बाइनरी सर्च को सॉर्ट की हुई सूची क्यों चाहिए?

क्योंकि सिर्फ़ सॉर्ट की हुई सूची में ही एक तुलना बताती है कि लक्ष्य किस तरफ़ है। बिना सॉर्ट की सूची में बीच का छोटा मान यह नहीं बताता कि लक्ष्य कहाँ है, इसलिए कुछ भी हटाया नहीं जा सकता।

डुप्लिकेट मान हों तो यह कौन-सा मान ढूँढता है?

उनमें से कोई भी एक, इस पर निर्भर करता है कि बीच कहाँ पड़ता है। जो रूप मिलान के बाद भी बाएँ या दाएँ खोजते रहते हैं, वे पहली या आख़िरी बार आने वाला मान ढूँढते हैं।

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

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

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

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

एडिटर पर जाएँ