# 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`, 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;
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){
}
```

## 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;
int size;
int n;

cout << "PLEASE ENTER ARRAY SIZE:-"<<endl;
cin >> size;

cout << ":ARRAY CREATED WITH SIZE OF " << size << " ELEMENTS:"<<endl;

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;
}
}
if(NotFound){
}

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){
}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;
int size;
int n;

cout << "PLEASE ENTER ARRAY SIZE:-"<<endl;
cin >> size;

cout << ":ARRAY CREATED WITH SIZE OF " << size << " ELEMENTS:"<<endl;

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++;
}

}
if(NotFound){