Concept Notes — Binary Search on Answer (ভেতর থেকে বোঝা)¶
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 হওয়া:
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):
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)
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 বার!
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):
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-এর উত্তরগুলো সাজালে:
একটা monotonic সিঁড়ি — একবার F শুরু হলে আর T ফেরে না। ব্যস, এই সিঁড়িতেই binary search চলে! এটাই Binary Search on Answer (BSoA): array-র জায়গায় answer space, comparison-এর জায়গায় feasibility check।
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 সবসময় তিন উপাদান:
- Answer space — উত্তর কোন range-এ? (lo, hi ঠিক করা)
- Feasibility check —
check(guess)→ True/False, এক পাসে হিসাবযোগ্য - 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-এর সিঁড়ি:
k : 1 2 3 4 5 6 ...
check : F F F T T T ... check(k) = "k speed-এ h ঘণ্টায় শেষ হয়?"
↑
প্রথম T-টাই উত্তর
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):
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:
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 ছাড়িয়ে গেলেই নতুন ভাগ শুরু।
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) টা:
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]।
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¶
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-এর গতিতে।