# Linear Search in c++ | loops | recursion

The linear search in c++algorithm is used for finding an element in the array.

Time Complexity: O(n)
Space Complexity: O(1)

The algorithm is as follows :

Traverse the whole array and break out of the loop if the element is found else element is not found.

NOTE: Linear Search is used mostly for unsorted arrays.

The below code shows an implementation using loops.

``````#include<bits/stdc++.h>
using namespace std;

void linear_search(int* arr , int n , int x)
{
for(int i=0;i<n;i++)
{
if(arr[i] == x)
{
cout<<"element was found in the array\n";
return;
}
}
}

int main()
{
int n,x;
cout<<"enter the size of array : ";
cin>>n;
int* arr = new int[n];
cout<<"enter array elements : ";
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"enter the element you want to find in array : ";
cin>>x;
linear_search(arr , n , x);
return 0;
}``````

## Linear Search using recursion

(i) forward search
(ii) backward search

## forward search using recursion

``````#include<bits/stdc++.h>
using namespace std;

void linear_search_forward_recursion(int* arr , int n , int x , int i = 0)
{
if(arr == x) // base case
{
cout<<"element found in array\n";
return;
}
if(i == (n - 1)) // base case
{
return;
}
linear_search_forward_recursion(arr + 1 , n , x , i + 1); // recursion
}

int main()
{
int n,x;
cout<<"enter the size of array : ";
cin>>n;
int* arr = new int[n];
cout<<"enter array elements : ";
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"enter the element you want to find in array : ";
cin>>x;
linear_search_forward_recursion(arr , n , x);
return 0;
}``````

## backward search using recursion

``````#include<bits/stdc++.h>
using namespace std;

void linear_search_backward_recursion(int* arr , int n , int x)
{
if(arr[n - 1] == x)// base case
{
cout<<"element was found in the array\n";
return;
}
if(n == 1) // base case
{
return;
}
linear_search_backward_recursion(arr , n - 1 , x);
}

int main()
{
int n,x;
cout<<"enter the size of array : ";
cin>>n;
int* arr = new int[n];
cout<<"enter array elements : ";
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"enter the element you want to find in array : ";
cin>>x;
linear_search_backward_recursion(arr , n , x);
return 0;
}`````` 