# Problems — Level 7: Binary Search on Answer

> এই folder-এ Level 7-এর 12টা problem-এর নোট আছে। প্রতিটার জন্য আলাদা `.md` file — নিজের ভাষায় problem বোঝা, F/T সিঁড়ির ছবি, lo/hi-এর dry run, code আর ভুল থেকে শেখা।

## কীভাবে problem গুলো use করবে?

প্রতিটা problem-এর note লেখা হয় [../../../templates/math-problem-note-template.md](../../../templates/math-problem-note-template.md) follow করে — ২০টা section-এর template: problem বোঝা → brute force → optimization → dry run → complexity → "ভবিষ্যতের আমাকে এক লাইনে কী বলব"। শুরুতে template-টা একবার পড়ে নাও।

নিয়মটা এই level-এ একটু বিশেষ:

1. Table থেকে problem নাও (recommended order [../README.md](../README.md)-তে)
2. BSoA problem-এ code-এর আগে তিনটা প্রশ্নের উত্তর লেখো: answer space কী? check(guess) কী? monotonic কেন? — তিনটার একটাও না পারলে আগে [../concept-notes.md](../concept-notes.md)-এ ফেরো
3. Dry run-এ lo | hi | mid | check-এর টেবিল হাতে বানাও — binary search-এর bug শুধু এখানেই ধরা পড়ে
4. নিজে সমাধান করার অগ্রগতি আলাদা খাতায় বা tracker-এ রাখো। “নোট আছে” কেবল ব্যাখ্যার উপস্থিতি বোঝায়।

## Tracker table

| # | Problem | Difficulty | Pattern | Inherits from | Source | Note file | নোটের অবস্থা |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 091 | Basic Binary Search | Easy | halving | — | LeetCode Binary Search — <https://leetcode.com/problems/binary-search/> | [091-basic-binary-search.md](091-basic-binary-search.md) | নোট আছে |
| 092 | Lower Bound | Easy | first ≥ x | 091 | Classic (Python bisect_left) | [092-lower-bound.md](092-lower-bound.md) | নোট আছে |
| 093 | Upper Bound | Easy | first > x | 092 | Classic (Python bisect_right) | [093-upper-bound.md](093-upper-bound.md) | নোট আছে |
| 094 | Search Insert Position | Easy | lower bound apply | 092 | LeetCode — <https://leetcode.com/problems/search-insert-position/> | [094-search-insert-position.md](094-search-insert-position.md) | নোট আছে |
| 095 | Square Root using Binary Search | Easy | first BSoA | 091 | LeetCode Sqrt(x) — <https://leetcode.com/problems/sqrtx/> | [095-square-root-binary-search.md](095-square-root-binary-search.md) | নোট আছে |
| 096 | Minimum Eating Speed | Medium | BSoA minimize | 095 | LeetCode Koko Eating Bananas — <https://leetcode.com/problems/koko-eating-bananas/> | [096-minimum-eating-speed.md](096-minimum-eating-speed.md) | নোট আছে |
| 097 | Ship Packages Within D Days | Medium | BSoA minimize | 096 | LeetCode — <https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/> | [097-ship-packages-d-days.md](097-ship-packages-d-days.md) | নোট আছে |
| 098 | Aggressive Cows | Medium | BSoA maximize | 096 | SPOJ AGGRCOW — <https://www.spoj.com/problems/AGGRCOW/> | [098-aggressive-cows.md](098-aggressive-cows.md) | নোট আছে |
| 099 | Allocate Minimum Pages | Medium | minimize max load | 097 | Classic interview problem (book allocation) | [099-allocate-minimum-pages.md](099-allocate-minimum-pages.md) | নোট আছে |
| 100 | Split Array Largest Sum | Hard | minimize max load | 099 | LeetCode — <https://leetcode.com/problems/split-array-largest-sum/> | [100-split-array-largest-sum.md](100-split-array-largest-sum.md) | নোট আছে |
| 101 | Median of Two Sorted Arrays | Hard | partition search | 092 | LeetCode — <https://leetcode.com/problems/median-of-two-sorted-arrays/> | [101-median-two-sorted-arrays.md](101-median-two-sorted-arrays.md) | নোট আছে |
| 102 | Kth Smallest in Multiplication Table | Hard | BSoA + counting | 096 | LeetCode — <https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/> (related: CSES Factory Machines — <https://cses.fi/problemset/task/1620>) | [102-kth-smallest-multiplication-table.md](102-kth-smallest-multiplication-table.md) | নোট আছে |

## "Inherits from" column-টা কী?

প্রতিটা problem আগের কারো কাঁধে দাঁড়িয়ে। 091 হলো ভিত; 092/093 সেটার বাঁক; 095-এ array উধাও হয়ে BSoA-র জন্ম; 096 থেকে minimize/maximize-এর পুরো পরিবার। আটকে গেলে "Inherits from" problem-টা আবার দেখো — template-টা সেখানেই পরিষ্কার হয়েছিল।

```text
091 (basic) ──> 092 (lower bound) ──> 093 (upper bound)
   │               ├──> 094 (insert position)
   │               └──> 101 (median partition)
   └──> 095 (sqrt, প্রথম BSoA)
            └──> 096 (Koko, minimize) ──> 097 (ships) ──> 099 (pages) ──> 100 (split)
                    ├──> 098 (cows, maximize)
                    └──> 102 (counting check)
```

## একটা ছোট পরামর্শ

এই level-এর প্রতিটা problem-এ নিজের কাছে তিনটা জবাবদিহি: **answer space, check, monotonicity।** আর code লেখার সময় প্রতিটা `lo = ...` / `hi = ...`-এর পাশে এক শব্দের মন্তব্য রাখো — "কেন এটা নিরাপদ"। Binary search-এ মুখস্থ template বিপজ্জনক — কারণ minimize আর maximize-এ move গুলো উল্টে যায়, আর ঝোঁকানো mid ভুল হলে infinite loop নিঃশব্দে অপেক্ষা করে। সিঁড়ির ছবি ([../visualization-ideas.md](../visualization-ideas.md)) আগে, code পরে — এই অভ্যাসটাই এই level-এর আসল উপহার।

Concept ঝালাই করতে → [../concept-notes.md](../concept-notes.md)। ছবি এঁকে বুঝতে → [../visualization-ideas.md](../visualization-ideas.md)।