খোঁজ দ্য বাইনারী সার্চ

অালাল আর দুলাল, দুই বন্ধু। ছোটোবেলা থেকেই দুইজন একসাথে খায়, ঘুমায়, আড্ডা দেয়। কিন্তু সমস্যা একটাই, দুইজনই পছন্দ করে জরিনাকে। দুইজনই চায় জরিনাকে বিয়ে করতে, কিন্তু এ নিয়ে দুই বন্ধু নিজেদের মধ্যে বিবাদ করতে চায় না, আবার কেউই জরিনাকে ছাড়তে চায় না। শেষে দুইজন মিলে সিদ্ধান্ত নিলো জরিনার বাবা চৌধুরী সাহেব যাকে পছন্দ করবেন সেই বিয়ে করবে জরিনাকে। দুইজন তাদের প্রস্তাব নিয়ে গেলাে জরিনার বাড়ীতে। এখন চৌধুরী সাহেব পড়লেন বিপদে। কাকে পছন্দ করবেন? তিনি দুইজনকেই ভালো ছেলে বলে জানেন। তিনি চিন্তা করলেন দুইজনকে একটা পরীক্ষা করবেন। তিনি ১০০ টা বাক্সে ভিন্ন ভিন্ন ওজনের পাথর রাখলেন, আর বললেন, “এখানে ওজন অনুসারে পাথরগুলো ক্রমানুসারে সাজানো আছে। তোমাদের দুইজনকে দুইটি ওজন মাপার যন্ত্র দেয়া হলো। তোমাদের খুঁজে বের করতে হবে, কোন বাক্সে ৬২ কেজি ওজনের পাথরটি আছে। যে আগে খুঁজে বের করতে পারবে তাকেই জরিনার সাথে বিয়ে দেয়া হবে।” ……………
গল্পের মাঝখানে যারা ভাবছেন ‘why 62?’ তাদের জন্য বলি, ‘৬২’ হলো চৌধুরী সাহেবের বয়স, আর যারা ভাবছেন ‘এটা কেমন পরীক্ষা?’ তাদের জন্য বলি, “চৌধুরী সাহেবের খুশী,উনি যেমন ইচ্ছা পরীক্ষা নিবে। আপনার কি?”…………..যাই হোক, ফিরে যাই গল্পে……………….
…………….চৌধুরী সাহেবের কথা শুনেই আলাল আর দুলাল নেমে পড়লো পাথর খুঁজতে। গল্পের শুরুতে যেটা বলা হয়নি সেটা হলো, আলাল আর দুলাল সবকিছু একসাথে করলেও দুইজনের মধ্যে একটা ছোট্টো পার্থক্য ছিলো। আলাল খেতো সাধারণ লবন আর দুলাল খেতো আয়োডিনযুক্ত লবণ, যার কারণে দুলালের মাথায় বুদ্ধি বেশি। তাই যখন আলাল প্রথম থেকে একটা একটা করে বাক্সের পাথর ওজন করতে শুরু করলো, দুলাল তখন করলো অন্য কাজ। সে প্রথমেই মাঝখানের ৫০তম বাক্সটার (মোট ১০০টা বাক্স ছিলো কিন্তু) পাথর ওজন করলো, সেখানে পেলো ‘৮৩’ কেজি ওজনের একটা পাথর। তখন সে চিন্তা করলো যেহেতু পাথরগুলি ওজন অনুসারে ক্রমানুসারে সাজানো আছে, সুতরাং ডানদিকের সবগুলো বাক্সের পাথরের ওজন এটা থেকে বেশি হবে। তারমানে ‘৬২’ কেজি ওজনের পাথর বাম দিকের ৫০ টা বাক্সের মধ্যেই আছে। এরপর সে খুঁজলো বামদিকের ৫০ টি বাক্সের মাঝখানেরটিতে অর্থাৎ ২৫ তম বাক্সে। দেখলো সেখানের পাথরটির ওজন ‘৩০’ কেজি। তারমানে বাম দিকের প্রথম ২৫টা বাক্স বাদ। সুতরাং ২৬তম থেকে ৪৯তম বাক্সের মধ্যেই আছে ‘৬২’ কেজির পাথরটি। এভাবে সে তার খোঁজা চালিয়ে গেলো। গল্প এখানেই শেষ………………………….

