অ্যারে সার্চ (linear search)

একটি অ্যারে তে যেসব উপাদান থাকে আমরা চাইলে সেগুলা বারবার ব্যবহার করতে পারি।

আগের পর্বে আমরা অ্যারের উপাদানগুলো যোগ করার প্রোগ্রাম করেছিলাম।
মনেকরো আমরা ১ থেকে ১০ পর্যন্ত সবগুলা সংখ্যা যোগ করতে চাই, সেক্ষেত্রে আমরা একটি লুপ দিয়ে কাজটি করতে পারি। লুপ নিয়ে কিছু সহজ সমস্যা (Loop exercise)  এর প্রথম সমস্যাটা দেখতে পারো। এবার হয়তো মনে হতে পারে যে কাজটি লুপ দিয়েই এতো সহজে করা যায় সেখানে অ্যারে কেন ব্যবহার করবো?! কিন্তু মনেকরো ১-১০ পর্যন্ত যোগ করার সময় পাঁচ নম্বরে যে সংখ্যাটা যোগ করেছি তা আমরা জানতে চাই।
  1+2+3+4+5+6+7+8+9+10  তাহলে পাঁচ নম্বরে 5 আছে। এটা অ্যারে ব্যবহার করলে যেকোন সময় আউটপুট এ দেখাতে পারবে। যদি তোমার অ্যারের নাম  a হয় এবং  0 besed index হয় তাহলে a[4] প্রিন্ট করলে তা পেয়ে যাবে। আর যদি 1 besed index হয় তাহলে a[5] প্রিন্ট করলে তা পেয়ে যাবে।
তোমার মনে হতে পারে একথা তো আর প্রোগ্রাম করে বলতে হবে না। মুখেই বলে দেওয়া যায় যে, পাঁচ নম্বর ইনডেক্স এ কোন সংখ্যা ছিলো।

তাহলে আমরা আরেকটু গভীরে যাই। আমরা আসলে এমন একটি প্রোগ্রাম লিখেছি যেখানে যেকোন নম্বর দিয়ে যোগ করা যায়। 1 2 3 4  5.. এভাবে ইনপুট দিতে হবে এমন কোন কথা নেই। ইউজার চাইলে  10 300 2 5 55 .... এভাবেও ইনপুট দিতে পারে। অ্যারের যোগ [Find the sum of all elements] পোস্টটা আবার দেখতে পারো।  এখন যদি আমরা জানতে চাই পাঁচ নম্বরে কোন সংখ্যা ইনপুট দেওয়া হয়েছিল ? অ্যারে দিয়ে করলে তা খুব সহজেই বলে দিতে পারবো।

এখন হয়তো তোমার ইচ্ছা হলো অ্যারের প্রথম উপাদান আর শেষ উপাদান যোগ করে তার মান sum নামক ভেরিয়েবলে রাখবে! তো ধরে নিলাম তুমি ৫ টি উপাদানের অ্যারে নিয়েছো। যেটি শুরু হয়েছে a[0] থেকে এবং শেষ হয়েছে a[4] এ । তাহলে sum = a[0]+a[4]; এই লাইনটা লিখলেই হবে।

আশা করি অ্যারে নিয়ে তোমাদের ধারণা অনেক পরিষ্কার হয়েছে ।


এবার আমাদের আজকের মূল বিষয়ে ফিরে যাই,
আমরা  অ্যারে তে অনেকগুলা সংখ্যা জমা রাখার পর মনেকরো  হঠাৎ একটা সংখ্যা খোঁজার প্রয়োজন হলো। হতে পারে কোন শ্রেণিতে ছাত্র - ছাত্রীর রোল নম্বর,  মনেকরো,আমরা একটি শ্রেণি থেকে কয়েকজন ছাত্র -ছাত্রী নিয়ে একটা প্রোগ্রামিং ক্লাব তৈরি করেছি। ক্লাবের সব সদস্যের রোল নম্বর একটি অ্যারেতে রেখেছি। এখন আমরা জানতে চাই আমাদের ক্লাবে (অ্যারেতে) 33 রোলের কোন শিক্ষার্থী আছে কি না? সেটা আমরা খুব সহজে লিনিয়ার সার্চ ব্যবহার করে  জানতে পারি।

আরো গভীরে যাও (+_+):


লিনিয়ার শব্দের অর্থ  রৈখিক। কাজেই বোঝতে পারছো এই সার্চটি একটি রেখার মতো কাজ করে।

নিচের চিত্রটি দেখোঃ

source: https://www.tutorialspoint.com/data_structures_algorithms/images/linear_search.gif

এখানে ১০ টি উপাদানের একটি অ্যারে আছে। এর মধ্যে আমরা 33 সংখ্যাটাকে খোঁজবো । তার জন্য আমাদের যা করতে হবে তা হলো এক এক করে সবগুলা সংখ্যা চেক করবো যে সংখ্যাটি 33 এর সমান কি না? যখনই আমরা 33 পেয়ে যাবো আমাদের সার্চ ব্রেক করে দেবো।

