बाइनरी सर्च

निर्देश

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

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

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

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

यहाँ एक उदाहरण देखिए:

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

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

ट्रैक के लिए विशेष नोट्स

अगर ऐरे में यह एलिमेंट मौजूद न हो, तो सिंबल 'not-found लौटाइए। ऐरे को वेक्टर के रूप में पास किया जाएगा।

---

स्रोत

Wikipedia