এখন পাঠকদের কাছে প্রশ্ন হলো, কে সবার আগে পাথরটি খুঁজে বের করতে পারবে?

প্রশ্নের উত্তর পাওয়া যাবে একটু পরেই। তারপর আগে কিছু কাজের কথা বলে নেয়া দরকার।

উপরের গল্পে আলাল যেই পদ্ধতিতে পাথরটি খুঁজতে শুরু করেছে সেটাও কোনো ফেলনা পদ্ধতি নয়, এটারও একটা সুন্দর নাম আছে। যেটা হলো, ‘Linear Searching’, এবং এটাও একটা প্রতিষ্ঠিত পদ্ধতি। Linear search একেবারেই সোজাসাপটা একটা পদ্ধতি, যেখানে যে কোনো একদিক থেকে সবগুলো জিনিস খুঁজতে থাকা হয় যতক্ষণ না যেটা খোঁজা হচ্ছে সেটা পাওয়া যাচ্ছে। এভাবে খুঁজতে থাকলে একটাই সমস্যা সেটা হলো যেদিক থেকে খোঁজা শুরু করা হলো, কাঙ্খিত বস্তুটি যদি একেবারে অপর প্রান্তে থাকে তাহলে সবগুলো জিনিস খুঁজে দেখা লাগবে আর তাতে করে সময়ও লাগবে অনেক বেশি।

আর দুলাল যে পদ্ধতিতে পাথর খুঁজছে সেটাই মূলত এই আর্টিকেলের আলোচ্য বিষয় যার নাম হচ্ছে, বাইনারী সার্চ (Binary Search)। কেনো এ পদ্ধতির নাম বাইনারী সার্চ এটা বুঝলেই এই পদ্ধতি কিভাবে কাজ করে তার প্রায় সবটা বোঝা হয়ে যায়। আমরা যদি উপরের গল্পে আবার খেয়াল করে দেখি তাহলে দুলালের পদ্ধতিটিকে এভাবে ব্যাখ্যা করা যায়-

খুঁজতে শুরু করার আগে দুলালের জন্য মোট বাক্স ছিলো ১০০টি। সে সেখান থেকে মাঝখানের বাক্সটি বেছে নিয়ে সেখানে কাঙ্খিত পাথরটি আছে কিনা দেখলো। সেখানে না পেয়ে সে ডান দিকের অর্ধেক (৫০টি) বাক্সকে তার হিসাবের থেকে বাদ দিয়ে বাম দিকের বাক্সে খুঁজতে শুরু করলো। এভাবে সে প্রতি বার তার খোঁজার ক্ষেত্রকে দুইভাগে ভাগ করে ফেলেছে এবং এই সিদ্ধান্ত নিয়েছে যে কোনভাগে বস্তুটি থাকার সম্ভাবনা আছে আর কোনভাগে থাকার সম্ভাবনা একেবারেই নেই। একারণেই এই পদ্ধতির নাম বাইনারী সার্চ।

খুব সহজ একটা ব্যাপার তাই না? এতক্ষণে বাইনারী সার্চের কনসেপ্টটা ক্লিয়ার হয়ে যাওয়ার কথা। তারপরও একটা ছবি দেখি-

40163

এখানে আমাদের প্রথমে একটা এ্যারেতে ১,২,৩,৪,৬,৭,৯ এলিমেন্টগুলো দেয়া আছে। সেখান থেকে আমরা দেখতে চাচ্ছি আমাদের এ্যারেতে ‘৬’ আছে কিনা। প্রত্যেকটা স্টেপে আমরা আমাদের সার্চের এরিয়াকে (n/2) তে কমিয়ে আনছি(হলুদ রঙের ঘরগুলো সার্চ এরিয়া) আর কারেন্ট সার্চ এলিমেন্ট বিবেচনা করছি ঐ এরিয়ার মাঝখানের এলিমেন্টটাকে। ঐ এলিমেন্টটা আমাদের কাঙ্খিত এলিমেন্ট না হলে আমরা সহজেই বলে দিতে পারছি আমাদের কাঙ্খিত এলিমেন্টটা কি ডানে নাকি বামে আছে। কারণ আমাদের সবগুলো এলিমেন্ট সর্টেড (sorted) আছে।

