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;
        }
    }
    cout<<"element was not found in the array\n";
}

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[0] == x) // base case
    {
        cout<<"element found in array\n";
        return;
    }
    if(i == (n - 1)) // base case
    {
        cout<<"element was not found in the array\n";
        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 
    {
        cout<<"element was not found in the array\n";
        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;
}

For more information on pointers click on this link.

For more information, you can refer to Geeks For Geeks.