# Level 7 — Binary Search on Answer (অনুমানের খেলা, অর্ধেক করে বাদ)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> ছোটবেলার number guessing game মনে আছে? "1 থেকে 100-এর মধ্যে একটা সংখ্যা ভেবেছি" — তুমি 50 বলো, "বড়" শুনলে নিচের অর্ধেক পুরোটা বাদ। 7টা প্রশ্নেই 100-এর যেকোনো সংখ্যা ধরা পড়ে। এই level-এ শিখবে সেই খেলাটা শুধু sorted array-তে না — **উত্তরের উপরেই** খেলতে: "উত্তরটা কি 50 হতে পারে?" জিজ্ঞেস করে করে অর্ধেক জগৎ বাদ দিতে।

## এই level এ কী শিখবে?

মূল idea গুলো:

- **Binary search-এর হৃদয়** — প্রতি প্রশ্নে search space অর্ধেক; lo/hi-এর invariant ("উত্তর সবসময় [lo, hi]-এর ভেতরে") ধরে রাখা
- **Lower bound vs upper bound** — প্রথম ≥ x আর প্রথম > x; Python-এর `bisect_left` / `bisect_right`
- **Binary Search on Answer (BSoA)** — উত্তর guess করো + একটা **feasibility check** লেখো; F F F T T T-এর monotonic সিঁড়ি
- **`while lo < hi` template** — overflow-হীন, infinite-loop-হীন একটা নির্ভরযোগ্য কাঠামো
- **Minimize ঘরানা** — Koko (speed → সময়), ships (capacity → দিন), pages (max load → সম্ভব কিনা)
- **Maximize ঘরানা** — aggressive cows: minimum gap যত বড় সম্ভব (সিঁড়িটা উল্টো: T T T F F F)
- **Counting দিয়ে check** — multiplication table-এ "x-এর চেয়ে ছোট-সমান কয়টা" প্রতি row-তে `min(x // i, n)`
- **Partition search** — median of two sorted arrays-এর sketch: কাটার জায়গাটাই search করা

## কেন এই level দরকার?

**Competitive programming (CP) এ:** "answer monotonic হলে binary search করো" — এটা CP-র অন্যতম মৌলিক reflex। Codeforces Div 2 C/D-তে BSoA নিয়মিত মুখ; CSES-এ Factory Machines, Array Division-এর মতো পুরো একটা ঘরানা আছে। Constraint-এ `10^18` দেখলেই অভিজ্ঞ চোখ বলে: "loop না, binary search"।

**Interview এ:** Koko Eating Bananas, Capacity to Ship Packages, Split Array Largest Sum — এগুলো common interview pattern; "minimize the maximum" শুনলেই BSoA মাথায় আসা উচিত। আর Median of Two Sorted Arrays তো বহু বছর ধরেই hard-interview-এর পোস্টার সমস্যা।

**পরের ধাপে:** binary search on real numbers (precision সহ), parametric search, ternary search — সবার ভিত এখানেই। আর "guess + check" এই decomposition-চিন্তা greedy আর DP-র feasibility check-এও ফিরবে।

## Prerequisites

- [Level 0: Absolute Basics](../00-absolute-basics/README.md) — loop, integer division (`//`)
- [Level 6: Two Pointers ও Sliding Window](../06-two-pointers-sliding-window-math/README.md) — "search space কমানো"-র চিন্তা; এখানে সেটাই অর্ধেক-অর্ধেক রূপে
- log-এর প্রাথমিক ধারণা — "কতবার অর্ধেক করলে 1-এ নামে" = log₂(n); O(n log n) পড়তে পারা

## Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