এখন কনসেপ্ট যদি বোঝা হয়ে থাকে তাহলে বাইনারী সার্চ কোড করাটা কি খুব কঠিন কিছু? মোটেও না। এই যে একটা বাইনারী সার্চের স্যুডোকোড (pseudo-code) –

binary_search(A, target):
   lo = 1, hi = size(A)
   while lo <= hi:
      mid = lo + (hi-lo)/2
      if A[mid] == target:
         return mid
      else if A[mid] < target:
         lo = mid+1
      else:
         hi = mid-1

   // target was not found

 যেখানে একটা ফাংশন তৈরি করা হয়েছে বাইনারী সার্চের জন্য। এখানে A হচ্ছে এ্যারেটা যেখানে আপনার এলিমেন্টগুলো থাকবে, target হচ্ছে যেই এলিমেন্টটাকে খোঁজা হচ্ছে, lo হচ্ছে এ্যারের প্রথম ঘর যেটা এখানে 1 ধরা হয়েছে, hi হচ্ছে এ্যারের শেষ পজিশন। একটু ভালো করে খেয়াল করলেই কোডটা কিভাবে কাজ করছে বোঝা যায়, প্রয়োজনে খাতা কলমে স্যাম্পল এলিমেন্ট নিয়ে করে দেখতে পারেন তাহলে আরো সহজ হয়ে যাবে ব্যাপারটা। এই স্যুুডোকোডটাকেই আপনি আপনার জানা ল্যাংগুয়েজে খুব সহজে কোড করে ফেলতে পারবেন।
এই কোডটাতে কেনো mid = (lo+hi)/2 না করে mid = lo + (hi-lo)/2 করা হয়েছে সেটা ভালোভাবে বুঝতে এই লিংকটাতে একটু ঢুঁ মেরে আসলে ভালো হয়। এখানেও একটা সুন্দর, কাজের আর্টিকেল আছে।

যদিও বাইনারী সার্চ কোড করাটা বেশ সহজ তারপরও একটু কিন্তু(!) থেকে যায়। যেটা এই পোস্টটা দেখলে পরিস্কার হয়ে যাবার কথা। পোস্টটায় খুব সুন্দর করে ব্যাখ্যা করা আছে তাই আমি জাস্ট লিংক দিয়ে দিলাম। পোস্টের লেখক আবুু আসিফ খানকে ধন্যবাদ সুন্দর করে বিষয়টা ব্যাখ্যা করার জন্য।

বাইনারী সার্চ কেনো লিনিয়ার সার্চ থেকে ভালো সেটা একটু চিন্তা করলেই বলে দেয়া যায়। আগেই বলেছি, লিনিয়ার সার্চের ক্ষেত্রে আমাদের যদি এলিমেন্টটা যেদিক থেকে সার্চ করছি তার উল্টো প্রান্তে থাকে তাহলে আমাদের সবগুলো এলিমেন্ট খুঁজে দেখা লাগবে, সেক্ষেত্রে লিনিয়ার সার্চের কমপ্লেক্সিটি হয়, O(n). কিন্তু বাইনারী সার্চের বেলায় আমাদের সবচাইতো worst case এর ক্ষেত্রেও কমপ্লেক্সিটি হবে O(log n). কারণ আমাদের এলিমেন্টটা যেখানেই থাকুক না কেন আমাদের সর্বোচ্চ logN বার সার্চ করতে হবে, কারণ আমরা প্রতিবার আমাদের সার্চ এরিয়াকে (N/2) তে কমিয়ে আনছি। সুতরাং বোঝাই যাচ্ছে, বাইনারী সার্চ লিনিয়ার সার্চ থেকে বেশ এফিসিয়েন্ট। এলগোরিদম কমপ্লেক্সিটি নিয়ে আরেকটু ভালো বুঝতে চাইলে এই পোস্টটা দেখা যেতে পারে।

