🔍 धडा 08 — Binary search: क्रमाने लावलेली नोंदवही

📍 तुम्ही इथे आहात: 12 पैकी धडा 08 · पुढे: lesson-09-trees-heaps

📦 या ब्रँचमध्ये काय आहे

धडे 01–08. O(log n) ची चाल, प्रत्येकाकडून एकदा तरी चुकणारा loop, आणि उत्तरावर binary search करण्याची युक्ती.

dsa/algorithms.py — binary_search (index आणि steps परत करतो), linear_search
dsa/demo.py — search: 50,000 विद्यार्थी, मग locker च्या आकाराचा प्रश्न

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

नोंदवही क्रमाने लावलेली आहे. ती मधोमध उघडा: "Dipika" — तुमचे नाव आधी आहे की नंतर? चुकीचा अर्धा भाग फेकून द्या आणि उरलेला अर्धा मधोमध उघडा. पन्नास हजार नावांना जास्तीत जास्त सोळा नजरा लागतात; दहा लाखांना वीस. हीच युक्ती नोंदवही अजिबात नसलेल्या प्रश्नांचीही उत्तरे देते: "सगळ्या दप्तरांना पुरेल असा सर्वात लहान locker कोणता?" एक आकार करून पाहा — बसते? मग लहान करून पाहा; बसत नाही? मोठा करून पाहा. उत्तर वाढताना एकदाच उलटणारा कोणताही हो/नाही प्रश्न अशा प्रकारे शोधता येतो.

🗺️ आकृती

flowchart LR
  A["lo=0 · hi=49,999 · mid=24,999"] -->|"target bigger"| B["lo=25,000 · hi=49,999"] -->|"target smaller"| C["lo=25,000 · hi=37,499"] --> D["… 16 looks"]

❓ काय

पूर्वअट: sorted (किंवा monotonic). खर्च O(log n) वेळ, O(1) space.
Loop: lo, hi = 0, n-1; जोपर्यंत lo <= hi: mid = (lo+hi)//2; समान → सापडले; लहान → lo = mid+1; मोठे → hi = mid-1; ओलांडले → सापडले नाही.
प्रकार: पहिली/शेवटची occurrence, insertion point (bisect.bisect_left), उत्तरावर search (check pass होणारी सर्वात लहान value).
कामावर हे कुठे असते: bisect, database B-tree indexes (Database school L06), git bisect, version ranges, rate-limit thresholds.

🤔 का

O(1) नंतरची सर्वात स्वस्त गोष्ट O(log n) आहे, आणि त्याला फक्त क्रम लागतो. "scan पेक्षा चांगले करता येईल का?" याचा अर्धा भाग म्हणजे "हे sorted आहे का, किंवा होऊ शकते का?" answer-search प्रकार optimisation प्रश्नांचा एक पूर्ण वर्ग त्याच आठ ओळींनी सोडवतो.

🔧 कसे (या repo मध्ये)

binary_search आपले loops मोजतो; demo.py search त्याच 50,000 विद्यार्थ्यांवर त्याच्या 15 नजरांची linear search च्या 41,235 शी तुलना करतो, मग fits(cap) check वापरून locker capacities 1–240 वर binary search करतो.

🧪 करून पाहा

python3 dsa/demo.py search
python3 - <<'EOF'
import sys, bisect; sys.path.insert(0, "dsa"); from algorithms import binary_search
reg = [3, 7, 7, 7, 12, 20]
print(binary_search(reg, 12), binary_search(reg, 5))                 # (4, steps), (-1, steps)
print("first 7 at", bisect.bisect_left(reg, 7), "· insert 10 at", bisect.bisect_left(reg, 10))
# search on the answer: the first version where the tests fail
def fails(v): return v >= 137
lo, hi = 1, 1000
while lo < hi:
    mid = (lo + hi) // 2
    if fails(mid): hi = mid
    else: lo = mid + 1
print("first failing version:", lo, "found in ~10 checks")
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

Linear 41,235 नजरा विरुद्ध binary 15 (log₂ 50,000 ≈ 15.6); locker चे उत्तर 90 kg; तुमचा bisect पहिला 7 index 1 वर आणि 10 साठीचा insertion point index 4 वर print करतो; "first failing version" 137 आहे.

🏁 तुम्ही आत्ताच काय सिद्ध केले

तुम्ही binary search आठवणीतून लिहू शकता, नसलेली key हाताळू शकता, आणि हो/नाही प्रश्नाचे शोधता येणाऱ्या range मध्ये रूपांतर करू शकता.

⚠️ नेहमीच्या चुका

