# Concept Notes — Binary Search on Answer (ভেতর থেকে বোঝা)

## সহজ করে শুরু: উত্তর অনুমান করে সম্ভব কি না পরীক্ষা

একটি সম্ভাব্য উত্তর x নাও। `possible(x)` যদি একবার সত্য হওয়ার পর সব বড় x-এর জন্য সত্য থাকে, তাহলে প্রথম সত্যটি binary search-এ খোঁজা যায়। যেমন গতি বাড়ালে কাজ শেষ করতে সময় বাড়ে না।

**প্রোগ্রামে কোথায় ব্যবহার করবে:** নির্দিষ্ট দিনের মধ্যে shipment-এর সর্বনিম্ন capacity, deadline মেটাতে সর্বনিম্ন speed এবং সাজানো data-তে insertion position বের করতে লাগে।

**কৌশল বাছার আগে শর্ত:** “সর্বনিম্ন” শব্দ দেখলেই binary search হবে না: monotonic check ও সঠিক bounds দেখাতে হবে। একই helper-এ first-true ও last-true update মিশিয়ে ফেলবে না।

পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও।

> Binary search-এর আসল রূপ array খোঁজা না — **অনুমানের খেলা**। যেকোনো প্রশ্ন, যার উত্তরে "হ্যাঁ/না, এর চেয়ে বড়/ছোট" বলা যায়, প্রতি প্রশ্নে অর্ধেক সম্ভাবনা মুছে দেয়। এই চোখে দেখলে binary search চলে এমন জায়গায় যেখানে কোনো array-ই নেই।

## 1. Number guessing game — log-এর জন্ম

1 থেকে 100-এর একটা সংখ্যা: প্রতিটা প্রশ্নে ("50-এর চেয়ে বড়?") অর্ধেক জগৎ বাদ। 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1 — মাত্র 7 প্রশ্ন। n থেকে 1-এ নামতে লাগে **log₂(n)** ধাপ; 10^18-এর জন্যও মাত্র ৬০টা। এই অসম্ভব দ্রুততার একটাই দাম: প্রতিটা প্রশ্নের উত্তর যেন নির্ভুলভাবে বলে দেয় **কোন অর্ধেক বাদ**।

Array-তে সেই নিশ্চয়তা দেয় sorted হওয়া:

```python
def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:  return mid
        if a[mid] < x:   lo = mid + 1     # বাঁ অর্ধেক বাদ
        else:            hi = mid - 1     # ডান অর্ধেক বাদ
    return -1
```

Mini dry run (`a = [2, 5, 8, 12, 16, 23], x = 16`):

```text
lo=0, hi=5: mid=2, a[2]=8 < 16   → lo=3
lo=3, hi=5: mid=4, a[4]=16 ✓     → উত্তর index 4
```

**Invariant**-টা মুখে বলো: "x যদি থাকে, তবে [lo, hi]-এর ভেতরেই আছে।" প্রতিটা update এই বাক্যটা সত্য রাখে — binary search-এ bug মানেই কোথাও এই বাক্য ভেঙেছে।

## 2. Lower bound আর upper bound — দুই ভাইয়ের ফারাক

খোঁজার চেয়েও বেশি দরকারি প্রশ্ন: "x-টা **কোথায় বসবে**?" দুটো সংজ্ঞা:

- **lower bound** = প্রথম index যেখানে `a[i] >= x` (Python: `bisect_left`)
- **upper bound** = প্রথম index যেখানে `a[i] > x` (Python: `bisect_right`)

```text
a =      [1,  3,  3,  3,  7]
index =   0   1   2   3   4
x = 3:  lower bound = 1 (প্রথম ≥3)    upper bound = 4 (প্রথম >3)
        দুটোর ফারাক = 4 - 1 = 3 — অর্থাৎ 3 আছে 3 বার!
```