আমরা কিভাবে বুঝবো কখন আমরা বাইনারী সার্চ ব্যবহার করতে পারবো?? আগে একটা মজার ব্যাপার বলে নেই। আমি যখন প্রথম বাইনারী সার্চ শিখি তারপরে অনেকদিন পর্যন্ত আমি মনে করতাম, যদি আমাকে অনেকগুলো নাম্বার দিয়ে জিগ্যেস করে এর মধ্যে কোনো একটা নাম্বার আছে কিনা তখন আমি নাম্বারগুলোকে সর্ট(sort) করে সেখানে বাইনারী সার্চ করে বলে দিবো নাম্বারটা আছে কিনা বা কোন পজিশনে আছে। এই ধরনের পরিস্থিতির বাইরে কোথাও বাইনারী সার্চ ব্যবহার করা যেতে পারে সেটা আমার মাথায়ই ছিলো না। তারপরে বেশ কিছু মজার প্রবলেম সলভ করতে গিয়ে বাইনারী সার্চের মাহাত্ম্য(!) ভালো করে বুঝতে পারলাম। 🙂

আসল ব্যাপারটা হলো, আমাদের সার্চ এলিমেন্টগুলোকে যদি monotonic function এ রিপ্রেজেন্ট করতে পারি তাহলে আমরা সেখানে বাইনারী সার্চ চালাতে পারবো। সহজভাবে বলতে গেলে, monotonic function মানে হলো আমাদের সার্চ লিস্টের এলিমেন্টগুলো যেনো অবশ্যই increasing অথবা decreasing অর্ডারে থাকে। আমাদের এলিমেন্টগুলোকে যদি এভাবে দেয়া না থাকে বা আমরা যদি এভাবে সাজাতে না পারি তাহলে সেখানে বাইনারী সার্চ কাজ করবে না।

নীচের উদাহরণটা দেখলে আশা করি বিষয়টা আরো পরিস্কার হবে।

আচ্ছা, আমরা তো সবসময়ই কোনো একটা নাম্বারের square root বের করার জন্য <math.h> এর বিল্ট ইন ফাংশন sqrt() ব্যবহার করি। কখনো কি ভেবে দেখেছি যদি আমাকে বলা হয় নিজেই এরকম একটা ফাংশন বানাও তখন কি আমি পারবো?
সেই কাজটাই এখন আমরা করবো।
মনে করি আমাদেরকে বলা হলো ১০ এর স্কয়ার রুট বের করতে। এখন আমরা দেখি যে, আমাদের কাঙ্খিত উত্তরটা কোথায় আছে? ১০ এর স্কয়ার রুট অবশ্যই ১০ এর থেকে ছোটো হবে এবং অবশ্যই ০ এর থেকে বড় হবে। তারমানে আমাদের সার্চ স্পেস হচ্ছে ০ থেকে ১০, যেটা আসলে অলরেডি সর্টেডই আছে। তারমানে আমরা খুব সহজেই এখান থেকে আমাদের কাঙ্খিত উত্তরটা পেতে পারি বাইনারী সার্চ ব্যবহার করে। কোনটা আমাদের কাঙ্খিত উত্তর সেটা কিভাবে বুঝবো? ধরি, আমাদের উত্তরটা x, যখনই আমরা একটা নাম্বারকে আমাদের কাঙ্খিত উত্তর বলে ধারণা করবো আমরা চেক করে দেখবো (x*x == ১০) কিনা। যদি হয় তাহলে সেই x ই আমাদের উত্তর। যদি (x*x)>10 হয় তাহলে আমাদের কাঙ্খিত উত্তর x এর চেয়ে ছোটো হবে। আর (x*x<10) হলে উত্তর x এর চেয়ে বড়। ব্যস এটাকে কোডে বসাতে পারলেই হয়ে গেলো আমাদের স্কয়ার রুট বের করার কোড। একটা স্যাম্পল কোড হতে পারে এরকম-
#include<bits/stdc++.h>

using namespace std;

