বাইনারি সার্চ ইমপ্লিমেন্টেশন

আমরা গত সেকশনে বাইনারি সার্চ কীভাবে কাজ করে তা জানলাম। এখন আমরা শিখবো কীভাবে আমরা তা কোডে ইমপ্লিমেন্ট করতে পারি ।

বাইনারি সার্চ ইমপ্লিমেন্ট করতে হলে array টি অবশ্যই ascending order এ sorted থাকতে হবে।

বাইনারি সার্চ ইমপ্লিমেন্ট করার ক্ষেত্রে আমাদের কিছু স্টেপ ফলো করতে হবে।

1. প্রথমে আমাদের নির্ধারণ করতে হবে আমরা এই স্টেপে এরে কত টুকু অংশ জুড়ে এই ভ্যালুটি খুজবো , যাকে আমরা বলতেছি searching space. শুরুতে পুরো এরেটি আমাদের searching space হবে। আমরা দুটি ভ্যারিয়েবল low এবং high রাখবো যার সাহায্যে এই স্টেপে এরে এর কতটুকু অংশ নিয়ে কাজ করবো তার ট্র্যাক রাখবো। শুরুতে যেহেতু আমরা পুরো এরেতেই ভ্যালুটি খুজছি , তাই low পয়েন্ট করবে এরে এর o তম ইন্ডেক্সে এবং high পয়েন্ট করবে এরে এর শেষ ইনডেক্স n-1 এ। অর্থাৎ low = 0 , high = n-1

2. এরপর আমরা searching space এর mid বের করবো । mid index হবে (low+high)/2

3. এরপর চেক করে দেখবো mid index এ যে ভ্যালু আছে তা আমাদের কাঙ্খিত target এর সমান কিনা। সমান হলে এখানে সার্চ করা বন্ধ করে দিবো।

4. যদি আমাদের কাঙ্খিত ভ্যালু থেকে mid index এর ভ্যালু বড় হয় , তাহলে আমরা নিশ্চিত যে , ঐ মিড এলিমেন্ট ডান অংশে কখনো কাঙ্খিত ভ্যালু টি থাকতে পারে না , শুধু মাত্র mid এলিমেন্ট এর বাম অংশে থাকতে পারে। তাই আমরা আমাদের searching space টা mid index er বাম সাইডে নিয়ে আসবো । অর্থাৎ ,high = mid -1 করে দিবো।

5. যদি আমাদের কাঙ্খিত ভ্যালু থেকে mid index এর ভ্যালু ছোট হয় , তাহলে আমরা নিশ্চিত যে , ঐ মিড এলিমেন্ট বাম অংশে কখনো কাঙ্খিত ভ্যালু টি থাকতে পারে না , শুধু মাত্র mid এলিমেন্ট এর ডান অংশে থাকতে পারে। তাই আমরা আমাদের searching space টা mid index er ডান সাইডে নিয়ে আসবো । অর্থাৎ ,low = mid +1 করে দিবো।

6. এই স্টেপ গুলা আমরা করতে থাকবো যতক্ষন আমাদের একটা valid searching space থাকবে। অর্থাৎ যতক্ষন low<=high হবে ।

Code implementation :

#include <bits/stdc++.h>
using namespace std;

int main()
{

    int N, Q;
    cin >> N >> Q;

    int array[N];

    for (int i = 0; i < N; i++) // O(N) 
    {
        cin >> array[i];
    }

    sort(array, array + N); // O(NlogN)  এরে সর্ট করা হলো , যেহেতু বাইনারি সার্চের পূর্বশর্ত হলো এরে সর্ট থাকা

    for (int i = 0; i < Q; i++) // O(Q) 
    {

        int X;
        cin >> X;

        int flag = 0;
        
        // Binary Search O (logN) 

        int low = 0, high = N - 1; // low এবং high ভ্যারিয়েবলের মাধ্যমে আমরা searching space নির্ধারণ করলাম

        while (low <= high) // যতক্ষন এরেতে সার্চ করার মতো atleast একটি ভ্যালু থাকে। 
        {
            int mid_index = (low + high) / 2; // mid index বের করছি

            if (array[mid_index] == X) // যদি searching space এর মধ্যখানের element এর মান কাঙ্খিত মানের সমান হয়
            {
                flag = 1; // তবে flag এর মান ১ করে সার্চ করা এখানে বন্ধ করে দিচ্ছি
                break;
            }
            else if (array[mid_index] > X) // যদি searching space এর মধ্যখানের element এর মান কাঙ্খিত মানের চেয়ে বড় হয়  
            {
                high = mid_index - 1; // তবে আমরা mid_index এর  ডান সাইডের অংশ টুকু বাদ দিচ্ছি ,অর্থাৎ high কে mid_index এর ডানে নিয়ে আসছি
            }
            else if (array[mid_index] < X) // যদি searching space এর মধ্যখানের element এর মান কাঙ্খিত মানের চেয়ে ছোট হয়  
            {
                low = mid_index + 1; // তবে আমরা mid_index এর বাম সাইডের অংশ টুকু বাদ দিচ্ছি ,অর্থাৎ low কে mid_index এর ডানে নিয়ে আসছি
            }
        }

        if (flag)
            cout << "found" << endl;
        else
            cout << "not found" << endl;
    }
}

Time complexity Analysis :

উক্ত কোডের টাইম কমপ্লেক্সিটি হবে O (N + NlogN + Q*logN) => O (Q*logN). এখন প্রবলেমের constraints এ N এবং Q এর মান ম্যাক্সিমাম 10^5 পর্যন্ত হতে পারে। সুতারাং worst case এ আমাদের কোডটি O(Q*logN) অর্থাৎ (10^5 * log2(10^5)) = (10^5 * 17) = 17 *10^5 টি অপারেশন করবে। এবং যেহেতু আমরা জানি 1sec e ম্যাক্সিমাম 10^8 টি অপারেশন করা যায় , তাই এই কোড এক সেকেন্ড এ খুব সহজে পাস করবে।

খুব চমৎকার একটি বিষয়। আমরা আমাদের কোডের কমপ্লেক্সিটি O( Q*N) হতে কমিয়ে O(Q*logN) এ নিয়ে আসলাম যা আসলে অনেক বড় একটি ইম্প্রুভমেন্ট। তাহলে আমরা এই মডিউল শেষে শিখলাম কীভাবে একটি এরে হতে খুব দ্রুত একটি ভ্যালু খুজে বের করে নিয়ে আসতে হয়। আমরা পরবর্তীতে এমন আরো কিছু ইন্টারেস্টিং টেকনিক / এলগরিদম দেখবো। শুভ কামনা রইলো সবার জন্য।