উত্তরের ওপর বাইনারি সার্চ (Binary Search on Answer)
কল্পনা করুন আপনি একজন ডেলিভারি ড্রাইভার, যাকে সন্ধ্যা ৬টার মধ্যে তার ডেলিভারি সম্পন্ন করতে হবে। আপনি বিভিন্ন গতিতে বা স্পিডে গাড়ি চালাতে পারেন। খুব ধীরে চালালে — আপনি সময়মতো পৌঁছাতে পারবেন না। আবার পর্যাপ্ত দ্রুতগতিতে চালালে — আপনি ঠিকই পৌঁছে যাবেন। 'খুব ধীর' এবং 'পর্যাপ্ত দ্রুতগতি'-এর মাঝামাঝি কোথাও একটি সর্বনিম্ন বা মিনিমাম স্পিড (minimum speed) রয়েছে যা দিয়ে ঠিক কাজটি সম্পন্ন হয় বা সম্ভব হয়।
আপনি কীভাবে এটি খুঁজে পাবেন? আপনি 1 কিলোমিটার/ঘণ্টা থেকে শুরু করে ঊর্ধ্বমুখী প্রতিটি সম্ভাব্য স্পিড পরীক্ষা করে দেখতে পারেন — কিন্তু সেটি অনেক বেশি ধীরগতির হবে। এর চেয়ে একটি বুদ্ধিমান উপায় হলো: মাঝামাঝি স্পিড বা গতিটি পরীক্ষা করা। যদি এটি কাজ করে, তবে এটিকে আরও কম গতিতে চেষ্টা করুন। আর যদি কাজ না করে, তবে আরো দ্রুতগতিতে চেষ্টা করুন। আপনি বাইনারি সার্চ করছেন — তবে তা কোনো অ্যারের ওপর নয়, বরং সম্ভাব্য উত্তরগুলোর স্পেস ব জায়গার (space of possible answers) ওপর।
মূল ধারণা (The big idea)
সাধারণ বাইনারি সার্চ একটি সাজানো অ্যারে বা সর্টেড অ্যারের ভেতরের কোনো একটি মান বা ভ্যালুকে খুঁজে বের করে। উত্তরের ওপর বাইনারি সার্চ (Binary search on answer) আপনার সমস্যার সম্ভাব্য সমস্ত সমাধানের বা সলিউশনের স্পেস থেকে একটি মান খুঁজে বের করে। এই কৌশলটি শুধুমাত্র তখনই কাজ করে যখন আপনার উত্তরের স্পেসে বা সীমানায় একটি পরিষ্কার বিভাজন বা বাউন্ডারি থাকে: এমন একটি নির্দিষ্ট থ্রেশহোল্ড (threshold) বা বিন্দুর নিচে এলে উত্তরটি হয় "না, ফিজিবল বা সম্ভব নয়", এবং এর উপরে গেলে তা হয় "হ্যাঁ, ফিজিবল বা সম্ভব" — এবং এটি সর্বত্রই প্রযোজ্য হতে হবে। এই বৈশিষ্ট্যটিকে মনোটোনিসিটি (monotonicity) বা একমুখিতা বলা হয়।
যদি আপনি feasible(x) নামে একটি ফাংশন লিখতে পারেন যা উত্তর দেয় "আমরা কি এটি x দিয়ে করতে পারি?", এবং যদি সেই ফাংশনটি ঠিক একটি নির্দিষ্ট বিন্দুতেই ফলস (false) থেকে ট্রু (true) তে পরিবর্তিত বা ফ্লিপ (flip) হয়, তবে আপনি সেই পরিবর্তন বা ফ্লিপ বিন্দুটি খোঁজার জন্য বাইনারি সার্চ করতে পারেন।
টেমপ্লেট (The template)
সর্বনিম্ন সম্ভাব্য উত্তরটিকে lo এ এবং সর্বোচ্চটিকে hi এ সেট করুন। যতক্ষণ lo < hi হবে ততক্ষণ লুপ বা চক্রটি চলতে দিন: mid = lo + (hi - lo) / 2 গণনা করুন। যদি feasible(mid) এর মান ট্রু (true) হয়, তবে উত্তরটি mid হতে পারে অথবা এর চেয়েও ছোট কোনো সংখ্যা হতে পারে — সেক্ষেত্রে hi = mid সেট করুন। অন্যথায়, mid অনেক বেশি ছোট — তাই lo = mid + 1 সেট করুন। লুপটি শেষে, lo == hi ই হবে আপনার ফিজিবল বা সম্ভবপর কোনো উত্তরগুলোর মধ্যে সবচেয়ে নিম্নতম বা কম মান।
কিছু ক্লাসিক উদাহরণ (Classic examples)
অ্যারেকে k সংখ্যক গ্রুপে ভাগ করুন (সর্বোচ্চ যোগফল হ্রাস করুন): একটি অ্যারে এবং k টি গ্রুপ দেওয়া আছে, গ্রুপগুলোর সবচেয়ে বেশি হওয়া যোগফলটিকে বা ম্যাক্সিমাম সামকে (maximum sum) সবচেয়ে কমিয়ে আনুন। একটি নির্দিষ্ট সম্ভাব্য ম্যাক্স সাম x এর জন্য, গ্রিডি বা লোভী উপায়ে চেক করে দেখুন আপনি এমন k টি গ্রুপ তৈরি করতে পারেন কি না যেখানে প্রতিটি গ্রুপের যোগফল ≤ x হয়। x এর ওপর [অ্যারের সর্বোচ্চ উপাদান, অ্যারের মোট যোগফল] রেঞ্জে বা সীমার মধ্যে বাইনারি সার্চ করুন। মোট সময়: \(O(n \cdot \log(total\ sum))\)।
কোকো এবং কলা খাওয়া (Koko eating bananas): কিছু কলার স্তূপ বা গাদা (piles) দেওয়া আছে, কোকোকে অবশ্যই H ঘণ্টার মধ্যে এগুলো শেষ করতে হবে। এর জন্য সর্বনিম্ন খাওয়ার হার k বের করুন। feasible(k) = সে কি k হারে এইচ (H) ঘণ্টার মধ্যে সমস্ত স্তূপের কলাগুলো শেষ করতে পারবে? [1, সর্বোচ্চ সংখ্যক কলার স্তূপ] এই সীমার মধ্যে k এর ওপর বাইনারি সার্চ করুন। মোট সময়: \(O(n \cdot \log(max\ pile))\)।
ইনটিজার স্কোয়ার রুট (Integer square root): কোনো দশমিক বা ফ্লোটিং পয়েন্ট (floating point) ছাড়াই ⌊√n⌋ খুঁজে বের করুন। feasible(x) = \(x^2\) ≤ n। [0, n] সীমার মধ্যে x এর ওপর বাইনারি সার্চ করুন। মোট সময়: \(O(\log n)\)।