Visualization Ideas — Binary Search on Answer¶
Binary search-এর সব bug লুকায় lo, hi আর mid-এর নাচে — আর সেই নাচ চোখে দেখার সেরা উপায় হলো প্রতিটা step আঁকা। এখানে আঁকার idea গুলো, আর শেষে 3টা worked ASCII example।
প্রতি concept-এর visualization idea¶
1. Guessing game = সংকুচিত দড়ি¶
1 থেকে n-এর একটা দড়ি আঁকো; lo আর hi হলো দুই হাত। প্রতিটা প্রশ্নের পর এক হাত mid-এ লাফ দেয় — দড়ির ধরা অংশ অর্ধেক। 5-6 frame আঁকলেই log-এর শরীরী অনুভূতি চলে আসে: দড়িটা ধসে পড়ছে, ধীরে না — exponentially।
2. Invariant ব্যানার¶
প্রতিটা binary search-এর উপরে একটা ব্যানার টাঙাও: "উত্তর সবসময় [lo, hi]-এর ভেতরে।" প্রতিটা lo = mid + 1 বা hi = mid লেখার সময় জিজ্ঞেস করো — ব্যানারটা এখনো সত্য? ছবিতে: প্রতি frame-এ [lo, hi] অংশটা highlight, বাদ পড়া অংশ ছাই রঙে — বাদ অংশে উত্তর নেই, এই বিশ্বাসটাই পুরো algorithm।
3. Lower/upper bound = দুটো কাঁটা¶
Sorted array-তে x-এর duplicate block-টা ঘিরে দুটো কাঁটা আঁকো: বাঁ কাঁটা = lower bound (block-এর শুরুর ঠিক আগে ঢোকার জায়গা), ডান কাঁটা = upper bound (block-এর শেষের ঠিক পরে)। দুই কাঁটার ফাঁক = x-এর সংখ্যা। [1, 3, 3, 3, 7]-এ আঁকলেই দুই ভাইয়ের পার্থক্য চিরতরে পরিষ্কার।
4. F/T সিঁড়ি — BSoA-র মূল ছবি¶
Answer space-টা x-অক্ষে; প্রতিটা guess-এর নিচে check-এর ফল লেখো। Minimize-এ পাবে F F F | T T T — খুঁজছ প্রথম T; maximize-এ T T T | F F F — খুঁজছ শেষ T। সীমানা-রেখাটা (|) মোটা করে আঁকো — পুরো খেলাটা ওই একটা রেখা খোঁজার। আর কোনো problem-এ আগে এই সিঁড়ি আঁকতে না পারলে — থামো, monotonicity-ই নেই হয়তো।
5. Koko-র টেবিল: speed → সময়¶
দুই column-এর টেবিল: speed k | মোট ঘণ্টা। k বাড়াও, ঘণ্টা নামতে দেখো — কোথাও সেটা h-এর নিচে নামে, সেটাই সীমানা। এই টেবিলটা আসলে check function-এর graph — হাতে বানালে "কেন monotonic" প্রশ্নের উত্তর চোখেই পেয়ে যাবে।
6. Aggressive cows = দাগ টানা রাস্তা¶
Number line-এ stall-গুলো দাগাও। একটা g বেছে greedy চালাও: প্রথম stall-এ গরু, তারপর প্রতিবার g-দূরত্বের রুলার বসিয়ে পরের বৈধ stall-এ। গরু আঁটল কি না — সেটাই check(g)। দুটো g (একটা ছোট, একটা বড়) দিয়ে পাশাপাশি আঁকো — কেন বড় g কঠিন, ছবিই বলবে।
7. Partition = দুই array-তে এক জোড়া কাঁচি¶
A আর B পাশাপাশি লেখো, প্রতিটায় একটা খাড়া কাটার দাগ। বাঁ পাশের সব টুকরো এক ঝুড়িতে, ডান পাশেরগুলো আরেক ঝুড়িতে — শর্ত: বাঁ ঝুড়ির max ≤ ডান ঝুড়ির min। A-র কাঁচি সরালে B-র কাঁচি উল্টোদিকে সরে (যোগফল ঠিক রাখতে) — এই যুগল-নাচটাই median problem-এর হৃদয়।
Worked ASCII example 1: lower bound-এর দড়ি-সংকোচন¶
a = [1, 3, 3, 3, 7], x = 3 — খুঁজছি প্রথম ≥ 3
frame 1: [1 3 3 3 7] · lo=0, hi=5, mid=2
───────────────── a[2]=3 ≥ 3 → hi=2 (mid রেখে!)
frame 2: [1 3 3] · · · lo=0, hi=2, mid=1
───────── a[1]=3 ≥ 3 → hi=1
frame 3: [1 3] · · · · lo=0, hi=1, mid=0
───── a[0]=1 < 3 → lo=1
frame 4: lo == hi == 1 → উত্তর 1 ✓
প্রতি frame-এ জীবিত অংশ অর্ধেক হয়েছে; আর hi = mid কেন (mid-1 না) — frame 1-এই দেখো, a[2] নিজেই উত্তর হতে পারত।
Worked ASCII example 2: Koko-র F/T সিঁড়ি (piles = [3, 6, 7, 11], h = 8)¶
speed k : 1 2 3 4 5 6 ... 11
মোট ঘণ্টা: 27 15 10 8 8 6 ... 4
check ≤8: F F F T T T ... T
↑
প্রথম T = উত্তর 4
binary search-এর পায়ের ছাপ:
lo=1, hi=11 → mid=6: T → hi=6
lo=1, hi=6 → mid=3: F → lo=4
lo=4, hi=6 → mid=5: T → hi=5
lo=4, hi=5 → mid=4: T → hi=4
lo=hi=4 ✓
পুরো টেবিল কখনো বানাতে হয়নি — মাত্র 4টা ঘরে উঁকি দিয়েই সীমানা ধরা পড়ল। 11টার বদলে 4 — আর n = 10^9 হলে 10^9-এর বদলে 30।
Worked ASCII example 3: aggressive cows-এর check (stalls = [1, 2, 4, 8, 9], c = 3)¶
guess g = 3:
1 2 4 8 9
🐄 🐄 · 1-এ প্রথম গরু; 2(দূরত্ব1)✗ 4(3)✓... আসলে দেখি:
1:🐄 2:1<3✗ 4:3≥3🐄 8:4≥3🐄 → 3টা বসে গেল ✓ T
guess g = 4:
1:🐄 2:✗ 4:3<4✗ 8:7≥4🐄 9:1<4✗ → মাত্র 2টা ✗ F
সিঁড়ি: g = 1 2 3 4 5 ...
check = T T T F F ... → শেষ T = 3, উত্তর 3
g = 3-এ আঁটে, g = 4-এ আঁটে না — maximize ঘরানার T T T F F F সিঁড়ি। এখানে check পাশ করলে lo = mid (আরো বড় লোভ), তাই mid-কে উপরে ঝোঁকাতে ভুলো না।
নিজে practice করার নিয়ম¶
- প্রতিটা binary search-এ dry run টেবিল বাধ্যতামূলক: step | lo | hi | mid | check/তুলনা | move — অন্তত যতক্ষণ template শরীরে না ঢোকে
- নতুন BSoA problem-এ code-এর আগে F/T সিঁড়িটা আঁকো; সিঁড়ি monotonic না হলে binary search-ই ভুল হাতিয়ার
hi - lo == 1অবস্থাটা প্রতিটা solution-এ হাতে চালাও — infinite loop-এর একমাত্র আস্তানা এখানেই- bisect_left/bisect_right-এর কাঁটার ছবিটা duplicate-ওয়ালা নতুন array-তে আবার আঁকো — গোনার কাজে এই দুটোই তোমার দৈনন্দিন হাতিয়ার হবে