Linear Search

Linear Search

• Linear search does not expect specific ordering of the data. Infact the data is arranged in the list. At every iteration the record will be compared with the help of the key. In this case sometimes all the elements get compared with the key value. Although this is an simple searching technique some unnecessary comparisons has to be performed. This method does not give the satisfactory solution for the system for large number of elements.

• The time complexity of this algorithm is O(n). The time complexity will increase linearly with the value of n. For higher value of n the linear search is not the satisfactory solution.

• From the above Fig. 9.8.1 the array is maintained to store the students record. The record is not sorted at all. If we want to search the student's record whose roll number is 12 then with the key‒roll number we will see the every record whether it is of roll number = 12. We can obtain such a record at Array [4] location.

• Let us now implement the sequential search using C++ program

C++ program

/*********************************************************************

Program for implementing the sequential search

**********************************************************************/

#include<iostream>

using namespace std;

class Search

{

private:

   int a[10],n,key;

public:

    void get_data();

    void Seq _Search(int);

};

void Search::Seq_Search(int key)

{

    int flag=0,mark;

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

    { //searching element from beginning of array

        if(a[i]= =key)

        {

            flag=1;//setting the flag if element found

            mark=i;//marking the location of key element

            break;

        }

    }

if(flag= =1)//flag=1 means element is found

    cout<<"\n The element is present at location: "<<mark+1;

else

    cout<<"\n The element is not present in the array";

}

void Search::get_data()

{

    cout<<"\n How Many Elements are there in an array?";

    cin>>n;

    cout<<"\n Enter the elements ";

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

        cin>>a[i];

}

void main()

{

    int k;

    Search obj;

    clrscr();

    obj.get_data();

    cout<<"\n\t Enter the element which is to be searched";

    cin>>k;

    obj.Seq_Search(k);

    getch( );

}

Output

How Many Elements are there in an array? 7

Enter the elements 10 20 30 40 50 60 70

Enter the element which is to be searched 50

The element is present at location: 5

Time complexity

This is a method in which we scan each element of the list one by one until target element is found.

Best case : When the element is present at first position. Hence time complexity is O(1).

Worst case : When the element is at the last position or not present at all. Hence time complexity is O(n).

Average case : On average, half of the elements are checked. The time complexity is O (n/2) which simplifies to O(n).

Space complexity : O(1), as no extra space used.