DSA Interview Prep · पाठ

क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य

Q: क्या “क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” पाठ निःशुल्क है?

हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

Q: क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।

Q: “क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

Q: क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

द्विआधारी खोज को पुनरावृत्त और पुनरावर्ती दोनों तरीकों से लागू कीजिए, lo/hi सीमाओं में सीमा से एक अधिक या कम होने वाले विवरण सही कीजिए और किनारी इनपुट से शुद्धता जाँचिए।

पाठ 1, कुल 4 में से13 चरण

क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 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))  # -1

mid में पूर्णांक अतिप्रवाह से बचना

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))  # 1

Python के 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 से अद्यतन किया जाता है, और पहला या अंतिम प्रकट होना खोजने के लिए मिलान मिलने के बाद तुरंत लौटने के बजाय खोज जारी रखनी होती है। अब हम जानेंगे कि बाइनरी खोज घुमाए हुए और अक्रमबद्ध ऐरे तक कैसे विस्तारित होती है।

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 30
पाठ: 120

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” पाठ निःशुल्क है?

हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “क्लासिक द्विआधारी खोज: बायाँ, दायाँ, मध्य” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।