আদর্শ পোস্ট ফরম্যাট

Posted by

Posted on

ফেব্রুয়ারি 2, 2014

Posted under

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

মন্তব্য

১ টি মন্তব্য

লিনিয়ার সার্চ

কতগুলো এলিমেন্টের একটা অ্যারের মধ্য থেকে একটা নির্দিষ্ট এলিমেন্ট খোঁজার সহজ পদ্ধতি হল লিনিয়ার সার্চ অথবা অনুক্রমিক সার্চ। এটা একটা ব্রুট ফোর্স অ্যালগরিদম। এই অ্যালগরিদমটা যতক্ষন পর্যন্ত ঐই নির্দিষ্ট এলিমেন্টটা খোজেঁ পাবে না ঠিক ততক্ষন পর্যন্ত অ্যারের প্রতিটা এলিমেন্ট চেক করতে থাকবে। আজকে আমরা শিখব কিভাবে লিনিয়ার সার্চ অ্যালগরিদম কাজ করে এবং সে সাথে লিনিয়ার সার্চ অ্যালগরিদমের সি, সি++, ও জাভা কোড দেখব।
লিনিয়ার সার্চ অ্যালগরিদমের সুবিধাঃ
১। অ্যারের এলিমেন্টগুলো সর্ট করা লাগে না।
২। সহজে কোড লেখা যায়।
৩। অ্যারের এলিমেন্ট ১০০ কিংবা তার কম হলে সার্চিং এর অন্য কোন অ্যালগরিদম ব্যবহার করার চিন্তা করতে হয় না।
লিনিয়ার সার্চ অ্যালগরিদমের অসুবিধাঃ
১। যেহেতু লিনিয়ার সার্চ অ্যালগরিদম প্রতিটা এলিমেন্ট চেক করে তাই সার্চে অনেক সময় লাগে।
২। বড় অ্যারের ক্ষেত্রে এই অ্যালগরিদম ব্যবহার করে ভাল ফল পাওয়া যায় না।
অ্যালগরিদম কমপ্লেক্সিটিঃ
Worst Case: O(n+1)
Average Case: O((n+1)/2)

কিভাবে কাজ করে?
ধরুন, n সংখ্যক এলিমেন্টের A নামে আমাদের একটা অ্যারে আছে, যার এলিমেন্টগুলো যথাক্রমেঃ 3, 4, 10, 67, 22, 56, 34, 90, 77, 48, 81, 102 এবং আমাদেরকে বলা হল ঐই অ্যারেতে 90 এলিমেন্টটা কত পজিশনে আছে সেটা সার্চ করতে।
লিনিয়ার সার্চ কিভাবে কাজ করে?
১ম ধাপঃ অ্যারের 0 পজিশনে আছে 3 কিন্তু আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[0] তে আমাদের সার্চ এলিমেন্ট নাই। তাই আমাদেরকে পরের ধাপে যেতে হবে।
২য় ধাপঃ অ্যারের 1 নাম্বার পজিশনে আছে 4 কিন্তু আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[1] এ আমাদের সার্চ এলিমেন্ট নাই। তাই আমাদেরকে পরের ধাপে যেতে হবে।
৩য় ধাপঃ অ্যারের 2 নাম্বার পজিশনে আছে 10 কিন্তু আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[2] এ আমাদের সার্চ এলিমেন্ট নাই। তাই আমাদেরকে পরের ধাপে যেতে হবে।
৪র্থ ধাপঃ অ্যারের 3 নাম্বার পজিশনে আছে 67 কিন্তু আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[3] এ আমাদের সার্চ এলিমেন্ট নাই। তাই আমাদেরকে পরের ধাপে যেতে হবে।
৫ম ধাপঃ অ্যারের 4 নাম্বার পজিশনে আছে 22 কিন্তু আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[4] এ আমাদের সার্চ এলিমেন্ট নাই। তাই আমাদেরকে পরের ধাপে যেতে হবে।
৬ষ্ঠ ধাপঃ অ্যারের 5 নাম্বার পজিশনে আছে 56 কিন্তু আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[5] এ আমাদের সার্চ এলিমেন্ট নাই। তাই আমাদেরকে পরের ধাপে যেতে হবে।
৭ম ধাপঃ অ্যারের 6 নাম্বার পজিশনে আছে 34 কিন্তু আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[6] এ আমাদের সার্চ এলিমেন্ট নাই। তাই আমাদেরকে পরের ধাপে যেতে হবে।
৮ম ধাপঃ অ্যারের 7 নাম্বার পজিশনে আছে 90 এবং আমাদের সার্চিং এলিমেন্ট 90, তাহলে A[7] এ আমাদের সার্চ এলিমেন্ট আছে। তাই ঐই অ্যারেতে আমাদের সার্চিং এলিমেন্টের পজিশন হল ৭।
কোড সিঃ

#include <stdio.h>

int main()
{
    int i, n, x, loc = -1;
    printf("How many elements?: ");
    scanf("%d", &n);
    int arr[n+3];
    printf("Enter the elements of the array:\n");
    for(i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    printf("Enter the element to search: ");
    scanf("%d", &x);
    for(i = 0; i < n; i++)
    {
        if(x == arr[i])
        {
            loc = i;
            break;
        }
    }
    if(loc == -1)
    {
        printf("Searching element is not available.\n");
    }
    else
    {
        printf("Searching element found at the location: %d\n", loc);
    }
    return 0;
}

কোড সি প্লাস প্লাসঃ

#include <iostream>
using namespace std;

int main()
{
    int i, n, x, loc = -1;
    cout<<"How many elements?: ";
    cin>>n;
    int arr[n+3];
    cout<<"Enter the elements of the array:"<<endl;
    for(i = 0; i < n; i++)
    {
        cin>>arr[i];
    }
    cout<<"Enter the element to search: ";
    cin>>x;
    for(i = 0; i < n; i++)
    {
        if(x == arr[i])
        {
            loc = i;
            break;
        }
    }
    if(loc == -1)
    {
        cout<<"Searching element is not available."<<endl;
    }
    else
    {
        cout<<"Searching element found at the location: "<<loc<<endl;
    }
    return 0;
}

কোড জাভাঃ

import java.util.Scanner;
public class testingpost
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int i, x, loc = -1, n;
		System.out.print("How many elements?: ");
		n = sc.nextInt();
		int [] arr = new int[n+3];
		System.out.println("Enter the elements:");
		for(i = 0; i < n; i++)
		{
			arr[i] = sc.nextInt();
		}
		System.out.print("Enter the element to search: ");
		x = sc.nextInt();
		for(i = 0; i < n; i++)
		{
			if(x == arr[i])
			{
				loc = i;
				break;
			}
		}
		if(loc == -1)
		{
			System.out.println("Searching element is not available");
		}
		else
		{
			System.out.println("Searching element fond at location: " + loc);
		}
	}
}

এই সম্পর্কিত অন্য পোষ্টঃ
— রিকার্সিভ বাইনারী সার্চ
এই পোষ্ট সম্পর্কিত প্রোগ্রামিং প্রবলেমঃ
1. 10474 – Where is the Marble?

আশাকরি আপনারা লিনিয়ার সার্চ অ্যালগরিদম কিভাবে কাজ করে তা বুঝতে পেরেছেন।

1 thoughts on “লিনিয়ার সার্চ”

আপনার মন্তব্য...