Skip to content

Level 7 — Binary Search on Answer (অনুমানের খেলা, অর্ধেক করে বাদ)

ছোটবেলার number guessing game মনে আছে? "1 থেকে 100-এর মধ্যে একটা সংখ্যা ভেবেছি" — তুমি 50 বলো, "বড়" শুনলে নিচের অর্ধেক পুরোটা বাদ। 7টা প্রশ্নেই 100-এর যেকোনো সংখ্যা ধরা পড়ে। এই level-এ শিখবে সেই খেলাটা শুধু sorted array-তে না — উত্তরের উপরেই খেলতে: "উত্তরটা কি 50 হতে পারে?" জিজ্ঞেস করে করে অর্ধেক জগৎ বাদ দিতে।

এই level এ কী শিখবে?

মূল idea গুলো:

  • Binary search-এর হৃদয় — প্রতি প্রশ্নে search space অর্ধেক; lo/hi-এর invariant ("উত্তর সবসময় [lo, hi]-এর ভেতরে") ধরে রাখা
  • Lower bound vs upper bound — প্রথম ≥ x আর প্রথম > x; Python-এর bisect_left / bisect_right
  • Binary Search on Answer (BSoA) — উত্তর guess করো + একটা feasibility check লেখো; F F F T T T-এর monotonic সিঁড়ি
  • while lo < hi template — overflow-হীন, infinite-loop-হীন একটা নির্ভরযোগ্য কাঠামো
  • Minimize ঘরানা — Koko (speed → সময়), ships (capacity → দিন), pages (max load → সম্ভব কিনা)
  • Maximize ঘরানা — aggressive cows: minimum gap যত বড় সম্ভব (সিঁড়িটা উল্টো: T T T F F F)
  • Counting দিয়ে check — multiplication table-এ "x-এর চেয়ে ছোট-সমান কয়টা" প্রতি row-তে min(x // i, n)
  • Partition search — median of two sorted arrays-এর sketch: কাটার জায়গাটাই search করা

কেন এই level দরকার?

Competitive programming (CP) এ: "answer monotonic হলে binary search করো" — এটা CP-র অন্যতম মৌলিক reflex। Codeforces Div 2 C/D-তে BSoA নিয়মিত মুখ; CSES-এ Factory Machines, Array Division-এর মতো পুরো একটা ঘরানা আছে। Constraint-এ 10^18 দেখলেই অভিজ্ঞ চোখ বলে: "loop না, binary search"।

Interview এ: Koko Eating Bananas, Capacity to Ship Packages, Split Array Largest Sum — এগুলো common interview pattern; "minimize the maximum" শুনলেই BSoA মাথায় আসা উচিত। আর Median of Two Sorted Arrays তো বহু বছর ধরেই hard-interview-এর পোস্টার সমস্যা।

পরের ধাপে: binary search on real numbers (precision সহ), parametric search, ternary search — সবার ভিত এখানেই। আর "guess + check" এই decomposition-চিন্তা greedy আর DP-র feasibility check-এও ফিরবে।

Prerequisites

  • Level 0: Absolute Basics — loop, integer division (//)
  • Level 6: Two Pointers ও Sliding Window — "search space কমানো"-র চিন্তা; এখানে সেটাই অর্ধেক-অর্ধেক রূপে
  • log-এর প্রাথমিক ধারণা — "কতবার অর্ধেক করলে 1-এ নামে" = log₂(n); O(n log n) পড়তে পারা

Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

  • [ ] while lo < hi template-এ lo/hi-এর invariant কী — প্রতি লাইনে বলতে পারি
  • [ ] mid = (lo + hi) // 2 কখন lo-এর দিকে ঝোঁকে, আর সেটা কখন infinite loop বাঁচায় — জানি
  • [ ] Lower bound (প্রথম ≥ x) আর upper bound (প্রথম > x)-এর পার্থক্য একটা উদাহরণে দেখাতে পারি
  • [ ] bisect_left / bisect_right কোনটা কী দেয় — না দেখে বলতে পারি
  • [ ] BSoA-র দুটো উপাদান (answer space + feasibility check) আলাদা করে চিনতে পারি
  • [ ] F F F T T T-এর monotonic সিঁড়ি কেন জরুরি — counter-example সহ বুঝি
  • [ ] Koko-তে check(speed) কেন monotonic — ব্যাখ্যা করতে পারি (speed বাড়লে সময় কমে)
  • [ ] Minimize আর maximize — দুই ঘরানায় lo/hi কোন দিকে চাপে, গুলিয়ে ফেলি না
  • [ ] Answer space-এর সীমা (lo, hi) ঠিক করার নিয়ম জানি — feasible একটা hi নিশ্চিত করা
  • [ ] Multiplication table-এ count ≤ x-এর formula min(x // i, n) কোথা থেকে আসে — বুঝি

Problem list

মোট 12টা problem — 5টা Easy, 4টা Medium, 3টা Hard।

Easy

# Problem Pattern Source
091 Basic Binary Search halving LeetCode Binary Search — https://leetcode.com/problems/binary-search/
092 Lower Bound first ≥ x Classic (Python bisect_left)
093 Upper Bound first > x Classic (Python bisect_right)
094 Search Insert Position lower bound apply LeetCode — https://leetcode.com/problems/search-insert-position/
095 Square Root using Binary Search first BSoA LeetCode Sqrt(x) — https://leetcode.com/problems/sqrtx/

Medium

# Problem Pattern Source
096 Minimum Eating Speed BSoA minimize LeetCode Koko Eating Bananas — https://leetcode.com/problems/koko-eating-bananas/
097 Ship Packages Within D Days BSoA minimize LeetCode — https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
098 Aggressive Cows BSoA maximize SPOJ AGGRCOW — https://www.spoj.com/problems/AGGRCOW/
099 Allocate Minimum Pages minimize max load Classic interview problem (book allocation)

Hard

# Problem Pattern Source
100 Split Array Largest Sum minimize max load LeetCode — https://leetcode.com/problems/split-array-largest-sum/
101 Median of Two Sorted Arrays partition search LeetCode — https://leetcode.com/problems/median-of-two-sorted-arrays/
102 Kth Smallest in Multiplication Table BSoA + counting LeetCode — https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ (related: CSES Factory Machines — https://cses.fi/problemset/task/1620)

পুরো tracker table (status সহ) আছে problems/README.md-তে।

  1. 091 — guessing game টা array-তে; lo/hi-এর invariant এখানেই পাকা করো
  2. 092 → 093 — lower আর upper bound পাশাপাশি; bisect দিয়ে যাচাই
  3. 094 — lower bound-এর প্রথম প্রয়োগ; নতুন কিছু না, চেনা জিনিস নতুন পোশাকে
  4. 095 — প্রথম BSoA! Array নেই, তবু binary search — এই মোড়টাই level-এর হৃদয়
  5. 096 → 097 — minimize ঘরানা দুই স্বাদে: speed আর capacity
  6. 098 — এবার maximize; সিঁড়িটা উল্টে যায়, মাথাও একটু উল্টাতে হয়
  7. 099 → 100 — "minimize the maximum" জোড়া; 099 হলো 100-এরই classic রূপ
  8. 102 — check function-টা নিজেই একটা counting problem; BSoA-র full power
  9. 101 — সবশেষে partition search; এটা আলাদা জাত, সময় নিয়ে বোঝো

Common mistakes (সাধারণ ভুল)

  1. Infinite loop: lo = mid আর নিচ-ঝোঁকা mid একসাথে — lo = mid করতে হলে mid = (lo + hi + 1) // 2 (উপরে ঝোঁকানো) লাগে, নইলে hi - lo == 1 অবস্থায় চিরঘূর্ণন। নিয়ম: কোন pointer mid-এ আসে দেখো, mid-এর ঝোঁক সেই অনুযায়ী।
  2. hi = mid - 1 vs hi = mid গুলিয়ে ফেলা — mid নিজে এখনো উত্তর হতে পারলে তাকে বাদ দিও না (hi = mid); নিশ্চিত বাদ হলে mid - 1। Invariant-টা মুখে বলো: "[lo, hi]-তে উত্তর আছে" — প্রতিটা update সেটা রক্ষা করছে কি?
  3. Feasibility check monotonic কিনা যাচাই না করা — F আর T এলোমেলো হলে binary search মিথ্যা বলে। Check লেখার আগে এক লাইনে নিজেকে বোঝাও: "guess বাড়ালে check-এর ফল কোন দিকে যায়, আর কেন?"
  4. Answer space-এর সীমা ভুল — Koko-তে hi = max(piles)-এর কমে শুরু করলে উত্তরটাই range-এর বাইরে পড়তে পারে; lo = 0 দিলে check-এ division by zero। lo = 1, hi = max(piles) — hi সবসময় একটা feasible মান হওয়া চাই।
  5. Check-এ ceiling division ভুল — "pile / speed-এর ceiling" দরকার, pile // speed না। Python idiom: (pile + speed - 1) // speed বা -(-pile // speed)। Floor দিলে সময় কম গুনে ভুল speed-কে feasible বলবে।
  6. Minimize আর maximize-এর move উল্টে ফেলা — minimize-এ check পাশ করলে hi = mid (আরো ছোট চেষ্টা); maximize-এ পাশ করলে lo = mid (আরো বড় চেষ্টা)। সিঁড়ির ছবি এঁকে নাও — কোন পাশে T জমে আছে।
  7. bisect_left আর bisect_right অদলবদল — দুটোই duplicate-এ আলাদা উত্তর দেয়: [1, 3, 3, 5]-এ x=3 → left দেয় 1, right দেয় 3। গোনা-জাতীয় কাজে (কয়টা < x, কয়টা ≤ x) ভুলটা নিঃশব্দে wrong answer দেয়।
  8. 0-আকারের সমস্যায় edge case — খালি array, k সবচেয়ে বড়/ছোট, এক element — binary search-এর bug-রা এখানেই লুকায়। প্রতিটা solution-এ n=1 কেস হাতে চালাও।

পরের level এ যাওয়ার আগে checklist

  • [ ] 091-এর dry run টেবিল (step | lo | hi | mid | সিদ্ধান্ত) হাতে বানিয়েছি
  • [ ] [1, 3, 3, 5]-এ x=3 দিয়ে bisect_left আর bisect_right-এর উত্তর হাতে বের করে Python-এ মিলিয়েছি
  • [ ] 095-এ "array ছাড়া binary search" — এই মোড়টা নিজের ভাষায় এক প্যারায় লিখেছি
  • [ ] 096-এর check(speed) আলাদা function হিসেবে লিখে আলাদাভাবে test করেছি
  • [ ] একটা minimize (096/097) আর একটা maximize (098) — দুটোর সিঁড়ির ছবি পাশাপাশি এঁকেছি
  • [ ] "অর্ধেক করে বাদ" কেন O(log n) — 10^18 থেকে কয় ধাপে 1-এ নামে, হিসাব করেছি (≈ 60)

সব টিক দিতে পারলে — চলো Level 8: Greedy Math Tricks-এ। সেখানে guess-ও না, window-ও না — প্রতি ধাপে স্রেফ সবচেয়ে লোভী choice, আর তার পেছনের প্রমাণ।

Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে source-map.md-তে।