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

20 October, 201610 April, 2020 Hasan Abdullahসার্চিং অ্যালগরিদম

• বাবল সর্ট অ্যালগরিদম – 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 এর ভ্যালুগুলো প্রিন্ট করে দেখতে পারো কিভাবে চেঞ্জ হচ্ছে। কোড নিয়ে খেলা করো, যতক্ষণ আনন্দ পাও… 🙂