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 |
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¶
Lower = 1, upper = 4
01চিহ্নিত ঘর: 12↑ lowerচিহ্নিত ঘর: 22চিহ্নিত ঘর: 3244↑ upperউজ্জ্বল তিনটি ঘরে 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-এর কাটাটি বাম অংশের মোট সংখ্যা থেকে নির্ধারিত হয়।