```python
def lower_bound(a, x):          # bisect.bisect_left-এর হাতে-বানানো রূপ
    lo, hi = 0, len(a)          # hi = len(a): "কোথাও নেই"-এর উত্তর n
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:  lo = mid + 1   # mid নিশ্চিত উত্তর না
        else:           hi = mid       # mid উত্তর হতে পারে — রেখে দাও!
    return lo
```

Mini dry run (`a = [1, 3, 3, 3, 7], x = 3`):

```text
lo=0, hi=5: mid=2, a[2]=3 ≥ 3 → hi=2
lo=0, hi=2: mid=1, a[1]=3 ≥ 3 → hi=1
lo=0, hi=1: mid=0, a[0]=1 < 3 → lo=1
lo == hi == 1 → উত্তর 1 ✓
```

`hi = mid` (mid - 1 না!) — কারণ mid নিজেই উত্তর হতে পারে। আর `while lo < hi` — শেষে lo আর hi এক বিন্দুতে মিলে যায়, সেটাই উত্তর। এই template-টাই সামনে বারবার আসবে।

## 3. BSoA — উত্তরের উপর binary search

এবার মোড়। ধরো প্রশ্ন: "⌊√x⌋ কত?" কোনো array নেই। কিন্তু একটা **check** আছে: "m² ≤ x?" — আর সেই check-এর উত্তরগুলো সাজালে:

```text
x = 17:   m      = 1  2  3  4  | 5  6  7 ...
          m²≤17  = T  T  T  T  | F  F  F ...
                              ↑
                  শেষ T-টাই উত্তর (4)
```

একটা **monotonic সিঁড়ি** — একবার F শুরু হলে আর T ফেরে না। ব্যস, এই সিঁড়িতেই binary search চলে! এটাই **Binary Search on Answer (BSoA)**: array-র জায়গায় answer space, comparison-এর জায়গায় feasibility check।

```python
def isqrt(x):
    lo, hi = 0, x + 1               # উত্তর [0, x]-এর মধ্যে
    while lo < hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:  lo = mid + 1
        else:               hi = mid
    return lo - 1                    # প্রথম F-এর আগেরটা = শেষ T
```

BSoA-র recipe সবসময় তিন উপাদান:

1. **Answer space** — উত্তর কোন range-এ? (lo, hi ঠিক করা)
2. **Feasibility check** — `check(guess)` → True/False, এক পাসে হিসাবযোগ্য
3. **Monotonicity-র প্রমাণ** — guess বাড়ালে check-এর ফল এক দিকেই যায়, কেন?

তিন নম্বরটা ছাড়া বাকি দুটো অর্থহীন — F T F T এলোমেলো হলে binary search নির্বিকারভাবে ভুল উত্তর দেবে।

## 4. Koko Eating Bananas — minimize ঘরানার মুখ

Koko-র সামনে কলার pile গুলো, h ঘণ্টা সময়; ঘণ্টায় k টা করে খেলে এক pile-এ লাগে `ceil(pile / k)` ঘণ্টা। **সবচেয়ে ছোট k** কত যাতে সময়ে শেষ হয়?

ভাবো — k বাড়ালে মোট সময় কমে (বা সমান)। তাহলে check-এর সিঁড়ি:

```text
k     :  1   2   3   4   5   6 ...
check :  F   F   F   T   T   T ...     check(k) = "k speed-এ h ঘণ্টায় শেষ হয়?"
                     ↑
              প্রথম T-টাই উত্তর
```

```python
def min_eating_speed(piles, h):
    def check(k):                              # k speed-এ পারা যায়?
        return sum((p + k - 1) // k for p in piles) <= h

    lo, hi = 1, max(piles)                     # hi নিশ্চিত feasible
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):  hi = mid               # পারা যায় → আরো ছোট চেষ্টা
        else:           lo = mid + 1           # পারা যায় না → বড় লাগবে
    return lo
```

Mini dry run (`piles = [3, 6, 7, 11], h = 8`):

