बाइनरी सर्च

निर्देश

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

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

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

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

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

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

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

व्यवहार

टेस्ट केसों के लिए आपके हल का व्यवहार Julia में पहले से मौजूद searchsorted फंक्शनों जैसा होना चाहिए। इसका मतलब है कि ऐरे में मिले पहले मैचिंग एलिमेंट का इंडेक्स लौटाने के बजाय आप एक रेंज लौटाएँगे। इस रेंज की निचली सीमा ऐरे के पहले मैचिंग एलिमेंट का इंडेक्स होगी और ऊपरी सीमा ऐरे के अंतिम मैचिंग एलिमेंट का इंडेक्स होगी। लेकिन अपने हल को आसान बनाने के लिए आप यह मान सकते हैं कि लक्ष्य एलिमेंट कई बार नहीं आता, सिवाय बोनस टास्क के उस टेस्टसेट के, जिसमें एक ही एलिमेंट एक से अधिक बार आता है।

अगर खोजा जाने वाला एलिमेंट ऐरे में नहीं है, तो आपको एक खाली रेंज लौटानी होगी। इस रेंज की निचली सीमा वह इंडेक्स होगी जहाँ उस एलिमेंट को सॉर्ट किए गए ऐरे में डाला जा सकता है। खाली रेंज का मतलब ऐसी रेंज है जिसकी ऊपरी सीमा निचली सीमा से कम हो।

अधिक जानकारी के लिए searchsorted फंक्शन का डॉक्युमेंटेशन और उदाहरण पढ़िए:

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

बोनस टास्क

• अपने हल को बढ़ाकर उसमें by, lt और rev कीवर्ड आर्गुमेंट का सहयोग जोड़िए। यहाँ by ऐरे के सभी एलिमेंट पर लगने वाला रूपांतरण बताता है, lt एक तुलना बताता है, और rev बताता है कि ऐरे उलटे क्रम में लगा है या नहीं। जब ये पैरामीटर इस्तेमाल होते हैं, तो आपको यह मान लेना होगा कि ऐरे पहले ही इन पैरामीटर के हिसाब से सॉर्ट किया जा चुका है। अधिक जानकारी के लिए sort का डॉक्युमेंटेशन देखिए।
• ऐसे ऐरे का सहयोग कीजिए जिनमें लक्ष्य एलिमेंट कई बार आता हो (वह पहला और अंतिम इंडेक्स ढूँढिए जिन पर लक्ष्य एलिमेंट बराबर होता है)।

---

स्रोत

Wikipedia