अपर बाउंड
एक क्रमबद्ध (sorted)
n तत्वों वाले array को दिया गया है, और आपको q क्वेरी का जवाब देना है। प्रत्येक क्वेरी इस प्रश्न से जुड़ी है: “दी गई सूची में x से बड़ा पहला नंबर कौन सा है?”इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n (2 ≤ n ≤ ) और q (1 ≤ q ≤ ) दिए जाते हैं।अगली पंक्ति में क्रमबद्ध रूप से रखे गए
n अंतरालयुक्त पूर्णांक ( ≤ ≤ ) दिए जाते हैं, जो बढ़ते क्रम में हैं।अंतिम पंक्ति में
q अंतरालयुक्त क्वेरी ( ≤ < ) दी जाती हैं।आउटपुट
प्रोग्राम को
q पंक्तियों में क्वेरी का उत्तर देना चाहिए। प्रत्येक पंक्ति में संबंधित क्वेरी का परिणाम प्रिंट करें।उदाहरण
Input | Output |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
संकेत
बाइनरी सर्च के पारंपरिक कार्यान्वयन में हम
[l; r) रेंज पर विचार करते हैं, जहाँ l इनक्लूसिव (शामिल) रहता है और r एक्सक्लूसिव (शामिल नहीं) रहता है। कुछ स्थितियों में आपको (l; r] जैसी रेंज की आवश्यकता हो सकती है—यानी l को बाहर रखना और r को शामिल करना। इसके लिए l, r और mid को कैल्कुलेट करने के तरीके में कुछ बदलाव करने पड़ सकते हैं।Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB