বাইনারি সার্চ অ্যালগরিদম – Binary Search Algorithm

Post updated on 10th April, 2020 at 10:55 pm

তোমাকে ১৫০০ পৃষ্ঠার ইয়া মোটকা ডেইটেলের Java – How to Program বইটা হাতে দিয়ে বললাম ৮২২ নম্বর পৃষ্ঠায় কী বলা আছে পড়। তুমি কী করবে? বইটা বাম হাতে নিবে, ডান হাত দিয়ে প্রথম পৃষ্ঠা উল্টাবে। দেখবে সেটা ৮২২ নম্বর পৃষ্ঠা না, এরপর দ্বিতীয় পৃষ্ঠা উল্টাবে, এরপর তৃতীয়, চতুর্থ… এরকম করে কি পেজ উল্টাতে থাকবে? নিশ্চয়ই না!!! এভাবে শুরুর থেকে একটা একটা করে চেক করে সামনের দিকে আগানোর পদ্ধতিতে কেতাবি ভাষায় আমরা বলি Linear Search Algorithm.

স্বাভাবিক ভাবেই তুমি বইয়ের প্রথম পৃষ্ঠা না খুলে একদম মাঝ বরাবর খুলবে। কারণ তুমি জানো বইয়ের পেজ সংখ্যা ১৫০০ আর বের করতে হবে ৮২২ নাম্বার পেজ। তার মানে ৮২২ বইয়ের মাঝামাঝির দিকেই থাকবে। তুমি মাঝখানে খুলে দেখলে পেজ নম্বর বের হয়েছে ৭৫০। এখন বইয়ের পেজগুলো তোমার সামনে দুই ভাগে বিভক্ত হয়ে গেছে। বাম পাশের ভাবে ৭৫০ এর চেয়ে কম মানের সব পেজ নম্বর। আর ডান পাশের ভাগে ৭৫০ এর চেয়ে বড় মানের সব পেজ নম্বর। তোমার যেহেতু ৮২২ দরকার তাই তুমি বাম পাশের ভাগে কিন্তু আর ৮২২ কে খুঁজবেই না। তুমি খোঁজাখুঁজির কাজ করবা ডান পাশে থাকা পেজগুলোর মধ্যে, তাই না?

• লিনিয়ার সার্চ অ্যালগরিদমঃ সবচেয়ে সহজ সার্চিং অ্যালগরিদম

এবার ধরো, ডান পাশের পেজগুলোই একটা আলাদা বই। যার পেজ নাম্বার শুরু হয়েছে ৭৫১ থেকে আর শেষ হয়েছে ১৫০০-তে গিয়ে। এখন তুমি যা করতে পারো, এই নতুন পার্টের মাঝামাঝি অংশ খুলো। একদম মাঝের পেজ নাম্বার হবে (751+1500)/2= 1125. এখন এই নতুন পার্টের মধ্যে আবার দুইটা পার্ট হয়ে গেল। বাম পাশে থাকবে ৭৫১ থেকে ১১২৫ নম্বর পেজ আর ডান পাশে থাকবে ১১২৬ থেকে ১৫০০ নম্বর পেজ। তোমার দরকার ৮২২, এটা এই পার্ট দুটির কোন অংশে থাকার সম্ভাবনা আছে? হ্যাঁ ঠিক ধরেছ! বাম পাশের অংশ অর্থাৎ ৭৫১ থেকে ১১২৫ নম্বর পেজের মধ্যেই ৮২২ নম্বর পেজ থাকবে (যদি কেউ পেজ ছিঁড়ে ফেলে না থাকে 😛 ). তাহলে আমাদের খোঁজাখুঁজি চালিয়ে যেতে হবে ৭৫১ থেকে ১১২৫ এর অংশের মধ্যে। ডান পাশের অংশ নিয়ে আমরা আর চিন্তা করব না। এখন মনে করো ৭৫১-১১২৫ এটা একটা নতুন বই। আবার এর মাঝামাঝি অংশ খুলো। পেজ নাম্বার হবে ৯৩৮, যা ৮২২ এর চেয়ে বড়। তার মানে এই নতুন পার্টের বাম পাশের অংশে আবার খুঁজতে হবে। নতুন বই হল ৭৫১-৯৩৮। এটাকে আবার মাঝখান থেকে খুলো… এভাবে বইটাকে প্রতিবার অর্ধেক করতে করতে এক সময় দেখা যাবে নতুন বই হয়েছে এক পেজের। আর সেই পেজ নাম্বারটা হচ্ছে ৮২২ অথবা একটা মাঝের পেজ খুললা, দেখা যাবে সেই মাঝের পেজটাই ৮২২।

বর্ণনা করে লিখতে গেলে অনেক অনেক লিখতে হয়। জটিলও মনে হতে পারে। কিন্তু আমরা এ কাজটা সব সময়ই করে থাকি। পেজ খুঁজে বের করা বা ডিকশনারি থেকে কোন শব্দ খুঁজে বের করা (আচ্ছা ডিকশনারি চিন তো? তুমি যদি অনেক জুনিয়র হয়ে থাকো তাহলে না-ও চিনতে পারো। অনেক অনেক অ্যাপ বা গুগল ট্রান্সলেটর ইউজ করো শব্দের অর্থ জানতে। আমরা ছোট বেলায় ইয়া মোটকা ডিকশেনারি নিয়ে বসতাম শব্দের উচ্চারণ আর অর্থ জানতে। 🙂 )। এই টাইপের খোঁজাখুঁজির কাজের ক্ষেত্রে আমরা যেই পদ্ধতি অনুসরণ করি সেটাকেই নাম দেয়া হয়েছে বাইনারি সার্চ। এর আরো দুটি নাম রয়েছেঃ Half-interval Search ও Logarithmic Search. আমাদের ব্রেইন যেই পদ্ধতিতে এ ধরণের ডেটা খুঁজে সেটা অনেক ফাস্ট আর ইফিসিয়েন্ট। তাই এই একই পদ্ধতিতে কম্পিউটারকে কাজ করানোর জন্যেই বাইনারি সার্চ অ্যালগরিদম। Binary Search Algorithm এর Complexity হচ্ছে O(log n) যেখানে Linear Search এর কমপ্লেক্সিটি O(n).

বাইনারি সার্চ অ্যালগরিদম অনেক বেশি ইফিসিয়েন্ট। ১৫০০ থেকে ৮২২ কে বের করতে বাইনারি সার্চের দরকার মাত্র ৯ টা স্টেপ। কিন্তু একই কাজ যদি লিনিয়ার সার্চ দিয়ে করতার তাহলে লাগত ৮২২ টা স্টেপ! তাই বলে যখনই সার্চের দরকার হবে বাইনারি সার্চ চালিয়ে দিব সেটাও কিন্তু কাজের কথা না। কারণ বাইনারি সার্চের ক্ষেত্রে দুইটা কনডিশন রয়েছে। তা হলঃ

1. Array must be sorted. অর্থাৎ অ্যারেটা ছোট থেকে বড় বা বড় থেকে ছোট আকারে সাজানো থাকতে হবে।
2. অ্যারের যে কোন element এ direct access করা যেতে হবে।

কোন একটা অ্যারে যদি সর্টেড থাকে তাহলেই কেবল মাত্র বাইনারি সার্চ অ্যালগরিদম ইমপ্লিমেন্ট করা যাবে। যেমন ডিকশনারি বা এই বইয়ের উদাহরণের সাথেই মিলিয়ে চিন্তা করতে পারো। আমরা জানি বইয়ের পেজগুলো সাজানো আছে। তাই আমাদের প্রয়োজন অনুসারে বইটাকে সব সময় দুই ভাগ করে প্রতিবার এক ভাগের উপর কাজ করেছি। অনেক সময়ই unsorted ডেটাকে sort করে বাইনারি সার্চ করা লাগতে পারে। কিন্তু মনে রাখতে হবে সর্টিং অপারেশনটা বেশ costly অর্থাৎ time consuming. তাই সর্ট করার দরকার পড়লে যে কোন ইফিসিয়েন্ট সর্টিং অ্যালগরিদম ব্যবহার করা উচিত।

• বাবল সর্ট অ্যালগরিদম – Bubble Sort Algorithm
• কাউন্টিং সর্ট অ্যালগরিদম – সবচেয়ে সহজ সর্টিং অ্যালগরিদম

এবার সরাসরি কোড দেখি উপরে বর্ণিত অ্যালগরিদমেরঃ

#include<stdio.h>
#define arr_size 10

int main()
{
    int arr[arr_size] = {2, 5, 8, 9, 19, 41, 45, 57, 98, 123};
    int i, startPoint, endPoint, midPoint, item, location, comparison;

    item = 57; //the value we want to search from Array

    //Start Binary Search
    startPoint = 0; //first index of array
    endPoint = arr_size-1; //last index of array
    location = -1;
    comparison = 0;

    while(startPoint <= endPoint)
    {
        comparison++;
        midPoint = (startPoint+endPoint)/2;

        if(arr[midPoint]==item)
        {
            location = midPoint;
            break;
        }
        else if(arr[midPoint]<item)
            startPoint = midPoint + 1;
        else
            endPoint = midPoint - 1;

    }

    printf("Given, a sorted array of 10 elements:\n\n");
    for(i = 0; i<arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n----------------------------\n\n");


    if(location==-1)
        printf("%d not found in the Array.\nTotal number of comparisons: %d\n", item, comparison);
    else
        printf("%d found at Location: %d\nTotal number of comparisons: %d\n", item, location+1, comparison);


    return 0;
}

প্রোগ্রামে একটা অ্যারে নেয়া হয়েছে। তাতে ১০ টা ইলিমেন্ট আছে। item নামের একটা ভেরিয়েবল নেয়া হয়েছে। আমরা, যেই ভ্যালুটা অ্যারের মধ্যে খুঁজতে চাই সেই ভ্যালুটা item এ অ্যাসাইন করে দিলাম। এখানে অ্যাসাইন করা হয়েছে 57. প্রোগ্রামটা লেখার উদ্দেশ্য হচ্ছে অ্যারে থেকে ৫৭-কে খুঁজে বের করা। যদি খুঁজে পাওয়া যায় তাহলে ১০ টা পজিশনের মধ্যে কত তম পজিশনে পাওয়া গেছে সেটা প্রিন্ট করতে হবে। আরেকটা কাজ করা হয়েছে, আইটেম খোঁজার জন্য কতটি স্টেপ দরকার হয়েছে সেটা প্রিন্ট করা।

কোডের নিচ থেকে ব্যাখ্যা শুরু করি। 40 নাম্বার লাইনে চেক করা হয়েছে location এর মান -1 কিনা। যদি -1 হয় তাহলে বুঝতে হবে সার্চ করে আইটেমটা খুঁজে পাওয়া যায় নি। সার্চ করার আগেই ১৪ নাম্বার লাইনে location = -1; করে রাখা হয়েছে। যদি আইটেম খুঁজে পাওয়া যায় তাহলে যেই ইন্ডেক্সে পাওয়া গেছে সেই ইন্ডেক্সের মান item এ assign হয়ে যাবে।

এবার লুপের ভিতরে দেখি কী হচ্ছে? ১৯ নাম্বার লাইনে comparison++ করা হয়েছে। অর্থাৎ যত বার লুপের ভিতরে ঢুকা হবে প্রতিবার এর মান এক করে বাড়বে। লুপের বাইরে প্রিন্ট করে দেখব আইটেমটা খুঁজে পেতে এই লুপের কতটা কষ্ট (!) করতে হয়েছে। এরপরের লাইনে অ্যারের মিড পজিশনের ইন্ডেক্স নাম্বারটা বের করা হয়েছে। খেয়াল করো, এটা অ্যারের মাঝখানের ইন্ডেক্সের নাম্বার। এটা কিন্তু মাঝের মান না। এই কোডের ক্ষেত্রে midPoint = 4 পাওয়া যাবে। arr[midPoint] এর মান 19. অর্থাৎ অ্যারের মধ্যবর্তী ইন্ডেক্স হচ্ছে 4, আর মধ্যবর্তী ইন্ডেক্সের ভ্যালু (value of 4th index) হচ্ছে 19. midPiont কেন বের করা হয়েছে? কারণ আমরা অ্যারেটাকে সব সময় মাঝখান থেকে দুইভাগ করে ফেলি। এই ভাগাভাগির কাজে midPoint আমাদেরকে সাহায্য করবে।

২২ নাম্বার লাইনে চেক করা হচ্ছে if(arr[midPoint]==item). অর্থাৎ অ্যারের একদম মাঝের ভ্যালুটাই item (যাকে আমরা খুঁজছি) তার সমান কিনা। যদি সমান হয়ে যায় তাহলে location = midPoint করব। কেননা midPoint-তম ইন্ডেক্সেই আমাদের কাংক্ষিত মান পাওয়া গেছে। তাই location ভ্যারিয়েবলে থাকা পূর্বে অ্যাসাইন করা -1 কে replace করা হল midPoint দিয়ে।

কিন্তু যদি if(arr[midPoint]==item) স্টেটমেন্টটা সত্য না হয়? তাহলে দুইটা ঘটনা ঘটতে পারে। arr[midPoint] এর মান হয় item থেকে ছোট, অন্যথায় item থেকে বড়। যদি তা item থেকে ছোট হয় তাহলে কী করব? অ্যারের বাম পাশের অংশকে আর হিসাবের মধ্যে রাখব না, তাই না? আমাদের এই কোডের ডেটাগুলো নিয়েই হিসাব কর। আমরা খুঁজছি ৫৭, কিন্তু অ্যারের মাঝখানের ইলিমেন্ট হচ্ছে ১৯। যা ৫৭ থেকে ছোট। তাহলে অ্যারের শুরু থেকে মাঝখান পর্যন্ত এই অংশের মধ্যে আর খুঁজবই না। কারণ এর মধ্যে ৫৭ থাকার সম্ভাবনা নাই। যদি অ্যারেতে ৫৭ থেকে থাকে তাহলে অবশ্যই তা অ্যারের ডান পাশের অংশে আছে। তাই বামের অংশকে হিসাব থেকে আউট! এই আউট করার কাজটা করা হয়েছে startPoint = midPoint + 1; এর মাধ্যমে। এর মানে কী? startPoint শুরুতে ছিল ০, midPoint হিসাব করে বের করা হল 4. চেক করে বুঝে গেছি ৫৭  মানটা ০ থেকে ৪ এর মধ্যে নাই। তাই ডান পাশের অ্যারে নিয়ে কাজ করার উদ্দেশ্যে অ্যারের startPoint-টা আপডেট করা হল (বইয়ের উদাহরণ মনে করো)। midPoint-তম ইন্ডেক্সে যেহেতু item নাই, তাই নতুন অ্যারের startPoint করা হল (midPoint+1)-তম ইন্ডেক্সকে।

যদি অ্যারের মিড ভ্যালুটা item এর সমান না হয় এবং ছোটও না হয় তাহলে হবে বড়। কারণ দুইটা সংখ্যার মধ্যে এই তিনটা রিলেশনই থাকতে পারে। যদি মাঝের ভ্যালুটা আইটেমের চেয়ে বড় হয় তাহলে আমাদের দরকার হবে অ্যারের প্রথম পার্ট নিয়ে কাজ করার। দ্বিতীয় পার্টকে কিভাবে বাদ দিব? অ্যারের endPoint টা আপডেট করলেই কিন্তু হয়ে যায়। তাই এটাকে আপডেট করা হল endPoint = midPoint – 1; দিয়ে।

উপরের startPoint, endPoint ও midPoint আপডেটের কাজটা লুপের ভিতরে চলতেই থাকবে। দুইটা কনডিশনের যে কোন একটা পেলে এই লুপটা break করবে। তা হচ্ছেঃ

1. যদি কোন একটা স্টেপে arr[midPoint] এর মান item এর সমান হয়। অর্থাৎ ২২ নম্বর লাইনের IF statement সত্য হলে location এর মান আপডেট করে লুপ ব্রেক হয়ে যাবে। কারণ আইটেমকে পেয়ে গেলে অযথা লুপ ঘুরানোর কোনই দরকার নাই।
2. startPoint ও endPoint আপডেট হতে থাকবে। যদি কখনো startPoint টা endPoint এর চেয়ে বড় হয়ে যায় তখনও লুপ ব্রেক করবে। কারণ স্বাধারণ ভাবেই বুঝা যায় কোন অ্যারের শুরুর ইন্ডেক্স সেই অ্যারের শেষের ইন্ডেক্সের চেয়ে বড় হতে পারে না। কিন্তু সমান হতে পারে! কখন? যখন অ্যারেতে একটা মাত্র ইন্ডেক্স থাকে। যখন যেটা শুরুর ইন্ডেক্স সেটাই শেষের ইন্ডেক্স। তাই, while এর condition পার্টে রাখা হয়েছে while(startPoint <= endPoint)। মানে, যতক্ষণ শুরুর ইন্ডেক্সটা শেষের ইন্ডেক্সের চেয়ে ছোট অথবা সমান থাকবে ততক্ষণ লুপের ভিতরে compare করার কাজটা চালিয়ে যাও। যদি অ্যারেতে আইটেমটা না থাকে তাহলেই কেবল মাত্র এই শর্তের মধ্যে পড়ে লুপ ব্রেক হবে।

এবার নিজে নিজে কোড করো। লুপের ভিতরে startPoint, endPoint, midPoint এর ভ্যালুগুলো প্রিন্ট করে দেখতে পারো কিভাবে চেঞ্জ হচ্ছে। কোড নিয়ে খেলা করো, যতক্ষণ আনন্দ পাও… 🙂