परिचय
आप गणितज्ञों के एक ऐसे समूह से मिले हैं जो गायक-गीतकार भी हैं।
उन्होंने अपनी हर पसंदीदा संख्या के लिए एक गाना लिखा है, और जैसा कि आप अंदाज़ा लगा सकते हैं, उनकी पसंदीदा संख्याएँ बहुत सारी हैं (जैसे 0, 73 या 6174)।
आप अपनी पसंदीदा संख्या का गाना सुनने के लिए उत्सुक हैं, लेकिन गाने इतने सारे हैं कि सही गाना ढूँढने में थोड़ा समय लग सकता है।
अच्छी बात यह है कि उन्होंने अपने गानों को एक प्लेलिस्ट में शीर्षक के हिसाब से लगाया है। शीर्षक और कुछ नहीं, वही संख्या है जिसके बारे में वह गाना है।
आप समझ जाते हैं कि शीर्षक देखकर गाना जल्दी ढूँढने के लिए आप बाइनरी सर्च एल्गोरिदम का उपयोग कर सकते हैं।
निर्देश
आपको एक बाइनरी सर्च एल्गोरिदम लागू करना है।
बाइनरी सर्च एल्गोरिदम किसी ऐरे में कोई चीज़ ढूँढता है। इसके लिए वह ऐरे को बार-बार आधे में बाँटता है और सिर्फ उसी आधे को रखता है जिसमें वह चीज़ होती है जिसे हम ढूँढ रहे हैं। इससे हम अपनी चीज़ की संभावित जगहों को जल्दी-जल्दी कम करते जाते हैं, जब तक कि वह चीज़ मिल न जाए या सारी संभावित जगहें खत्म न हो जाएँ।
बाइनरी सर्च सिर्फ तब काम करती है जब ऐरे क्रमबद्ध हो।
यह एल्गोरिदम ऐसा दिखता है:
- किसी क्रमबद्ध ऐरे का बीच का एलिमेंट ढूँढिए और उसकी तुलना उस चीज़ से कीजिए जिसे हम ढूँढ रहे हैं।
- अगर बीच का एलिमेंट हमारी चीज़ है, तो काम पूरा!
- अगर बीच का एलिमेंट हमारी चीज़ से बड़ा है, तो हम उस एलिमेंट को और उसके बाद के सारे एलिमेंट को हटा सकते हैं।
- अगर बीच का एलिमेंट हमारी चीज़ से छोटा है, तो हम उस एलिमेंट को और उसके पहले के सारे एलिमेंट को हटा सकते हैं।
- अगर ऐरे का हर एलिमेंट हट चुका है, तो वह चीज़ ऐरे में नहीं है।
- वरना ऐरे का जो हिस्सा अभी हटा नहीं गया है, उस पर यही प्रक्रिया दोहराइए।
यहाँ एक उदाहरण देखिए:
मान लीजिए हमें इस क्रमबद्ध ऐरे में संख्या 23 ढूँढनी है: [4, 8, 12, 16, 23, 28, 32].
- सबसे पहले हम 23 की तुलना बीच के एलिमेंट, यानी 16 से करते हैं।
- 23, 16 से बड़ा है, इसलिए हम ऐरे का बायाँ आधा हिस्सा हटा सकते हैं। अब हमारे पास
[23, 28, 32] बचता है।
- इसके बाद हम 23 की तुलना नए बीच के एलिमेंट, यानी 28 से करते हैं।
- 23, 28 से छोटा है, इसलिए हम ऐरे का दायाँ आधा हिस्सा हटा सकते हैं:
[23].
- हमें अपनी चीज़ मिल गई।
प्रतिबंध
कलेक्शन टूल की स्टैंडर्ड लाइब्रेरी इस्तेमाल करके अपने आप को कम न समझिए। आप इस अभ्यास को Array.tryFindIndex जैसे टूल के बिना पूरा कर सकते हैं, और करना भी चाहिए।
संकेत
इस अभ्यास में नीचे दिए गए F# फीचर काम आते हैं:
-
टेल रिकर्शन बड़े इनपुट पर स्टैक ओवरफ्लो रोकने के लिए टेल रिकर्शन इस्तेमाल कीजिए। हालाँकि इसकी स्पष्ट जाँच करने वाले कोई टेस्ट केस नहीं हैं, फिर भी टेल रिकर्शन इस्तेमाल करने से हल का प्रदर्शन बेहतर होता है। टेल रिकर्शन पर एक और अच्छा संसाधन यह ब्लॉग पोस्ट है।
-
पैटर्न मैचिंग बहुत शक्तिशाली है और कई शाखाओं वाली शर्तों के लॉजिक को सरल बनाने में मदद करती है।