- [ ] `while lo < hi` template-এ lo/hi-এর invariant কী — প্রতি লাইনে বলতে পারি
- [ ] `mid = (lo + hi) // 2` কখন lo-এর দিকে ঝোঁকে, আর সেটা কখন infinite loop বাঁচায় — জানি
- [ ] Lower bound (প্রথম ≥ x) আর upper bound (প্রথম > x)-এর পার্থক্য একটা উদাহরণে দেখাতে পারি
- [ ] `bisect_left` / `bisect_right` কোনটা কী দেয় — না দেখে বলতে পারি
- [ ] BSoA-র দুটো উপাদান (answer space + feasibility check) আলাদা করে চিনতে পারি
- [ ] F F F T T T-এর monotonic সিঁড়ি কেন জরুরি — counter-example সহ বুঝি
- [ ] Koko-তে check(speed) কেন monotonic — ব্যাখ্যা করতে পারি (speed বাড়লে সময় কমে)
- [ ] Minimize আর maximize — দুই ঘরানায় lo/hi কোন দিকে চাপে, গুলিয়ে ফেলি না
- [ ] Answer space-এর সীমা (lo, hi) ঠিক করার নিয়ম জানি — feasible একটা hi নিশ্চিত করা
- [ ] Multiplication table-এ count ≤ x-এর formula `min(x // i, n)` কোথা থেকে আসে — বুঝি

## Problem list

মোট 12টা problem — 5টা Easy, 4টা Medium, 3টা Hard।

