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