Binary Search (Codeforces)

Problem Link : https://codeforces.com/group/MWSDmqGsZm/contest/219774/problem/Z

Question Analysis :

প্রবলেমে বলা হয়েছে আপনাকে দুইটি নাম্বার N এবং Q দেয়া হবে। একটি N সাইজের এরে দেয়া হবে। এরপর থেকে Q সংখ্যক কুয়েরি জিজ্ঞেস করা হবে যেখানে প্রত্যেকটি কুয়েরি তে একটি ভ্যালু দেয়া থাকবে X . আপনার প্রত্যেকটি কুয়েরি এর জন্য উত্তর দিতে হবে , উক্ত এরেটি্র মধ্যে X ভ্যালুটি আছে কিনা ।

Example Analysis : আমরা Example টি নিয়ে আলোচনা করবো।

Array	1	5	4	3	2
Index	0	1	2	3	4

এখানে কুয়েরি গুলা হলোঃ প্রথম কুয়েরি -> X = 5 , অর্থাৎ 5 এই এরে এর মধ্যে আছে কিনা তা উত্তর দিতে বলা হয়েছে। এই এরে এর 1 নাম্বার ইনডেক্স এ ভ্যালু 5 আছে। তাই এর উত্তর হলো found.

দ্বিতীয় কুয়েরি -> X = 3 , অর্থাৎ 3 ভ্যালুটি এই এরে এর মধ্যে আছে কিনা তা উত্তর দিতে বলা হয়েছে। এই এরে এর 3 নাম্বার ইনডেক্স এ ভ্যালু 3 আছে। তাই এর উত্তর হলো found.

তৃতীয় কুয়েরি -> X = 6 , অর্থাৎ 6 ভ্যালুটি এই এরে এর মধ্যে আছে কিনা তা উত্তর দিতে বলা হয়েছে। এই এরে এর কোন ইন্ডেক্সে ভ্যালু 6 নেই। তাই এর উত্তর হলো not found.

Naive approach :

#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++)
    {
        cin >> array[i];
    }

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

        int X;
        cin >> X;

        int flag = 0;

        for (int j = 0; j < N; j++) // O (N) 
        {

            if (array[j] == X)
            {

                flag = 1;
            }
        }

        if (flag)
            cout << "found" << endl;
        else
            cout << "not found" << endl;
    } // O (Q*N) 
}

আমরা প্রতিটি কুয়েরি এর জন্য একটি লুপ চালাচ্ছি যার কমপ্লেক্সিটি হবে O (Q) এবং কোন ভ্যালু টা খুজতে হবে তা ইনপুট এ নিচ্ছি । এরপর ঐ লুপের এরে টির প্রত্যেকটি এলিমেন্টে লুপের সাহায্যে যেয়ে দেখবো যে আমাদের টার্গেট ভ্যালু এর সাথে মিলছে কিনা। এবং এরের সাইজ যেহেতু N তাই আমাদের প্রত্যেকটি কুয়েরি তে worst case এ পুরো এরেটি খুজে দেখতে হবে , তাই ভিতরের লুপের কমপ্লেক্সিটি O(N) , তাই এই কোডের overall টাইম কমপ্লেক্সিটি হলো O(Q*N).

এখন প্রবলেমের constraints এ N এবং Q এর মান ম্যাক্সিমাম 10^5 পর্যন্ত হতে পারে। সুতারাং worst case এ আমাদের O(Q*N) কমপ্লেক্সিটি এর কোড (10^5 * 10^5) টি = 10^10 অপারেশন করবে। এবং যেহেতু আমরা জানি 1sec e ম্যাক্সিমাম 10^8 টি অপারেশন করা যায় , তাই এই কোড এক সেকেন্ড এ পাস করবে না এবং TIME LIMIT EXCEEDED হবে।

সুতারাং আমাদের এই কোড টি আরও অপটিমাইজ করতে হবে। নেক্সট পেইজে আমরা এই বিষয় সম্পর্কে জানবো।