क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य
द्विआधारी खोज को पुनरावृत्त और पुनरावर्ती दोनों तरीकों से लागू कीजिए, lo/hi सीमाओं में सीमा से एक अधिक या कम होने वाले विवरण सही कीजिए और किनारी इनपुट से शुद्धता जाँचिए।
क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
बाइनरी खोज क्यों महत्वपूर्ण है
बाइनरी खोज प्रत्येक चरण में खोज-क्षेत्र को आधा करके O(n) रैखिक स्कैन को O(log n) में बदल देती है। दस लाख तत्वों वाले ऐरे में रैखिक स्कैन के लिए 1,000,000 तक तुलनाएँ आवश्यक हो सकती हैं, लेकिन बाइनरी खोज के लिए अधिकतम 20 तुलनाएँ पर्याप्त होती हैं। यही दक्षता इसे कोडिंग साक्षात्कारों में सबसे अधिक परीक्षित एल्गोरिदमों में से एक बनाती है।
मुख्य विचार यह है कि एक क्रमबद्ध ऐरे आपको एक ही तुलना के बाद यह तय करने देता है कि बचे हुए डेटा के किस आधे हिस्से को पूरी तरह हटाना है।
बाएँ, मध्य और दाएँ का ढाँचा
बाइनरी खोज तीन सूचकांक-पॉइंटर का उपयोग करती है: lo (बायाँ सिरा), hi (दायाँ सिरा) और mid (मध्यबिंदु)। प्रत्येक पुनरावृत्ति में आप mid = (lo + hi) // 2 निकालते हैं और लक्ष्य की तुलना arr[mid] से करते हैं। यदि लक्ष्य छोटा है, तो hi = mid - 1 कीजिए; यदि बड़ा है, तो lo = mid + 1 कीजिए; यदि बराबर है, तो लक्ष्य मिल गया।
लूप तब तक चलता है जब तक lo <= hi हो। लक्ष्य न मिलने पर लूप समाप्त होने के बाद -1 लौटाइए।
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1mid में पूर्णांक अतिप्रवाह से बचना
mid = (lo + hi) // 2 व्यंजक निश्चित-चौड़ाई वाले पूर्णांकों वाली भाषाओं (Java, C++) में पूर्णांक अतिप्रवाह पैदा कर सकता है। Python के पूर्णांक मनमानी सटीकता वाले होते हैं, इसलिए अतिप्रवाह कभी नहीं होता, लेकिन साक्षात्कारकर्ता फिर भी आपसे सुरक्षित विकल्प जानने की अपेक्षा करते हैं: mid = lo + (hi - lo) // 2।
यह रूप वही मध्यबिंदु निकालता है, लेकिन पहले दोनों पॉइंटरों को जोड़ने के बजाय केवल आधी दूरी को lo में जोड़ता है। साक्षात्कार में इसका उल्लेख करना निम्न-स्तरीय चिंताओं के प्रति आपकी जागरूकता दिखाता है।
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # Trueसमावेशी और बहिष्कारी सीमाएँ
बाइनरी खोज के सबसे पेचीदा हिस्सों में से एक यह तय करना है कि hi अंतिम मान्य सूचकांक (समावेशी, hi = len(arr) - 1) को दर्शाता है या अंत के ठीक बाद की स्थिति (बहिष्कारी, hi = len(arr)) को। अलग-अलग परंपराओं के लिए अलग लूप शर्तें और सीमा अद्यतन आवश्यक होते हैं।
समावेशी सीमाओं के साथ while lo <= hi का उपयोग कीजिए और hi = mid - 1 अद्यतन कीजिए। बहिष्कारी सीमाओं के साथ while lo < hi का उपयोग कीजिए और hi = mid अद्यतन कीजिए। दोनों परंपराओं को मिलाना बाइनरी खोज के कार्यान्वयनों में त्रुटियों का सबसे सामान्य स्रोत है।
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2पुनरावर्ती बाइनरी खोज
बाइनरी खोज को पुनरावर्ती रूप से लिखा जा सकता है, जिसमें अद्यतन lo और hi सीमाएँ कॉल-स्टैक के माध्यम से भेजी जाती हैं। प्रत्येक पुनरावर्ती कॉल खोज-क्षेत्र को आधा कर देती है, इसलिए गहराई O(log n) होती है। मूल स्थिति तब होती है जब lo > hi (नहीं मिला) या arr[mid] == target (मिल गया) हो।
वास्तविक उपयोग के कोड में पुनरावृत्तिमूलक संस्करण को प्राथमिकता दी जाती है, क्योंकि इससे स्टैक-फ़्रेम का अतिरिक्त खर्च बचता है; हालांकि, व्हाइटबोर्ड पर पुनरावर्ती संस्करण विभाजित करो और जीतो की संरचना को अधिक स्पष्ट रूप से दिखाता है।
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4सीमांत स्थितियाँ: खाली ऐरे और एकल तत्व
विश्वसनीय बाइनरी खोज को बिना क्रैश हुए सीमांत स्थितियों को सँभालना चाहिए। तीन सबसे सामान्य स्थितियाँ हैं: खाली ऐरे (लूप कभी नहीं चलता और -1 सही रूप से लौटता है), एक तत्व वाला ऐरे (mid, lo और hi के बराबर होता है, इसलिए एक तुलना पर्याप्त है), और सीमा से बाहर के लक्ष्य (lo अंततः hi से बड़ा हो जाता है और -1 लौटता है)।
साक्षात्कार में आगे के प्रश्नों पर जाने से पहले अपने कार्यान्वयन को इन मानों के साथ हमेशा जाँचिए।
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)समय और स्थान जटिलता
बाइनरी खोज की O(log n) समय जटिलता होती है, क्योंकि प्रत्येक तुलना खोज-क्षेत्र को आधा कर देती है। k तुलनाओं के बाद शेष क्षेत्र n/2^k होता है; खोज तब समाप्त होती है जब यह 1 तक पहुँचता है, इसलिए k = log₂ n।
पुनरावृत्तिमूलक संस्करण की स्थान जटिलता O(1) होती है (केवल तीन पूर्णांक चर), जबकि पुनरावर्ती संस्करण की O(log n) होती है, क्योंकि कॉल-स्टैक की गहराई उतनी होती है। साक्षात्कार में हमेशा दोनों जटिलताएँ बताइए और स्थान सीमित होने पर पुनरावृत्तिमूलक रूप को प्राथमिकता दीजिए।
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')सटीक मिलान और सीमा की खोज
पारंपरिक बाइनरी खोज वह कोई भी सूचकांक लौटाती है जहाँ लक्ष्य मौजूद हो। लेकिन साक्षात्कार की कई समस्याएँ लक्ष्य के पहले या अंतिम प्रकट होने की स्थिति पूछती हैं। इनके लिए मिलान मिल जाने के बाद भी खोज जारी रखनी होती है—तुरंत लौटने के बजाय सीमा को संकुचित करके आगे बढ़ते रहिए।
पहला प्रकट होना खोजते समय, arr[mid] == target मिलने के बाद mid को संभावित उत्तर के रूप में दर्ज कीजिए और hi = mid - 1 रखिए। अंतिम प्रकट होने के लिए lo = mid + 1 रखिए।
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1Python के bisect मॉड्यूल का उपयोग
Python की मानक लाइब्रेरी वास्तविक उपयोग के लिए तैयार बाइनरी खोज हेतु bisect.bisect_left(arr, x) और bisect.bisect_right(arr, x) उपलब्ध कराती है। bisect_left वह सबसे बायाँ सूचकांक लौटाता है जहाँ x को ऐरे को क्रमबद्ध बनाए रखते हुए डाला जा सकता है; प्रभावी रूप से यह वह पहली स्थिति खोजता है जहाँ arr[i] >= x हो।
साक्षात्कारकर्ता आपको bisect का उपयोग करने की अनुमति दे सकते हैं; पहले हमेशा इसकी पुष्टि कीजिए। यह जानना फिर भी आवश्यक है कि यह अंदरूनी रूप से कैसे काम करता है (यह O(log n) बाइनरी खोज है)।
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # Trueबाइनरी खोज की सामान्य कमियाँ
साक्षात्कारों में बाइनरी खोज की अधिकांश त्रुटियाँ तीन गलतियों के कारण होती हैं। पहली, गलत लूप शर्त: समावेशी सीमाओं के साथ <= के बजाय < का उपयोग करने पर अंतिम बचा हुआ तत्व छूट जाता है। दूसरी, गलत सीमा अद्यतन: +1 या -1 भूलने पर lo == hi होने पर अनंत लूप बन जाता है। तीसरी, अक्रमबद्ध ऐरे पर काम करना: बाइनरी खोज केवल क्रमबद्ध डेटा पर सही होती है।
कोई भी बाइनरी खोज लिखने से पहले ज़ोर से कहिए: 'ऐरे क्रमबद्ध है, मेरी सीमाएँ समावेशी हैं और मेरा लूप तब तक चलता है जब तक lo <= hi हो।'
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)बाइनरी खोज के लिए साक्षात्कार सुझाव
जब आपको क्रमबद्ध ऐरे, एकदिश रूप से बढ़ते फलन या ऐसे खोज-क्षेत्र की समस्या दिखे जिसे आधा किया जा सकता हो, तो तुरंत बाइनरी खोज पर विचार कीजिए। साक्षात्कार में अपनी सोच स्पष्ट करते हुए कहिए: 'ऐरे क्रमबद्ध है, इसलिए प्रत्येक तुलना में मैं आधे तत्व हटा सकता हूँ और O(log n) समय प्राप्त कर सकता हूँ।'
अपने समाधान को कम-से-कम तीन मानों पर हमेशा जाँचिए: शुरुआत का मान, अंत का मान और ऐसा मान जो मौजूद न हो। पूछे जाने से पहले ही जटिलता बताना—'समय O(log n), स्थान O(1)'—मजबूत बुनियादी समझ का संकेत देता है।
त्वरित जाँच
इस पाठ में Data Structures & Algorithms — Coding Interview Prep की अवधारणाओं की अपनी समझ जाँचिए।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: बाइनरी खोज प्रत्येक चरण में खोज-क्षेत्र को आधा करके O(log n) समय लेती है, समावेशी सीमा परंपरा में lo <= hi का उपयोग होता है और lo = mid+1 तथा hi = mid-1 से अद्यतन किया जाता है, और पहला या अंतिम प्रकट होना खोजने के लिए मिलान मिलने के बाद तुरंत लौटने के बजाय खोज जारी रखनी होती है। अब हम जानेंगे कि बाइनरी खोज घुमाए हुए और अक्रमबद्ध ऐरे तक कैसे विस्तारित होती है।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” पाठ निःशुल्क है?
हाँ—“क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” में मैं क्या सीखूँगा?
द्विआधारी खोज को पुनरावृत्त और पुनरावर्ती दोनों तरीकों से लागू कीजिए, lo/hi सीमाओं में सीमा से एक अधिक या कम होने वाले विवरण सही कीजिए और किनारी इनपुट से शुद्धता जाँचिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य
- घुमाए गए और अव्यवस्थित ऐरे में द्विआधारी खोज
- निचली सीमा और ऊपरी सीमा
- उत्तर-स्थान पर द्विआधारी खोज