Implementation and Time analysis of linear search algorithm

 linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.


Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.

//time analysis of linear searching....
 
#include<iostream>
#include<sys/time.h>
using namespace std;
struct timeval t1,t2;

class linear
{
    int a[100],count,i;
    public:
        void getdata(int n)
        {
            for(int i=1;i<=n;i++)           
            {
                cin>>a[i];
            }
        }
        void putdata(int n)
        {
            for(int i=1;i<=n;i++)
            {
                cout<<" "<<a[i];
            }
            cout<<"\n";
        }
        void searchdata(int n,int x)
        {
            for(i=1;i<=n;i++)
            {
                if(x==a[i])
                {   
                    count++;
                    cout<<"\n"<<a[i]<<" element is found at position :"<<i<<endl;       
                }
       
            }   
            if(count==0)
            {
                cout<<"element is not found\n";
            }
            putdata(n);
        }
    };
int main()
{
    double t;
    int n,x;
    linear lnr;
    cout<<"-----:Implementaton of Linear Search Algorithm:-----";
    cout<<"enter the no of elements you want ::-";
    cin>>n;
    cout<<"------enter list-----\n";
    lnr.getdata(n);
    cout<<"\n-----list-----";
    lnr.putdata(n);
    cout<<"\nEnter element you want to search ::-\t";
    cin>>x;
    gettimeofday(&t1,'\0');
    lnr.searchdata(n,x);
    gettimeofday(&t2,'\0');
    t=(double)(t2.tv_usec-t1.tv_usec)/1000000+(double)(t2.tv_usec-t1.tv_usec);
    cout<<"time diff:"<<t<<"usec.\n";
    return 0;
}