बाइनरी सर्च पैटर्न जो बार-बार आते हैं

बाइनरी सर्च एक ही चाल नहीं है। इंटरव्यू और प्रोडक्शन कोड में कुछ ही आकार दोहराते हैं: कोई मान ढूंढना, कोई सीमा ढूंढना, और ऐरे के बजाय उत्तर पर सर्च करना। ज्यादातर बग "लॉग एन भूल गया" नहीं होते। लूप इनवेरिएंट में ऑफ-बाय-वन गलतियां होती हैं।

यह पोस्ट वही छोटा नक्शा है जो मैं रखता हूं। पाइथन टेम्पलेट, हर आकार का मानसिक मॉडल, और वे जाल जो व्हाइटबोर्ड पर आधा घंटा खा जाते हैं।

---

एक विचार जो काफी है

आप एक रेंज [lo, hi] (या हाफ-ओपन [lo, hi)) रखते हैं जहां उत्तर अभी भी रहता है। हर कदम उस रेंज का लगभग आधा गिरा देता है। यह तभी चलता है जब:

१. सर्च स्थान किसी कुंजी से क्रमबद्ध हो (मान, या एक मोनोटोन प्रीडिकेट)।
२. आप ओ(१) या बेहतर में तय कर सकें कि उत्तर अभी किस आधे में है।
३. आपका लूप हर इटरेशन में सिकुड़े, और बाहर निकलते समय lo/hi ज्ञात अवस्था में हों।

अगर प्रीडिकेट मोनोटोन नहीं, बाइनरी सर्च गलत औजार है। मिड की कोई भी चतुर गणना गैर-मोनोटोन समस्या नहीं सुधारती।

---

पैटर्न १: क्लासिक खोज (सटीक मान)

सॉर्टेड ऐरे, target ढूंढो या गायब बताओ। हाफ-ओपन रेंज कुछ बाड़-खंभे दर्द बचाती है:

def binary_search(a: list[int], target: int) -> int:
    """Return index of target, or -1 if missing. a must be sorted ascending."""
    lo, hi = 0, len(a)  # search in [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

नोट:

• mid = lo + (hi - lo) // 2 निश्चित-चौड़ाई पूर्णांक वाली भाषाओं में ओवरफ्लो बचाता है। पाइथन में ज्यादातर स्टाइल है। फिर भी अच्छी आदत, जब इंटरव्यू सी++ या जावा में हो।
• मिस पर lo इंसर्शन पॉइंट है (पहला इंडेक्स जहां a[i] >= target अगर तुलनाएं < / >= रहीं)। अगले पैटर्न के लिए काम आता है।
• डुप्लिकेट: कोई मैच लौटाता है, सबसे बायां या दायां नहीं।

---

पैटर्न २: लोअर बाउंड और अपर बाउंड

लोअर बाउंड: पहला इंडेक्स i जहां a[i] >= target (या len(a) अगर हर तत्व छोटा है)।

अपर बाउंड: पहला इंडेक्स i जहां a[i] > target।

साथ में डुप्लिकेट के लिए पूरा बराबर-रेंज देते हैं, और सॉर्टेड सूची में "एक्स की गिनती" लॉग समय में।

def lower_bound(a: list[int], target: int) -> int:
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(a: list[int], target: int) -> int:
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def equal_range(a: list[int], target: int) -> tuple[int, int]:
    return lower_bound(a, target), upper_bound(a, target)

उदाहरण: a = [1, 2, 2, 2, 5], target = 2 → लोअर 1, अपर 4, गिनती 3।

सी++ में std::lower_bound / std::upper_bound हैं। पाइथन के bisect.bisect_left और bisect.bisect_right वही विचार हैं। इंटरव्यू में लूप खुद लिखो ताकि साबित हो कि इनवेरिएंट तुम्हारा है।

प्रोडक्शन उपयोग

• सॉर्टेड इवेंट लॉग: पहला टाइमस्टैम्प >= t0, पहला > t1।
• कीमत सीढ़ी या दर तालिका: वह सबसे छोटा स्तर जो मात्रा को कवर करे।
• डेडुप आईडी सूची: स्कैन के बिना सदस्यता और रेंज लंबाई।

---

पैटर्न ३: उत्तर-स्थान सर्च (उत्तर पर बाइनरी सर्च)

आप ऐरे इंडेक्स नहीं कर रहे। आप एक संख्या x (क्षमता, दिन, न्यूनतम अधिकतम-लोड, गति) अनुमान लगाते हैं और एक मोनोटोन जांच पूछते हैं: छोटे x पर feasible(x) झूठा, बड़े पर सच (या उलटा)। बाइनरी सर्च सबसे छोटा सच (या सबसे बड़ा झूठ) ढूंढती है।

"न्यूनतम x ऐसा कि feasible(x)" का ढांचा:

