পোস্টটি পড়া হয়েছে 10,155 বার
লিনিয়ার সার্চ, Linear search algorithm

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

Hasan Abdullahসার্চিং অ্যালগরিদম

Post updated on 28th November, 2016 at 01:36 pm

অ্যারে হচ্ছে সবচেয়ে সহজতম ডেটা স্ট্রাকচার। সিম্পল কিছু ডেটা সিরিয়াল্যি স্টোর করার জন্য এই ডেটা স্ট্রাকচার ব্যবহৃত হয়। যে কোন ডেটা স্ট্রাকচারেই অসংখ্য ডেটার মধ্য থেকে কাংক্ষিত ডেটা খুঁজে বের করার প্রয়োজন হয়। এই ডেটা কত দ্রুত খুঁজে বের করা যায় সেটা একটা বড় চ্যালেঞ্জ। আজ দেখব অ্যারের কোন ডেটাকে সার্চ করার সবচেয়ে সহজ একটা অ্যালগরিদম।

ধরো তুমি ঢাকার শহরের কোন একটা বাসার ঠিকানা খুঁজে বের করার মত একটা জটিল কাজের দায়িত্ব নিয়েছ। স্বাভাবিক ভাবেই তুমি দেখবে গলির প্রথম ৩টা বাড়ির নাম্বার যদি হয় ৪৫, ৪৬, ৪৭। পরের বাড়িগুলোর নাম্বার নির্ঘাত হবে ৭২, ৭৩, ৭৪… পরের গলিতে গিয়ে দেখতে পাবে সব নাম্বার ১০০ এর বেশি দিয়ে। তার মানে যে কোন কারণেই হোক বাড়ির নাম্বারগুলো সাজানো অবস্থায় নাই। ছোট থেকে বড় বা বড় থেকে ছোট ক্রমানুসারে সাজানো না থাকায় তোমার বাড়ি খুঁজে পেতে ঝামেলা হচ্ছে। ধরা যাক একটা গলির নাম A. তুমি ৫৩ নাম্বার বাড়িটা খুঁজে বের করতে চাও। তাহলে কী করবে? A গলির শুরু থেকে প্রতিটা বাড়ির নাম্বার প্লেট চেক করবে, যতক্ষণ পর্যন্ত কাংক্ষিত বাড়িটা খুঁজে না পাও। যদি ৫৩ পেয়ে যাও তাহলে আর খোঁজাখুঁজি করবে না। কিন্তু এই গলিতে যদি ৫৩ নাম্বারের বাড়ি না থেকে থাকে তাহলে? সে ক্ষেত্রে কিন্তু গলির সবগুলো বাড়ি চেক করা শেষে তুমি সিদ্ধান্ত নিতে পারবে যে “এই নাম্বারটি এই গলিতে অনুপস্থিত”।

তুমি যদি উপরের বাড়ি খোঁজার ব্যাপারটা বুঝে গিয়ে থাকো তাহলে তুমি লিনিয়ার সার্চ অ্যালগরিদম বুঝে গেছ। নিজে নিজেই অ্যারে দিয়ে এটা ইমপ্লিমেন্ট করতে পারবে।

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

লিনিয়ার সার্চের কোডটা নিচের মত হতে পারেঃ

scanf("%d", &item); //that value we want to search

for(i=0; i<arr_size; i++)
{
    if(arr[i]==item)
    {
        printf("Item found in index number: %d", i);
        break;
    }
}

if(i==arr_size)
    printf("Item not found");

লুপ ঘুরিয়ে অ্যারের মধ্যে item-কে খোঁজা হচ্ছে। যদি পাওয়া যায় (arr[i]==item) তাহলে কত নাম্বার ইন্ডেক্সে পাওয়া গেছে তা প্রিন্ট করা হয়েছে। এরপরের লাইনে লুপটা ব্রেক করে দেয়া হয়েছে। কারণ আমরা আমাদের কাংক্ষিত item পেয়ে গেছি। আর লুপ ঘুরানোর দরকার নাই (বাড়ি খুঁজে পাওয়ার মত)।

কিন্তু যদি item পাওয়া না যায় সে ক্ষেত্রে কিন্তু লুপটা অ্যারের শেষ ইন্ডেক্স পর্যন্ত চেক করবে। অ্যারের শেষ ইন্ডেক্স হচ্ছে (arr_size-1) অর্থাৎ অ্যারের সাইজের চেয়ে ১ কম (কারণ ইনডেক্স নাম্বার শূণ্য থেকে শুরু হয়)। অ্যারের শেষ ইন্ডেক্সেও যদি item পাওয়া না যায় তাহলে লুপের ভিতরের IF statement সত্য হবে না। সত্য না হলে ভিতরের break স্টেটমেন্টও কাজ করবে না। তাই loop variable (i) এর মান আরো ১ বাড়বে। বেড়ে এটি হবে arr_size এর সমান। এটাই চেক করা হচ্ছে লুপের বাইরে। যদি কখনো i এর মান অ্যারের সাইজের সমান হয় তাহলে বুঝতে হবে লুপের ভিতরে অ্যারের শেষ ইন্ডেক্সের মানও চেক করা হয়েছে কিন্তু মানটি সেখানেও পাওয়া যায় নি। তাই “Item not found” প্রিন্ট করে দেয়া হয়েছে।

Worst case এর ক্ষেত্রে অর্থাৎ যদি item-টি অ্যারেতে পাওয়া না যায় সেক্ষেত্রে Linear Search Algorithm এর time complexity হচ্ছে O(n). Best case এর ক্ষেত্রে O(1) আর Average Case এর ক্ষেত্রে O(n).

এই অ্যালগরিদমটির কোড করতে ঝামেলা কম, সহজ। কিন্তু এর running time বেশি। এ জন্য বেশি ডেটার ক্ষেত্রে বাইনারি সার্চ এলগরিদম ব্যবহার  করা হয়। যা ইমপ্লিমেন্ট করতে একটু কষ্ট কিন্তু পারফর্মেন্স বাড়িয়ে দেয় অনেক গুণ বেশি!