#define eps 0.000001

int main()
{
    float num,mid;

    cin>>num;
    float lo=0;
    float hi = num;

    while(true)
    {
        mid = lo+(hi-lo)/2;
        float sq = mid*mid;
        if(fabs(sq-num)<=eps)
            break;
        if(sq>num)
            hi = mid;
        else
            lo = mid;
    }

    cout<<mid<<endl;

    return 0;
}

এখানে যেহেতু আমাদের ফ্লোটিং পয়েন্ট নাম্বার নিয়ে কাজ করতে হয়েছে তাই চেকিংটা ইন্টিজার নাম্বারের মতো না হয়ে একটু ভিন্ন হয়েছে।

এটা একটা খুব সুন্দর উদাহরণ যেটা প্রথম দেখাতেই হয়তো নাও মনে হতে পারে যে বাইনারী সার্চ দিয়ে এত সহজে সলভ করা যায়।
বিচক্ষণ পাঠক উপরের উদাহরণটায় আরেকটা জিনিস হয়তো বুঝে ফেলেছেন। তারপরও একটু ব্যাখ্যা করি।
আমাদের এই উদাহরণটাতে আমরা একটা নাম্বার x খুঁজে বের করেছি যেটা কিনা আমাদের prediction কে fulfill করে। আমাদের prediction টা ছিলো যে এই নাম্বারটা ১০ এর স্কয়ার রুট। এটা সত্য হতে হলে x*x=10 হতে হবে। এখানে এই শর্তটাকে আমরা বলতে পারি, predicate function, যেটা আমাদের প্রাপ্ত নাম্বারটাই সঠিক উত্তর কিনা সেটা চেক করে। প্রবলেমের ডেসক্রিপশনের উপর ভিত্তি করে এই prediction function টা বিভিন্ন রকম হতে পারে। কিন্তু এই ব্যাপারটা মাথায় রাখলে প্রবলেমটা যে বাইনারী সার্চ দিয়ে সলভ করা সম্ভব সেটা বোঝা সহজ হয়।
UVa অনলাইন জাজের Pie ,এই প্রবলেমটা আশা করি এখন আপনি সলভ করতে পারবেন। 🙂

বাইনারী সার্চের আরো কিছু মজার প্রবলেম আছে। যেমন codeforces 483B প্রবলেমটায় আপনাকে cnt1, cnt2 , x, y চারটা নাম্বার দেয়া থাকবে। x,y দুইটা প্রাইম নাম্বার। আপনাকে সবচাইতে ছোটো এমন একটা নাম্বার, মনে করি z, খুঁজে বের করতে হবে যেটার জন্য এই কন্ডিশনটা সত্যি হয়- “1 থেকে z এর মধ্যে কমপক্ষে cnt1 টা নাম্বার আছে যাদেরকে x দিয়ে ভাগ করলে ভাগশেষ 0 হবে না এবং 1 থেকে z এর মধ্যে কমপক্ষে cnt2 টা নাম্বার আছে যাদেরকে y দিয়ে ভাগ করলে ভাগশেষ 0 হবে না” ।
এখানে দুইটা জিনিস লক্ষ্যণীয়, প্রথমত এই কন্ডিশনটাই আমাদের prediction function আর দ্বিতীয়ত আমার কাঙ্খিত উত্তরটি যদি z হয়, তাহলে z থেকে বড় সবগুলো নাম্বারই এই কন্ডিশনটাকে fulfill করবে। আমাকে বাইনারী সার্চের কন্ডিশনটাকে এমনভাবে সাজাতে হবে যাতে করে যেকোনো একটা নাম্বার এই prediction function কে সত্যি প্রমাণ করলেই আমার সার্চিং শেষ না হয়ে যায়। আমাকে ততক্ষণ পর্যন্ত খুঁজতে হবে যতক্ষণ না নিশ্চিত হওয়া যায় যে প্রাপ্ত নাম্বারের চেয়ে ছোটো আর কোনো নাম্বারই prediction function কে সত্যি প্রমাণ করবে না।
উপরের কথাগুলি হয়তো একটু কঠিন মনে হতে পারে। সলিউশনটা এখানে দিয়ে দিচ্ছি, আশা করি এটা দেখলে কথাগুলি বুঝতে সুবিধা হবে।