def min_feasible(lo: int, hi: int, feasible) -> int:
    """
    Assume feasible is False for values below the answer,
    True for values at and above. Search in [lo, hi].
    Returns the smallest x where feasible(x) is True.
    Precondition: feasible(hi) is True (or widen hi first).
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid          # mid works; try smaller
        else:
            lo = mid + 1      # mid fails; need larger
    return lo

क्लासिक इंटरव्यू आकार जो यहीं मैप होते हैं:

समस्या परिवार	x का अर्थ	feasible(x)
कोको खाना केले	खाने की गति	h घंटे में सारे ढेर खत्म
ऐरे स्प्लिट सबसे बड़ा योग	अनुमत अधिकतम सबऐरे योग	<= m भागों में बांट सकते हो
पैकेज भेजने की क्षमता	जहाज क्षमता	D दिनों में सब पैकेज
मिन मैक्स दूरी / आक्रामक गायें	न्यूनतम दूरी	k गायें उस गैप से रखो
n वस्तुएं बनाने का समय	बीता समय	मशीनें तब तक काफी बना चुकीं

कठिन हिस्सा बाइनरी सर्च नहीं। यह है:

१. मोनोटोनिसिटी साबित करना (गति ५ चली तो ६ भी चलेगी)।
२. बाउंड सेट करना (कोको-शैली में lo = एक ढेर का अधिकतम; hi = ढेरों का योग या सुरक्षित ऊपरी सीमा)।
३. feasible सही और अच्छे समय में लिखना (अक्सर प्रति जांच ओ(एन) → कुल ओ(एन लॉग आर))।

छोटा उदाहरण: न्यूनतम क्षमता

पैकेज वजन [1, 2, 3, 4, 5], दिन D = 3। क्रम बदले बिना भेजने की न्यूनतम क्षमता।

def can_ship(weights: list[int], days: int, cap: int) -> bool:
    used, load = 1, 0
    for w in weights:
        if w > cap:
            return False
        if load + w > cap:
            used += 1
            load = 0
        load += w
    return used <= days


def ship_within_days(weights: list[int], days: int) -> int:
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(weights, days, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

lo सबसे भारी पैकेज से शुरू (क्षमता उससे छोटी नहीं हो सकती)। hi है "सब एक दिन में"। लूप उस न्यूनतम क्षमता पर रुकता है जो अभी भी days में खत्म करे।

---

पैटर्न ४: घूमा हुआ सॉर्टेड ऐरे (फिर भी बाइनरी सर्च)

ऐरे सॉर्टेड था, फिर रोटेट हुआ: [4, 5, 6, 7, 0, 1, 2]। एक आधा हमेशा सॉर्टेड रहता है। सॉर्टेड आधे से target की तुलना करो और तय करो कौन सा पक्ष गिराएं।

def search_rotated(a: list[int], target: int) -> int:
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:  # left half sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # right half sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

डुप्लिकेट पर a[lo] <= a[mid] अस्पष्ट हो जाता है जब a[lo] == a[mid] == a[hi]। तब सबसे खराब स्थिति में एक सिरा रैखिक सिकोड़ना पड़ सकता है। इंटरव्यू में जोर से कहो; सीमा जानना दिखता है।

---

ऑफ-बाय-वन जाल जो सच में काटते हैं

ये सबसे आम बग हैं, मेरे भी।

बंद बनाम हाफ-ओपन

शैली	आरंभ	लूप	जब a[mid] < target	अन्यथा
हाफ-ओपन [lo, hi)	hi = n	while lo < hi	lo = mid + 1	hi = mid
बंद [lo, hi]	hi = n - 1	while lo <= hi	lo = mid + 1	hi = mid - 1

फ़ंक्शन बीच में शैलियां मिलाना क्लासिक अनंत लूप है: hi = mid के साथ while lo <= hi और lo == hi पर कोई प्रगति नहीं।

हर फ़ंक्शन में एक शैली चुनो और उसी पर रहो। मैं बाउंड के लिए हाफ-ओपन, और जब समस्या पाठ समावेशी इंडेक्स सोचे तो बंद रखता हूं।

mid = (lo + hi) // 2 से अनंत लूप

जब hi = lo + 1 और "दाईं ओर" शाखा पर lo = mid (न कि mid + 1) सेट करो, mid हमेशा lo रहता है। ठीक: या तो हाफ-ओपन में lo = mid + 1, या "अधिकतम" सर्च में lo = mid लिखते समय mid = lo + (hi - lo + 1) // 2 (ऊपर झुकाव)।

# Maximize: last True under a monotone predicate on [lo, hi]
def max_true(lo: int, hi: int, ok) -> int:
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # bias upward
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

खाली ऐरे और एक तत्व

हमेशा [], हिट और मिस के साथ [x], और दो तत्व आजमाओ। ढीले मिड अपडेट पहले इन्हीं आकारों पर टूटते हैं।

बाउंड पर पूर्णांक ओवरफ्लो

उत्तर-स्थान समस्याएं hi को 10**18 तक धकेल सकती हैं। सी++/जावा में lo + hi ओवरफ्लो करता है; lo + (hi - lo) / 2 पसंद करो। पाइथन में ठीक है, पर इंटरव्यूअर सुरक्षित रूप अभी भी नोट करते हैं।

प्रीडिकेट दिशा

"न्यूनतम क्षमता" के लिए, जब feasible(mid) सच हो तो hi = mid (मिड रखो)। झूठा हो तो lo = mid + 1। एक बार उलटा और ऐसी क्षमता लौटेगी जो काम न करे, या हमेशा लूप। कोड से पहले लूप ऊपर हिंदी वाक्य लिखो।

फ्लोटिंग पॉइंट बाइनरी सर्च

इंटरव्यू में कम, "सबसे छोटा अर्धव्यास" जैसी ज्यामितीय समस्याओं में आम। निश्चित इटरेशन गिनती (६०-१००) या hi - lo पर एप्सिलॉन। फ्लोट की तुलना == से मत करो। जब हो सके स्केल्ड इकाइयों पर पूर्णांक सर्च करो।

---

निर्णय चेकलिस्ट

mid = ... लिखने से पहले:

१. सर्च स्थान क्या है? ऐरे इंडेक्स, या संख्या रेखा पर उम्मीदवार उत्तर?
२. मोनोटोन क्या है? सॉर्टेड मान, या feasible(x) जो एक बार झूठ से सच होता है?
३. क्या लौटाओगे? कोई भी मैच, सबसे बायां, सबसे दायां, इंसर्शन पॉइंट, मिन सच, मैक्स सच?
४. हाफ-ओपन या बंद? सिर्फ एक शैली।
५. बाउंड? lo ० / अधिकतम(तत्व) से शुरू हो सकता है? hi एक्सक्लूसिव n, इंक्लूसिव n-1, या सिद्ध अधिकतम क्षमता?
६. खाली और किनारे खुशहाल पथ से पहले लिखे।

अगर (२) का जवाब नहीं दे सकते, रुक जाओ। रैखिक स्कैन या दूसरा एल्गोरिदम सही हो सकता है; बाइनरी सर्च नहीं।

---

प्रोडक्शन नोट (सिर्फ लीटकोड नहीं)

बाइनरी सर्च इंटरव्यू के बाहर भी दिखती है:

• कॉन्फ़िग / फ़ीचर रोलआउट: वह पहला बिल्ड आईडी ढूंढो जिसने मेट्रिक गिराई (क्रमबद्ध डिप्लॉय पर फ्लेक-जागरूक जांच)।
• ऑटोस्केलिंग थ्रेशोल्ड: समवर्तिता या बैच आकार पर बाइनरी सर्च जब तक विलंब एसएलओ टूटे।
• डेटाबेस / स्टोरेज: बी-ट्री लीफ सर्च वही विचार है; ऐप कोड शायद ही दोबारा लिखे, इनवेरिएंट एक ही है।
• गेम / सिम ट्यूनिंग: न्यूनतम समय कदम, अधिकतम लोड, स्पॉन दर जो बजट के अंदर रहे।

प्रोडक्शन में feasible अक्सर प्रयोग या लोड टेस्ट होता है, इसलिए इटरेशन गिनती मिड माइक्रो-ऑप्टिमाइज़ से ज्यादा मायने रखती है। फिर भी हर (lo, hi, mid, result) लॉग करो ताकि गैर-मोनोटोन मेट्रिक चुपचाप बकवास न लौटाए।

---

चीट शीट

लक्ष्य	टेम्पलेट
कोई भी बराबर	क्लासिक; मैच पर mid लौटाओ
पहला >= x	लोअर बाउंड; if a[mid] < x: lo = mid+1 else hi = mid
पहला > x	अपर बाउंड; if a[mid] <= x: lo = mid+1 else hi = mid
बराबर गिनती	upper - lower
मिन x जहां ok(x)	अगर ठीक: hi = mid वरना lo = mid+1
मैक्स x जहां ok(x)	mid ऊपर झुकाओ; अगर ठीक: lo = mid वरना hi = mid-1
घूमा ऐरे	सॉर्टेड आधा पहचानो; दूसरा हटाओ

इनवेरिएंट याद रखो, बारह समस्या नाम नहीं। जब लोअर/अपर बाउंड और उत्तर-स्थान सर्च मांसपेशी-स्मृति बन जाएं, लीटकोड के ज्यादातर "बाइनरी सर्च" टैग वही लूप हैं, बस feasible अलग।

---

अंत में

बाइनरी सर्च तब फेल होती है जब रेंज सिकुड़ती नहीं, प्रीडिकेट मोनोटोन नहीं, या बंद और हाफ-ओपन अपडेट मिल जाते हैं। ये तीन जकड़ लो, बाकी नामकरण है।

इस हफ्ते अगर एक ही अभ्यास करो: लोअर बाउंड और मिन-फ़ीज़िबल दो बार बिना देखे शुरू से लिखो, और खाली, एक-तत्व, और सब-डुप्लिकेट ऐरे पर चलाओ। इंटरव्यू और प्रोडक्शन जो असल में मांगते हैं, उसका ज्यादातर यही है।