Linear search algorithm in c++

Welcome to programmopedia! In this article, we will learn about linear search in c++. We are going to write c++ programs to search arrays using a linear search algorithm. Linear search is not the only searching algorithm available but it’s the easiest and basic one. It’s not as efficient as other searching algorithms like binary search are. It’s because this sort of searching has high program execution time as we have to do comparison with every array element. Remember that linear search is not limited to arrays rather it can be applied on other data structures like linked lists. Now let’s first understand how a linear search algorithm works.

What is linear search algorithm in c++?

Linear search is a searching algorithm in which the number is compared sequentially with the array elements one by one until its found. That’s why it is also referred to as a sequential search. 
Let suppose we want to find n in an array. We will follow the following steps.

• First of all, take the left-most element of the array and compare it with n.
• If not found, compare n with the next leftmost element of the array.
• Keep on comparing n with the next leftmost elements until the n is found.
•  Print the index of the array where n is found and stop searching further.

See the below figure to understand the linear search algorithm in detail.

How to apply linear search in c++?

• Declare an array Arr[50], an int type variable size and a variable n. Here size will be the array size and n is the number to search.
• The maximum array size that a user can enter is 50 and I think it’s enough for this demonstration.
• Read input in variable size and print a message that array is created.

int Arr[100];
    int size;
    int n;
       
    cout << "PLEASE ENTER ARRAY SIZE:-"<<endl;
    cin >> size;
     
    cout << ":ARRAY CREATED WITH SIZE OF " << size << " ELEMENTS:"<<endl;
 


• Run a loop less than size times and read input from the user at all the array indexes.
• Ask the user to enter a number to search in the array.

//READ INPUT IN ARRAY
 for(int i = 0; i < size; i++){
        cout << "ENTER ELEMENT AT INDEX " << i << ":-";
        cin>>Arr[i];
    }
      
    cout << "ENTER A NUMBER TO SEARCH IN ARRAY"<<endl;
    cin >> n;
 


• Now Run another loop less than size times to search the number in the array.
• Take a boolean variable NotFound. It will act as a flag that is set to true by default.
• Now compare n with Arr[i] until they match. 
• Print a message and the index of the array when a match is made.
• Set the NotFound flag to false and break the loop when n is found.

 // SEARCH ARRAY USING LINEAR SEARCH ALGO
 bool NotFound = true;
    for(int i = 0; i < size; i++){
        if(Arr[i] == n){
            cout << "ELEMENT FOUND AT INDEX:- " << i;
            NotFound = false;
            break;
        }
    }
     

• Write an if condition outside the loop and print that number is not found if the NotFound flag is true.

 //PRINT NOT FOUND MESSAGE
    if(NotFound){
        cout  << "ElEMENT NOT FOUND IN ARRAY"<<endl;
    }

Simple Linear search program in c++?

Now it’s time to see the code of all above-explained steps at once as a complete linear search program in c++.

#include <iostream>
using namespace std;
   
int main(){
    int Arr[100];
	int size;
	int n;
       
    cout << "PLEASE ENTER ARRAY SIZE:-"<<endl;
    cin >> size;
     
    cout << ":ARRAY CREATED WITH SIZE OF " << size << " ELEMENTS:"<<endl;
      
    //READ INPUT IN ARRAY
    for(int i = 0; i < size; i++){
        cout << "ENTER ELEMENT AT INDEX " << i << ":-";
        cin>>Arr[i];
    }
      
    cout << "ENTER A NUMBER TO SEARCH IN ARRAY"<<endl;
    cin >> n;
      
    // SEARCH ARRAY USING LINEAR SEARCH ALGO
    bool NotFound = true;
    for(int i = 0; i < size; i++){
        if(Arr[i] == n){
            cout << "ELEMENT FOUND AT INDEX:- " << i;
            NotFound = false;
            break;
        }
    }
      //PRINT NOT FOUND MESSAGE 
    if(NotFound){
        cout  << "ElEMENT NOT FOUND IN ARRAY"<<endl;
    }
 
    return 0;
}

Output of program:

 Linear search program in CPP with duplicate values in array?

The previous program can not tell that the number is found more than one time if it’s duplicated in the array. But in this program, we will also manage the duplication of numbers in the array by doing slight changes in code. Let’s see what changes we need.

• Take a variable counter and initialize it to zero.
• Check for a match inside a for loop with less than size iterations.
• When n is found, this time don’t break the loop. Instead, increment the counter by one and keep on searching for the next match.

 bool NotFound = true;
    int counter = 0;
for(int i = 0; i < size; i++){
        if(Arr[i] == n){
            cout << "ELEMENT FOUND AT INDEX:- " << i<<endl; 
	    NotFound = false;
	    counter++;    
        }
       
    }
 

• After the completion of the loop, print that n is found counter  times in array if the bool flag NotFound is false.

//PRINT NOT FOUND MESSAGE 
 if(NotFound){
        cout  << "ElEMENT NOT FOUND IN ARRAY"<<endl;
    }else{
    	cout  << "ElEMENT FOUND "<<counter<<" TIMES IN ARRAY"<<endl;
    }

That’s how we can write a linear search program in c++ for arrays having duplicate values. Now see the updated program code.

#include <iostream>
using namespace std;
   
int main(){
    int Arr[50];
	int size;
	int n;
       
    cout << "PLEASE ENTER ARRAY SIZE:-"<<endl;
    cin >> size;
     
    cout << ":ARRAY CREATED WITH SIZE OF " << size << " ELEMENTS:"<<endl;
      
    //READ INPUT IN ARRAY
    for(int i = 0; i < size; i++){
        cout << "ENTER ELEMENT AT INDEX " << i << ":-";
        cin>>Arr[i];
    }
      
    cout << "ENTER A NUMBER TO SEARCH IN ARRAY"<<endl;
    cin >> n;
      
    // SEARCH ARRAY USING LINEAR SEARCH ALGO

	bool NotFound = true;
	int counter = 0;
    for(int i = 0; i < size; i++){
        if(Arr[i] == n){
            cout << "ELEMENT FOUND AT INDEX:- " << i<<endl; 
			NotFound = false;
			counter++;    
        }
       
    }
      //PRINT NOT FOUND MESSAGE 
    if(NotFound){
        cout  << "ElEMENT NOT FOUND IN ARRAY"<<endl;
    }else{
    	cout  << "ElEMENT FOUND "<<counter<<" TIMES IN ARRAY"<<endl;
	}
 
    return 0;
}


Output of program:

I have tried my best to explain Linear search in c++ with two example programs. I am now sure that you are clear about the linear search algorithm in c++. We will also discuss other searching algorithms in c++ in our coming articles. I hope you found this information useful and liked my effort. Thanks for reading and supporting us.