#include<bits/stdc++.h>

using namespace std;
#define maxim 0x7FFFFFFF //highest possible positive value of 32 bit int
int main()
{
    int cnt1,cnt2,x,y;

    cin>>cnt1>>cnt2>>x>>y;

    int lo=1,hi=maxim,mid;

    while(lo<hi)
    {
        mid = lo+(hi-lo)/2;

        int remx = mid - (mid/x); //count the nuumber of elements which give remainder other than 0 dividing by x
        int remy = mid - (mid/y); //count the nuumber of elements which give remainder other than 0 dividing by y
        int totrem = mid - (mid/(x*y)); //The total number of elements which are not divided by both x and y, like 6 which is divisible by 2 and 3

        if(cnt1<=remx && cnt2<=remy && cnt1+cnt2<=totrem) //predicate function
            hi = mid;
        else
            lo = mid+1;
    }

    cout<<hi<<endl; //hi was the last smallest value which holds predicate function true

    return 0;
}

আশা করি এতক্ষণে অন্তত বাইনারী সার্চের কনসেপ্টটা সবাই ধরতে পেরেছেন। বাইনারী সার্চের উপর নেটে পাওয়া সবচাইতে ভালো টিউটরিয়ালটি হলো টপকোডারের টিউটরিয়ালটি। সময় করে এটি দেখে নিতে পারেন।

বাইনারী সার্চের প্রবলেম খুঁজছেন সলভ করার জন্য?? নীচের লিংকগুলো আপনাকে সাহায্য করবে আশা করি।

SPOJ binary search problems.
UVa Binary Search problems.
Codeforces binary search problems.
A2OJ Problem List.

বাইনারী সার্চ দিয়ে কিভাবে আরো সুন্দর সুন্দর প্রবলেম সলভ করা যায় সেটি জানতে নীচের লিংকগুলো দেখা যেতে পারে।
শাকিল আহমেদের ব্লগ
মুকিত ভাইয়ের ব্লগ

Happy coding………………………….. 🙂

Want to like or share?:
0

12 comments

  1. superb!!!
    নতুন যে কাউকে বুঝানোর জন্য এর থেকে সহজে মনে হয় ডেস্ক্রাইব করা সম্ভব না।
    দুই-এক জায়গায় একটু টাইপিং মিসটেক আছে। আশা করছি সেটা ঠিক হয়ে যাবে।
    বাইনারি সার্চ এলগো ইউজ করে solve করতে হবে এমন কিছু প্রবলেম লিংক সাথে দিলে সুবিধা হত… 🙂

    [ফেসবুকে লাইকের প্লাগইনটা এড করে দিয়েন। প্রতিটা পোস্ট তাহলে খুব সহজেই স্প্রেড হতে পারবে]

    1. সাধারণভাবে আমরা একটা ইন্টিজার নাম্বারের সাথে আরেকটা ইন্টিজার নাম্বার সমান কিনা সেটা তুলনা করতে পারি ‘=’ অপারেটর দিয়ে। কিন্তু ফ্লোটিং পয়েন্ট নাম্বারের ক্ষেত্রে এভাবে করলে ভুল হয়। সেক্ষেত্রে eps একটা নাম্বার ধরে নেয়া হয়েছে যত ঘর পর্যন্ত দুইটা ফ্লোটিং পয়েন্ট নাম্বার ম্যাচ করলে সেটাকে ইক্যুয়াল ধরা হবে সেটার জন্য। এটাকে প্রয়োজন অনুযায়ী কম বেশি ধরে নেয়া যায়। আমি এখানে ৬ ঘর ধরেছি। এখন যেকোনো দুইটা ফ্লােটিং পয়েন্ট এর ব্যবধান যদি এই eps এর কম বা সমান হয় তাহলে সেই দুইটা নাম্বারকে এখানে সমান বিবেচনা করা হচ্ছে।

Leave a Reply

Your email address will not be published. Required fields are marked *