mid - 1 ऐवजी hi = mid (किंवा उलट) → अनंत loop किंवा सुटलेला element.
unsorted list मध्ये search करणे. ते शांतपणे निरर्थक उत्तर देते.
ठरलेल्या रुंदीचे ints असलेल्या भाषांमध्ये (lo + hi) मध्ये overflow; Python सुरक्षित आहे.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक database index lookup, प्रत्येक "या timestamp साठीचा config शोधा", प्रत्येक capacity-planning मधला "बसणारा सर्वात लहान instance" म्हणजे binary search — बहुतेक वेळा तुमच्यासाठी केलेला, कधीकधी नाही.

⏭️ पुढे

धडा 09 — trees आणि heaps: कॅटलॉगचा खण आणि व्यासपीठ.

🔍 Lesson 08 — Binary search: the sorted register

📍 You are here: Lesson 08 of 12 · Next: lesson-09-trees-heaps

📦 What's in this branch

Lessons 01–08. The O(log n) walk, the loop everyone gets wrong once, and the trick of binary-searching an answer.

dsa/algorithms.py — binary_search (returns index and steps), linear_search
dsa/demo.py — search: 50,000 pupils, then the locker-size question

🧒 Explain like I'm 5

The register is sorted. Open it in the middle: "Dipika" — is your name before or after? Throw the wrong half away and open the remaining half in the middle. Fifty thousand names take at most sixteen looks; a million take twenty. The same trick answers questions with no register at all: "what is the smallest locker that fits all the bags?" Try a size — does it fit? Then try smaller; doesn't? Try bigger. Any yes/no question that flips once as the answer grows can be searched this way.

🗺️ Diagram

flowchart LR
  A["lo=0 · hi=49,999 · mid=24,999"] -->|"target bigger"| B["lo=25,000 · hi=49,999"] -->|"target smaller"| C["lo=25,000 · hi=37,499"] --> D["… 16 looks"]

❓ What

Precondition: sorted (or monotonic). Cost O(log n) time, O(1) space.
The loop: lo, hi = 0, n-1; while lo <= hi: mid = (lo+hi)//2; equal → found; smaller → lo = mid+1; bigger → hi = mid-1; crossed → not found.
Variants: first/last occurrence, insertion point (bisect.bisect_left), search on the answer (the smallest value for which a check passes).
Where it lives at work: bisect, database B-tree indexes (Database school L06), git bisect, version ranges, rate-limit thresholds.

🤔 Why

O(log n) is the cheapest thing after O(1), and it only needs order. Half of "can we do better than a scan?" is "is it sorted, or could it be?" The answer-search variant solves a whole class of optimisation questions with the same eight lines.

🔧 How (in this repo)

binary_search counts its loops; demo.py search compares its 15 looks with linear search's 41,235 on the same 50,000 pupils, then binary-searches locker capacities 1–240 with a fits(cap) check.

🧪 Try it

python3 dsa/demo.py search
python3 - <<'EOF'
import sys, bisect; sys.path.insert(0, "dsa"); from algorithms import binary_search
reg = [3, 7, 7, 7, 12, 20]
print(binary_search(reg, 12), binary_search(reg, 5))                 # (4, steps), (-1, steps)
print("first 7 at", bisect.bisect_left(reg, 7), "· insert 10 at", bisect.bisect_left(reg, 10))
# search on the answer: the first version where the tests fail
def fails(v): return v >= 137
lo, hi = 1, 1000
while lo < hi:
    mid = (lo + hi) // 2
    if fails(mid): hi = mid
    else: lo = mid + 1
print("first failing version:", lo, "found in ~10 checks")
EOF

✅ Verify — what you should see

Linear 41,235 looks versus binary 15 (log₂ 50,000 ≈ 15.6); the locker answer is 90 kg; your bisect prints the first 7 at index 1 and the insertion point for 10 at index 4; the "first failing version" is 137.

🏁 What you just proved

You can write binary search from memory, handle the missing key, and turn a yes/no question into a searchable range.

⚠️ Common mistakes

hi = mid instead of mid - 1 (or vice versa) → infinite loop or a skipped element.
Searching an unsorted list. It returns nonsense quietly.
Overflow in (lo + hi) in languages with fixed-width ints; Python is safe.

🏭 Why this matters in production: every database index lookup, every "find the config for this timestamp", every capacity-planning "smallest instance that fits" is binary search — usually done for you, sometimes not.

⏭️ Next

Lesson 09 — trees & heaps: the catalogue drawer and the podium.

← Previoussorting Next →trees heaps

This page is the lesson's README from the lesson-08-binary-search branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.