```text
lo=1, hi=11: mid=6 → সময় = 1+1+2+2 = 6 ≤ 8 → T → hi=6
lo=1, hi=6:  mid=3 → সময় = 1+2+3+4 = 10 > 8 → F → lo=4
lo=4, hi=6:  mid=5 → সময় = 1+2+2+3 = 8 ≤ 8 → T → hi=5
lo=4, hi=5:  mid=4 → সময় = 1+2+2+3 = 8 ≤ 8 → T → hi=4
lo == hi == 4 → উত্তর 4 ✓
```

লক্ষ করো: `(p + k - 1) // k` হলো ceiling division — `p // k` লিখলে সময় কম গুনে ভুল হয়। আর Ship Packages problem-টা হুবহু একই কাঠামো — k-এর জায়গায় জাহাজের capacity, ঘণ্টার জায়গায় দিন। **এক template, ভিন্ন গল্প।**

## 5. Aggressive Cows — maximize ঘরানা, সিঁড়ি উল্টো

n টা stall-এর position দেওয়া, c টা গরু বসাতে হবে — **সবচেয়ে কাছের দুই গরুর দূরত্ব (minimum gap) যত বড় সম্ভব** করো। এবার guess করো gap `g`, আর check: "প্রতি দুই গরুর মাঝে অন্তত g দূরত্ব রেখে c টা গরু বসানো যায়?" — greedy-তে এক পাসে হয়: প্রথম stall-এ একটা বসাও, তারপর যেখানে g দূরত্ব পাও সেখানেই পরেরটা।

g ছোট হলে বসানো সহজ, বড় হলে কঠিন — সিঁড়িটা এবার **T T T F F F**:

```python
def aggressive_cows(stalls, c):
    stalls.sort()
    def check(g):                              # gap ≥ g রেখে c টা বসে?
        cnt, last = 1, stalls[0]
        for s in stalls[1:]:
            if s - last >= g:
                cnt += 1; last = s
        return cnt >= c

    lo, hi = 0, stalls[-1] - stalls[0]
    while lo < hi:
        mid = (lo + hi + 1) // 2               # উপরে ঝোঁকানো mid!
        if check(mid):  lo = mid               # পারা যায় → আরো বড় চেষ্টা
        else:           hi = mid - 1
    return lo
```

দুটো বদল খেয়াল করো: (1) check পাশ করলে `lo = mid` — কারণ আরো **বড়** খুঁজছি; (2) তাই `mid = (lo + hi + 1) // 2` — উপরে ঝোঁকানো, নইলে `hi - lo == 1`-এ `mid = lo` হয়ে `lo = mid` কোনো অগ্রগতিই করে না → infinite loop। নিয়মটা মনে রাখো: **`lo = mid` থাকলে mid উপরে ঝোঁকাও, `hi = mid` থাকলে নিচে।**

## 6. Minimize the maximum — pages আর split

"K টা ভাগে array ভাঙো যাতে **সবচেয়ে ভারী ভাগটা যত হালকা সম্ভব** হয়" — book allocation আর Split Array Largest Sum, দুটো একই problem। Guess করো সর্বোচ্চ load `m`; check: "কোনো ভাগের sum যেন m না ছাড়ায় — এভাবে ভাঙলে ভাগ লাগে বড়জোর K টা?" Greedy এক পাস: বাঁ থেকে যোগ করতে থাকো, m ছাড়িয়ে গেলেই নতুন ভাগ শুরু।

```text
a = [7, 2, 5, 10, 8], K = 2, guess m = 18:
[7, 2, 5] (sum 14, পরেরটা নিলে 24 > 18) | [10, 8] (sum 18) → 2 ভাগ ≤ 2 ✓ T
guess m = 17: [7,2,5]=14 | [10]=10 (8 নিলে 18>17) | [8] → 3 ভাগ > 2 ✗ F
```

m যত বড়, ভাগ তত কম লাগে → monotonic → BSoA। `lo = max(a)` (কোনো ভাগ এক element-এর ছোট হয় না), `hi = sum(a)` (এক ভাগেই সব)। Minimize template-টাই (section 4) বসে যায়।

## 7. Counting check — multiplication table

