बाइनरी सर्च

निर्देश

आपको एक बाइनरी सर्च एल्गोरिदम लागू करना है।

बाइनरी सर्च एल्गोरिदम किसी ऐरे को बार-बार आधा-आधा बाँटकर उसमें मौजूद एलिमेंट ढूँढ़ता है। हर बार वह सिर्फ उसी आधे हिस्से को रखता है जिसमें ढूँढ़ा जा रहा एलिमेंट मौजूद होता है। इसकी मदद से हम अपने एलिमेंट की संभावित जगहों को जल्दी से सीमित कर लेते हैं, और यह क्रम तब तक चलता है जब तक हमें वह एलिमेंट मिल न जाए या सभी संभावित जगहें खत्म न हो जाएँ।

यह एल्गोरिदम ऐसा काम करता है:

• क्रमबद्ध ऐरे का बीच वाला एलिमेंट निकालिए और उसकी तुलना उस एलिमेंट से कीजिए जिसे हम ढूँढ़ रहे हैं।
• अगर बीच वाला एलिमेंट ही हमारा ढूँढ़ा जा रहा एलिमेंट है, तो काम पूरा!
• अगर बीच वाला एलिमेंट हमारे एलिमेंट से बड़ा है, तो हम उस एलिमेंट को और उसके बाद आने वाले सभी एलिमेंट को बाहर कर सकते हैं।
• अगर बीच वाला एलिमेंट हमारे एलिमेंट से छोटा है, तो हम उस एलिमेंट को और उसके पहले आने वाले सभी एलिमेंट को बाहर कर सकते हैं।
• अगर ऐरे का हर एलिमेंट बाहर हो चुका है, तो वह एलिमेंट ऐरे में नहीं है।
• वरना, ऐरे के जिस हिस्से को बाहर नहीं किया गया है, उस पर यही प्रक्रिया दोहराइए।

यहाँ एक उदाहरण है:

मान लीजिए हम इस क्रमबद्ध ऐरे में संख्या 23 ढूँढ़ रहे हैं: [4, 8, 12, 16, 23, 28, 32].

• हम 23 की तुलना बीच वाले एलिमेंट 16 से करके शुरू करते हैं।
• चूँकि 23, 16 से बड़ा है, हम ऐरे का बायाँ आधा हिस्सा बाहर कर सकते हैं, और हमारे पास [23, 28, 32] बचता है।
• इसके बाद हम 23 की तुलना नए बीच वाले एलिमेंट 28 से करते हैं।
• चूँकि 23, 28 से छोटा है, हम ऐरे का दायाँ आधा हिस्सा बाहर कर सकते हैं: [23].
• हमें अपना एलिमेंट मिल गया।

---

स्रोत

Wikipedia