### Easy

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 091 | [Basic Binary Search](problems/091-basic-binary-search.md) | halving | LeetCode Binary Search — <https://leetcode.com/problems/binary-search/> |
| 092 | [Lower Bound](problems/092-lower-bound.md) | first ≥ x | Classic (Python bisect_left) |
| 093 | [Upper Bound](problems/093-upper-bound.md) | first > x | Classic (Python bisect_right) |
| 094 | [Search Insert Position](problems/094-search-insert-position.md) | lower bound apply | LeetCode — <https://leetcode.com/problems/search-insert-position/> |
| 095 | [Square Root using Binary Search](problems/095-square-root-binary-search.md) | first BSoA | LeetCode Sqrt(x) — <https://leetcode.com/problems/sqrtx/> |

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 096 | [Minimum Eating Speed](problems/096-minimum-eating-speed.md) | BSoA minimize | LeetCode Koko Eating Bananas — <https://leetcode.com/problems/koko-eating-bananas/> |
| 097 | [Ship Packages Within D Days](problems/097-ship-packages-d-days.md) | BSoA minimize | LeetCode — <https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/> |
| 098 | [Aggressive Cows](problems/098-aggressive-cows.md) | BSoA maximize | SPOJ AGGRCOW — <https://www.spoj.com/problems/AGGRCOW/> |
| 099 | [Allocate Minimum Pages](problems/099-allocate-minimum-pages.md) | minimize max load | Classic interview problem (book allocation) |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 100 | [Split Array Largest Sum](problems/100-split-array-largest-sum.md) | minimize max load | LeetCode — <https://leetcode.com/problems/split-array-largest-sum/> |
| 101 | [Median of Two Sorted Arrays](problems/101-median-two-sorted-arrays.md) | partition search | LeetCode — <https://leetcode.com/problems/median-of-two-sorted-arrays/> |
| 102 | [Kth Smallest in Multiplication Table](problems/102-kth-smallest-multiplication-table.md) | BSoA + counting | LeetCode — <https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/> (related: CSES Factory Machines — <https://cses.fi/problemset/task/1620>) |

পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে।

## Recommended order

1. **091** — guessing game টা array-তে; lo/hi-এর invariant এখানেই পাকা করো
2. **092 → 093** — lower আর upper bound পাশাপাশি; `bisect` দিয়ে যাচাই
3. **094** — lower bound-এর প্রথম প্রয়োগ; নতুন কিছু না, চেনা জিনিস নতুন পোশাকে
4. **095** — প্রথম BSoA! Array নেই, তবু binary search — এই মোড়টাই level-এর হৃদয়
5. **096 → 097** — minimize ঘরানা দুই স্বাদে: speed আর capacity
6. **098** — এবার maximize; সিঁড়িটা উল্টে যায়, মাথাও একটু উল্টাতে হয়
7. **099 → 100** — "minimize the maximum" জোড়া; 099 হলো 100-এরই classic রূপ
8. **102** — check function-টা নিজেই একটা counting problem; BSoA-র full power
9. **101** — সবশেষে partition search; এটা আলাদা জাত, সময় নিয়ে বোঝো

## Common mistakes (সাধারণ ভুল)

1. **Infinite loop: `lo = mid` আর নিচ-ঝোঁকা mid একসাথে** — `lo = mid` করতে হলে `mid = (lo + hi + 1) // 2` (উপরে ঝোঁকানো) লাগে, নইলে `hi - lo == 1` অবস্থায় চিরঘূর্ণন। নিয়ম: কোন pointer mid-এ আসে দেখো, mid-এর ঝোঁক সেই অনুযায়ী।
2. **`hi = mid - 1` vs `hi = mid` গুলিয়ে ফেলা** — mid নিজে এখনো উত্তর হতে **পারলে** তাকে বাদ দিও না (`hi = mid`); নিশ্চিত বাদ হলে `mid - 1`। Invariant-টা মুখে বলো: "[lo, hi]-তে উত্তর আছে" — প্রতিটা update সেটা রক্ষা করছে কি?
3. **Feasibility check monotonic কিনা যাচাই না করা** — F আর T এলোমেলো হলে binary search মিথ্যা বলে। Check লেখার আগে এক লাইনে নিজেকে বোঝাও: "guess বাড়ালে check-এর ফল কোন দিকে যায়, আর কেন?"
4. **Answer space-এর সীমা ভুল** — Koko-তে `hi = max(piles)`-এর কমে শুরু করলে উত্তরটাই range-এর বাইরে পড়তে পারে; `lo = 0` দিলে check-এ division by zero। `lo = 1, hi = max(piles)` — hi সবসময় একটা feasible মান হওয়া চাই।
5. **Check-এ ceiling division ভুল** — "pile / speed-এর ceiling" দরকার, `pile // speed` না। Python idiom: `(pile + speed - 1) // speed` বা `-(-pile // speed)`। Floor দিলে সময় কম গুনে ভুল speed-কে feasible বলবে।
6. **Minimize আর maximize-এর move উল্টে ফেলা** — minimize-এ check পাশ করলে `hi = mid` (আরো ছোট চেষ্টা); maximize-এ পাশ করলে `lo = mid` (আরো বড় চেষ্টা)। সিঁড়ির ছবি এঁকে নাও — কোন পাশে T জমে আছে।
7. **`bisect_left` আর `bisect_right` অদলবদল** — দুটোই duplicate-এ আলাদা উত্তর দেয়: `[1, 3, 3, 5]`-এ x=3 → left দেয় 1, right দেয় 3। গোনা-জাতীয় কাজে (কয়টা < x, কয়টা ≤ x) ভুলটা নিঃশব্দে wrong answer দেয়।
8. **0-আকারের সমস্যায় edge case** — খালি array, `k` সবচেয়ে বড়/ছোট, এক element — binary search-এর bug-রা এখানেই লুকায়। প্রতিটা solution-এ n=1 কেস হাতে চালাও।

## পরের level এ যাওয়ার আগে checklist

- [ ] 091-এর dry run টেবিল (step | lo | hi | mid | সিদ্ধান্ত) হাতে বানিয়েছি
- [ ] `[1, 3, 3, 5]`-এ x=3 দিয়ে bisect_left আর bisect_right-এর উত্তর হাতে বের করে Python-এ মিলিয়েছি
- [ ] 095-এ "array ছাড়া binary search" — এই মোড়টা নিজের ভাষায় এক প্যারায় লিখেছি
- [ ] 096-এর check(speed) আলাদা function হিসেবে লিখে আলাদাভাবে test করেছি
- [ ] একটা minimize (096/097) আর একটা maximize (098) — দুটোর সিঁড়ির ছবি পাশাপাশি এঁকেছি
- [ ] "অর্ধেক করে বাদ" কেন O(log n) — 10^18 থেকে কয় ধাপে 1-এ নামে, হিসাব করেছি (≈ 60)

সব টিক দিতে পারলে — চলো [Level 8: Greedy Math Tricks](../08-greedy-math-tricks/README.md)-এ। সেখানে guess-ও না, window-ও না — প্রতি ধাপে স্রেফ সবচেয়ে লোভী choice, আর তার পেছনের প্রমাণ।

## Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।