# Binary search — কোন অংশ বাদ যাচ্ছে

## প্রথম true খোঁজা: Koko-এর গতি

Piles `[3,6,7,11]`, সময় 8 ঘণ্টা। প্রতি pile-এর সময় `ceil(pile/speed)`।

| speed | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| ঘণ্টা | 27 | 15 | 10 | 8 | 8 | 6 | 5 | 5 | 5 | 5 | 4 |
| 8 ঘণ্টায় সম্ভব? | F | F | F | T | T | T | T | T | T | T | T |

```mermaid
flowchart TD
    A["lo=1, hi=11, mid=6"] -->|"6 ঘণ্টা: সম্ভব"| B["hi=6: উত্তর 6 বা তার নিচে"]
    B --> C["lo=1, hi=6, mid=3"]
    C -->|"10 ঘণ্টা: অসম্ভব"| D["lo=4"]
    D --> E["lo=4, hi=6, mid=5"]
    E -->|"8 ঘণ্টা: সম্ভব"| F["hi=5"]
    F --> G["lo=4, hi=5, mid=4"]
    G -->|"8 ঘণ্টা: সম্ভব"| H["hi=4, lo=hi: উত্তর 4"]
```

Invariant: উত্তর সবসময় inclusive `[lo,hi]`-এর মধ্যে। True পেলে mid-কে বাদ দিই না—সেটিই প্রথম true হতে পারে।

## Lower bound ও upper bound

```dsa
kind: array
title: "Target 2-এর শুরু ও শেষের পরের সীমানা"
steps:
  - label: "Lower = 1, upper = 4"
    values: [1, 2, 2, 2, 4]
    active: [1, 2, 3]
    pointers: {lower: 1, upper: 4}
    note: "উজ্জ্বল তিনটি ঘরে target আছে। Upper নিজে target-এর অংশ নয়।"
```

Lower bound = প্রথম index যার মান অন্তত 2; upper bound = প্রথম index যার মান 2-এর বেশি। তাই 2-এর সংখ্যা `4-1=3`। Target 9 হলে দুটিই array-এর দৈর্ঘ্য 5 ফেরত দেবে; ওই index-এ array access করা যাবে না।

শেষ true খোঁজার সমস্যায় (যেমন maximum minimum distance) check-এর দিক উল্টো হতে পারে; এই first-true update হুবহু বসাবে না।

## Aggressive Cows: শেষ true

Stalls `[1,2,4,8,9]`, cow 3টি। প্রতিবার প্রথম stall নিই, তারপর আগের cow থেকে যথেষ্ট দূরের প্রথম stall।

| minimum gap | নির্বাচিত stall | সম্ভব? |
| --- | --- | --- |
| 1 | 1,2,4 | হ্যাঁ |
| 2 | 1,4,8 | হ্যাঁ |
| 3 | 1,4,8 | হ্যাঁ |
| 4 | 1,8; তৃতীয়টির জায়গা নেই | না |

Gap 4 সম্ভব না হলে আরও বড় gap-ও সম্ভব নয়। তাই largest feasible gap 3। এখানে check-এর সারি true→false; Koko-তে ছিল false→true।

## দুই sorted array-এর median: সঠিক কাটার জায়গা

| Array | বাঁ অংশ | ডান অংশ |
| --- | --- | --- |
| A = [1,3] | 1 | 3 |
| B = [2,4] | 2 | 4 |
| সীমার মান | সর্বোচ্চ 2 | সর্বনিম্ন 3 |

বাঁয়ে মোট 2টি, ডানে 2টি। বাঁয়ের সর্বোচ্চ `max(1,2)=2`, ডানের সর্বনিম্ন `min(3,4)=3`; সব বাঁয়ের মান সব ডানের মানের চেয়ে ছোট বা সমান। Median `(2+3)/2=2.5`। Binary search-এ A-এর কাটার জায়গা বদলাই, B-এর কাটাটি বাম অংশের মোট সংখ্যা থেকে নির্ধারিত হয়।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)