অ্যালগরিদমঃ লিনিয়ার সার্চ

সবচেয়ে সহজ সার্চিং অ্যালগরিদম হচ্ছে লিনিয়ার সার্চ (Linear Search)। যেমন আমাদের কাছে একটা নাম্বার লিস্ট রয়েছে। সেখানে একটা নির্দিষ্ট নাম্বার আছে কিনা আমরা তা বের করতে চাই। তার জন্য ঐ লিস্টের প্রথম সংখ্যার সাথে আমারা যে সংখ্যাটা খুঁজছি, তা মিলিয়ে দেখি। যদি মিলে যায়, তাহলে আমরা আমাদের সার্চিং প্রসেসটা শেষ করি। না হয় পরের নাম্বারের সাথে মিলিয়ে দেখি।

যেমন আমাদের কাছে এ লিস্টটি রয়েছেঃ 4, 8, 2, 7, 1। আমরা খুঁজে দেখব 7 আছে কিনা এই লিস্টে। তার জন্য প্রথমে লিস্টের প্রথম সংখ্যার সাথে মিলিয়ে দেখব। এটা কি 7? না, এটা যেহেতু 7 না, লিস্টের পরের সংখ্যার সাথে মিলিয়ে দেখব। এক সময় আমরা পেয়ে যাবো। যদি সংখ্যাটি পাওয়া না যেতো, অ্যালগরিদমটি বলত, সংখ্যাটি পাওয়া যায় নি।


   for each item in the list

      if match item == value

         return the item's location
 

অনেক সহজ!

লিনিয়ার সার্চে যেহেতু যত গুলো নাম্বার রয়েছে, ততবার ততবার তুলনা করা হয়, তাই লিনিয়ার সার্চের কমপ্লেক্সিটি হচ্ছে O(n)

সি প্রোগ্রামিং এ আমরা নিচের মত করে ইমপ্লিমেন্ট করতে পারিঃ

#include<stdio.h>

void bubble_sort(int[], int);

void main()
{
   int list[] = {4,8,2,7,1};
   int i, n = 5;

   for(i = 0; i<n; i++){

    if(list[i] == 7){
        printf("We found 7 in the list at: %d th position\n", i+1 );
        return;
    }

   }

}

Leave a Reply

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