द्विआधारी खोज (Binary Search)
कल्पना कीजिए कि हमने दुनिया भर की सभी इमारतों की ऊँचाइयों को बढ़ते क्रम में लिख लिया है। इस तरह सूची का पहला तत्व दुनिया की सबसे छोटी इमारत होगी और आख़िरी तत्व सबसे ऊँची इमारत। अब हम एक खेल खेलते हैं जिसमें हमें किसी इमारत की ऊँचाई एक क्वेरी के रूप में दी जाती है, और हमें उस इमारत का सूचकांक (इंडेक्स) बताना होता है। यदि ऐसी कोई इमारत ही न हो जिसकी ऊँचाई क्वेरी में माँगी गई हो, तो हमें -1 लौटाना होता है।
एक सरल (naive) तरीक़ा यह होगा कि हम एक
for लूप चलाएँ और सूची के प्रत्येक तत्व से गुज़रकर उसे क्वेरी से मिलाएँ। यदि सूची में n तत्व हैं, तो बदतर स्थिति (worst case) में हर क्वेरी के लिए हमें n जाँचें करनी होंगी:h = [...] # सभी इमारतों की ऊँचाइयाँ बढ़ते क्रम में
q = int(input()) # क्वेरी में माँगी गई ऊँचाई
for i, height in enumerate(h):
if height == q: # अगर हमें वह इमारत मिलती है
print(i) # इंडेक्स छापें
break # और रुक जाएँ
else: # अगर ऊँचाई q वाली इमारत नहीं मिली (else = nobreak)
print(-1) # संकेत देने के लिए -1 छापें कि नहीं मिलालेकिन क्योंकि यह सूची बढ़ते क्रम में सॉर्टेड है, हम बहुत-सी ग़ैरज़रूरी जाँचें कर रहे हैं। प्रत्येक तत्व को शुरू से जाँचने के बजाय, हम कुछ चरणों को छोड़कर सीधे सही ऊँचाई तक तेज़ी से पहुँच सकते हैं।
चूँकि ऐरे बढ़ते क्रम में व्यवस्थित है, एक बेहतर तरीक़ा यह है कि हम सबसे पहले बीच वाले तत्व को देखें। अगर यह तत्व
q से छोटा है, तो बाएँ तरफ़ के पूरे हिस्से को हटा दें और सिर्फ़ दाएँ हिस्से पर ध्यान दें। यदि यह q से बड़ा है, तो दाएँ हिस्से को हटा दें और सिर्फ़ बाएँ हिस्से पर ध्यान दें। बीच वाले तत्व को देखकर ग़ैरज़रूरी हिस्सा हटाते रहने की यही पद्धति द्विआधारी खोज (Binary Search) कहलाती है:h = [...] # सभी इमारतों की ऊँचाइयाँ बढ़ते क्रम में
q = int(input()) # क्वेरी में माँगी गई ऊँचाई
l, r = 0, len(h) # जवाब हमेशा [l; r) के बीच में होगा। ध्यान दें कि r इनक्लूसिव नहीं है
while r - l > 1: # विचार करने के लिए कम से कम एक तत्व है
mid = (l + r) // 2 # बीच वाला इंडेक्स लें
if h[mid] > q: # h[mid] > q => दायाँ हिस्सा छोड़ दें
r = mid
else: # h[mid] <= q => बायाँ हिस्सा छोड़ दें
l = mid
# अंत में h[l] को q के बराबर होना चाहिए
print(l if h[l] == q else -1)मान लीजिए हमारे पास इमारतों की ऊँचाइयों का एक ऐरे
h = [20, 22, 23, 23, 34, 49, 52, 55, 58] है, और हम इमारत की ऊँचाई 49 वाले इंडेक्स को ढूँढना चाहते हैं।इस एल्गोरिथ्म के साथ, हम कई चक्रों (iterations) से गुज़रेंगे:
mid = (0 + 9) // 2 = 4⇒h[4] = 34≤49⇒ हम बायाँ हिस्सा छोड़ देते हैं.
mid = (4 + 9) // 2 = 6⇒h[6] = 52>49⇒ हम दायाँ हिस्सा छोड़ देते हैं.
mid = (4 + 6) // 2 = 5⇒h[5] = 49≤49⇒ हम बायाँ हिस्सा छोड़ देते हैं.
l = 5,r = 6⇒r - l == 1⇒ while लूप समाप्त हो जाता है और हम 5 को प्रिंट करते हैं क्योंकिh[5] = 49।
यह छोटा सा उदाहरण देखने में उतना बड़ा अनुकूलन नहीं लगता, लेकिन 10 अरब इमारतों की कल्पना कीजिए। यदि हम हर एक तत्व पर क्रमानुसार जाँच करें, तो बदतर स्थिति में 10 अरब बार जाँच करनी होगी। जबकि हर बार ऐरे को दो भागों में विभाजित करके ग़ैरज़रूरी हिस्से को हटाने पर, प्रदर्शन में काफ़ी सुधार होता है। आइए देखें कि 10 अरब तत्वों की स्थिति में, जब हम ऐरे को हर बार आधा करते हैं, तो कितने चक्र (iterations) में जवाब तक पहुँचेंगे:
स्पॉइलर: यह केवल 32 चक्र हैं, 10 अरब की जगह
- 10,000,000,000 / 2 = 5,000,000,000
- 5,000,000,000 / 2 = 2,500,000,000
- 1250000000 / 2 = 625000000
- 625000000 / 2 = 312500000
- 312500000 / 2 = 156250000
- 156250000 / 2 = 78125000
- 78125000 / 2 = 39062500
- 39062500 / 2 = 19531250
- 19531250 / 2 = 9765625
- 9765625 / 2 = 4882812
- 4882812 / 2 = 2441406
- 2441406 / 2 = 1220703
- 1220703 / 2 = 610351
- 610351 / 2 = 305175
- 305175 / 2 = 152587
- 152587 / 2 = 76293
- 76293 / 2 = 38146
- 38146 / 2 = 19073
- 19073 / 2 = 9536
- 9536 / 2 = 4768
- 4768 / 2 = 2384
- 2384 / 2 = 1192
- 1192 / 2 = 596
- 596 / 2 = 298
- 298 / 2 = 149
- 149 / 2 = 74
- 74 / 2 = 37
- 37 / 2 = 18
- 18 / 2 = 9
- 9 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
तो सोचिए, यदि कोई एल्गोरिथ्म 10 अरब तत्वों की सूची में रेखीय खोज (linear search) करता है और हर तत्व की जाँच करने में 1 सेकंड लेता है, तो उसे पूरा होने में क़रीब 317 साल लग जाएँगे। वहीं द्विआधारी खोज (Binary Search) करने में सिर्फ़ 32 सेकंड लगेंगे!
यही अंतर है ऑपरेशनों और ऑपरेशनों के बीच।
चुनौती
आपको 1 से 4 तक के
n GPA दिए गए हैं (1 सबसे कम ग्रेड है और 4 सबसे अच्छा)। साथ ही, कई न्यूनतम थ्रेशहोल्ड दिए गए हैं। आपको यह बताना है कि कितने लोग अगले ग्रेड में पास होंगे, यह मानते हुए कि किसी दिए गए थ्रेशहोल्ड और उससे अधिक GPA वाले सभी लोग पास माने जाते हैं।इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक
n (1 ≤ n ≤ ) होता है, जो छात्रों की संख्या दर्शाता है।अगली पंक्ति में
n फ्लोटिंग बिंदु संख्या होती हैं, जो छात्रों के GPA को बढ़ते क्रम में दिखाती हैं (1 ≤ ≤ 4)।तीसरी पंक्ति में एक पूर्णांक
q (1 ≤ q ≤ ) होता है, जो थ्रेशहोल्ड की संख्या दर्शाता है।इनपुट की अंतिम पंक्ति में
q फ्लोटिंग बिंदु संख्या होती हैं, जो पास होने के लिए न्यूनतम थ्रेशहोल्ड (1 ≤ ≤ 4) को दर्शाती हैं।आउटपुट
प्रोग्राम को
q पंक्तियाँ प्रिंट करनी चाहिए। पंक्ति i में यह दर्शाना चाहिए कि थ्रेशहोल्ड के आधार पर कितने छात्र अगले ग्रेड में पास होते हैं।उदाहरण
इनपुट | आउटपुट |
10
1.1 1.2 1.4 1.7 2 3 3.3 3.5 3.8 3.8
5
3.7
3.8
1
1.5
2 | 2
2
10
7
6 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB