C++ Program to implement Linear Search [DEVCPP/GCC]

LINEAR SEARCH

Linear search consists of an array and a key value (value to be searched). The key value is compared with each value of the array sequentially. If the value is found the corresponding index value is returned.

COMPLEXITY

BEST CASE:  Element found in the first position.
COMPLEXITY: O(1)

WORST CASE: Element not found.
COMPLEXITY: O(n)

AVERAGE CASE: Element found in any location except first.
COMPLEXITY: O(n)

STEPS

1. Initialize a boolean variable(flag) as false.

2. Input the elements of array using a loop.

3. Input key element from the user.

4. Compare the key value with the ith element of the array. (i=0 initially)

5. If the value is matched then set flag as true and break from the loop. If not, then increment i.

6. Repeat steps 4-5 until i <= length of the array.

7. If flag is true, then element is found at i+1th location else the element is not found.

PROGRAM

//Program to implement Linear Search

# include <iostream>

using namespace std;

int main()
 {
          int a[10],i,j,key;
          bool flag=false;

          cout<<"ENTER THE NUMBERS: \n";

          for(i=0;i<10;i++)
         {
                cin>>a[i];
         }
 
         cout<<"\nENTER THE ELEMENT TO BE SEARCHED: ";
         cin>>key;

         for(i=0;i<10;i++)
         {
                    if(a[i]==key)
                    {
                             flag=true;
                             break;
                    }
 
         }

         if(flag)
                cout<<"ELEMENT FOUND AT POSITION: "<<i+1<<endl;
         else
                cout<<"ELEMENT NOT FOUND"<<endl;
       
         return 0;
 }

OUTPUT

Author : Shikha Rajput

Share this

Related Posts