এবার চলো প্রগ্রামটি দেখে নেইঃ

#include<stdio.h>
int main()
{
    int a[100],i,n,item;
    printf("Enter the size of array:\n");
    scanf("%d",&n);
    printf("Enter %d elements: \n",n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    printf("Entered elements: are\n");
    for(i=0; i<n; i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\nEnter the item you want to search: \n");
    scanf("%d",&item);
    for(i=0; i<n; i++)
    {
        if(a[i]==item)
        {
            printf("Item found at %d th position\n",i+1);
            break;
        }
    }
    return 0;
}

printf("\nEnter the item you want to search: \n");      এই লাইনের আগ পর্যন্ত কোড গুলা আশাকরছি বোঝতে পারছো। কোন সমস্যা হলে আগের টিউটোরিয়াল গুলা দেখতে পারো।

• আমরা printf("\nEnter the item you want to search: \n");    এই লাইনে ইউজারকে বলছি যে সে সংখ্যাটা সার্চ করতে হবে তা ইনপুট দিতে। তারপরের লাইনে আমরা সংখ্যাটা ইনপুট নিয়েছি। এবং তা item নামক ভেরিয়েবল এ রেখেছি।

• এবার আমরা একটা লুপ চালিয়েছি অ্যারের শুরু থেকে শেষ পর্যন্ত। লুপের ভিতরে আমরা একটা শর্ত দিয়েছি। যেখানে প্রতিটা উপাদানকে চেক করছি তা আমাদের item এর সমান কি না।  যদি কখনো শর্ত মিলে যায় অর্থাৎ আমরা যে সংখ্যাটা খোঁজছি তা পাওয়া যায় তাহলে প্রিন্ট করবে কততম পজিশনে সংখ্যাটা পাওয়া গেছে। এবং এই পজিশনটা হলো i যতবার ঘুরেছে এর সমান। যেহেতু আমরা ইনডেক্সিং 0 থেকে করেছি তাই আমাদের আউটপুট এ i+1 করে দিয়েছি। কারণ আমরা সাধারণত পজিশন 0 থেকে হিসাব না করে 1 থেকে করি। প্রিন্ট করার পর আমরা লুপ ব্রেক করে দিয়েছি। কারণ আমাদের খোজা শেষ। 

কিন্তু মনেকরো আমরা যে সংখ্যা খোঁজছি তা অ্যারেতে নেই। এক্ষেত্রে আমাদের উপরের প্রোগ্রাম কোন আউটপুট দিবে না।
তবে আমরা যদি প্রোগ্রামটা একটু পরিবর্তন করে flag ভেরিয়েবল ব্যবহার করি তাহলে সহজেই এই সমস্যা সমাধান করা যাবে, প্রোগ্রামটা দেখে নেইঃ

 
#include<stdio.h>
int main()
{
    int a[100],i,n,item,flag=0;
    printf("Enter the size of array:\n");
    scanf("%d",&n);
    printf("Enter %d elements: \n",n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("Entered elements: are\n");
    for(i=0;i<n;i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\nEnter the item you want to search: \n");
    scanf("%d",&item);
    for(i=0;i<n;i++)
    {

       if(a[i]==item)
        {
            printf("Item found at %d th position\n",i+1);
            flag++;
            break;
        }
    }
    if(flag==0)
    {
        printf("Item not found in this array! \n");
    }
    return 0;
}

আমরা flag=0 ধরে নিয়েছিলাম। আর যদি আমাদের কাংখিত সংখ্যাটা পাওয়া যায় তখন আমরা break করার পুর্বে flag++ করে এর মান পরিবর্তন করে দিয়েছি। তুমি চাইলে flag--, flag=1, ইত্যাদি যা খুশি করতে পারো। তবে যাই করো লক্ষ্য রেখো flag এর মান যেন পরিবর্তন হয়।
তারপর আমরা flag এর বাইরে শর্ত দিয়েছি  flag এর মান শুণ্য এর সমান হলে প্রিন্ট করবে যে সংখ্যাটা এই অ্যারেতে খোঁজে পাওয়া যায় নি।
আর যদি flag এর মান শুণ্য না হয়? আমাদের এই শর্ত কিছু প্রিন্ট করবে না। কারণ শর্তটি তখন মিথ্যা হয়ে যাবে।  কিন্তু উপরের লুপের ভিতরের শর্ত সত্য হবে তাই প্রিন্ট করবে  সংখ্যাটি কত তম পজিশনে পাওয়া গেছে।   
কারণটা নিজেই বোঝার চেস্টা করো। আমি আর ব্যাখ্যা করছি না। 

HaPpY cOdInG :)