বাইনারি সার্চ – ২ (বাইসেকশন)

আগের পর্বে আমরা দেখেছি কীভাবে একটি ডিসক্রিট (Discrete) অ্যারেতে বাইনারি সার্চ কাজ করে। কিন্তু অনেক সমস্যা আছে যেখানে আমরা কোনো অ্যারেতে সার্চ করি না, বরং একটি কন্টিনিউয়াস (Continuous) রেঞ্জের মধ্যে আমাদের উত্তর খুঁজতে হয়। একে সাধারণত বাইসেকশন মেথড (Bisection Method) বলা হয়।

বাইসেকশন মেথড কী?

ধরি, তুমি জানো যে একটা সমীকরণের মান $x = 0$ এর জন্য নেগেটিভ এবং $x = 100$ এর জন্য পজিটিভ। যেহেতু মানটি নেগেটিভ থেকে পজিটিভ হয়েছে, তার মানে মাঝখানে কোথাও এর মান ০ হয়েছে (যদি ফাংশনটি কন্টিনিউয়াস হয়)। এখন ঠিক কোন মানে ০ হয়েছে, সেটা বের করতে আমরা বাইসেকশন ব্যবহার করতে পারি।

পদ্ধতি:

1. আমরা $high = 100$ এবং $low = 0$ ধরি।
2. আমরা মাঝের মান $mid = (high + low) / 2$ বের করি।
3. $f(mid)$ এর মান চেক করি। যদি তা নেগেটিভ হয়, তবে আমাদের উত্তর $mid$ থেকে $high$ এর মাঝে আছে। তাই $low = mid$ করে দিই।
4. যদি তা পজিটিভ হয়, তবে আমাদের উত্তর $low$ থেকে $mid$ এর মাঝে আছে। তাই $high = mid$ করে দিই।

যেহেতু এটা কন্টিনিউয়াস স্পেস, আমরা $low \le high$ দিয়ে লুপ চালাই না। বদলে আমরা একটা নির্দিষ্ট এরর সাইজ বা ইটারেশন কাউন্ট ব্যবহার করি, যেমন while (high - low > 0.0000001) অথবা নির্দিষ্ট ১০০ বার লুপ চালাই।

C++ Implementation

একটি সংখ্যার বর্গমূল (Square Root) বের করার জন্য বাইসেকশন মেথডের ব্যবহার:

#include <iostream>
using namespace std;

double get_sqrt(double n) {
    double low = 0.0;
    double high = max(1.0, n); // n যদি ১ এর ছোট হয়, তবে উত্তর n এর চেয়ে বড় হবে 
    double mid;

    // আমরা সুনির্দিষ্ট উত্তরের জন্য ১০০ বার লুপ চালাবো
    for (int i = 0; i < 100; i++) {
        mid = low + (high - low) / 2.0;

        if (mid * mid < n) {
            low = mid;
        } else {
            high = mid;
        }
    }
    
    return mid;
}

int main() {
    cout << "Square root of 25 is " << get_sqrt(25.0) << endl;
    cout << "Square root of 2 is " << get_sqrt(2.0) << endl;
    return 0;
}

এখানে $O(\log n)$ কমপ্লেক্সিটি মেইনটেইন করেই খুব দ্রুত আমরা ফ্র্যাকশনাল উত্তর বের করে ফেলতে পারছি। বাইসেকশন মেথড ম্যাথমেটিক্স এবং কম্পিটিটিভ প্রোগ্রামিংয়ে প্রচুর ব্যবহার হয়!