m × n গুণের টেবিলে **k-তম ছোট** সংখ্যা? টেবিলটা বানালেই মরণ (m, n ≤ 3×10^4)। কিন্তু guess করো মান `x`, আর গোনো: "x-এর চেয়ে ছোট-সমান কয়টা ঘর?" প্রতিটা row i-তে মানগুলো `i, 2i, 3i, ..., ni` — এর মধ্যে ≤ x হলো `min(x // i, n)` টা:

```text
3×3 টেবিল, x = 4:
row 1: 1 2 3        ≤4 → min(4//1, 3) = 3 টা
row 2: 2 4 6        ≤4 → min(4//2, 3) = 2 টা
row 3: 3 6 9        ≤4 → min(4//3, 3) = 1 টা     মোট count(4) = 6
```

`count(x) ≥ k` হওয়াটা x-এ monotonic (x বাড়লে count কমে না) → BSoA। উত্তর হলো **প্রথম x যার count(x) ≥ k** — lower bound-এর সেই চেনা কাঠামো, শুধু array-র বদলে একটা গোনার function। Check-টা নিজে O(m), পুরোটা O(m log(mn))। CSES Factory Machines-ও একই পরিবার: "t সময়ে কয়টা product বানানো যায়" গুনে সময়ের উপর binary search।

## 8. Median of Two Sorted Arrays — partition sketch

দুটো sorted array-র মিলিত median — O(log) চাইলে merge করা চলবে না। নতুন চোখ: median মানে আসলে একটা **কাটা** — বাঁ পাশে অর্ধেক element, ডান পাশে অর্ধেক। দুই array-তেই একটা করে কাটা দাও; প্রথমটায় কাটা i ঠিক করলে দ্বিতীয়টার কাটা j নিজে থেকেই ঠিক (`i + j = মোট অর্ধেক`)। কাটা **বৈধ** হবে যদি: বাঁ পাশের সবাই ≤ ডান পাশের সবাই — মানে `A[i-1] ≤ B[j]` আর `B[j-1] ≤ A[i]`।

```text
A: 1  3 | 8  9        কাটার বাঁয়ে: {1, 3, 2, 7} — ডানে: {8, 9, 11}
B: 2  7 | 11          check: 3 ≤ 11 ✓, 7 ≤ 8 ✓ → বৈধ কাটা!
```

i ছোট হলে `A[i] < B[j-1]` ধরনের লঙ্ঘন, বড় হলে উল্টোটা — কোন দিকে সরতে হবে check-ই বলে দেয় → ছোট array-র উপর binary search, O(log(min(m, n)))। এখানে শুধু sketch — পুরো যত্নের জায়গা problem 101-এর note।

## এক নজরে cheat sheet

```text
exact search      : while lo <= hi; mid মিললে return; নইলে অর্ধেক বাদ
lower bound       : প্রথম ≥ x; while lo < hi; a[mid] < x → lo=mid+1, নইলে hi=mid
upper bound       : প্রথম > x; শুধু comparison-টা ≤ হয়ে যায়
bisect            : bisect_left = lower, bisect_right = upper
BSoA recipe       : answer space + check(guess) + monotonicity-র প্রমাণ
minimize (FFFTTT) : check পাশ → hi = mid; ফেল → lo = mid + 1; mid নিচে ঝোঁকা
maximize (TTTFFF) : check পাশ → lo = mid; ফেল → hi = mid - 1; mid = (lo+hi+1)//2
ceil division     : (p + k - 1) // k
counting check    : multiplication table-এ count(x) = Σ min(x // i, n)
সন্দেহ হলে        : invariant বাক্যটা জোরে বলো — "[lo, hi]-তেই উত্তর"
```

মনে রাখার একটাই বাক্য: **উত্তর খুঁজতে পারো না? তাহলে উত্তর ধরে নিয়ে যাচাই করতে পারো কি না দেখো।** যাচাই সস্তা আর monotonic হলেই — খেলা শেষ, log-এর গতিতে।