Linear Search algorithm is also known as Sequential Search. The search process will start from first element and goes sequentially.
In this algorithm, we first initialize a variable position = -1. Then we iterate through every element in the array and compare it with the key (element to be searched).

If key is equal to an array element, we update the value of position with the index value of that element and stop the iteration.

If not, we go to the next element.

If there isn't any element in array which is equal to key, the value of position remains -1 denoting that the element is not found in array.

Example 1 for Linear Search :

Let array = {44,76,28,18} and key = 28

Screenshot 61

Here, the position is updated to 2 denoting that the key is at 2nd index of the array.

Example 2 for Linear Search:

Let array = {56,64,32,12,29} and key = 23

Screenshot 60

Here, after iterating through the complete array, the value of position is still -1. So, key is not found in the array.

Advantage of Linear Search: This algorithm works even if the array elements are not in sorted order.

Disadvantage of Linear Search: During each comparison, only one element is eliminated for the list of array elements.

Time Complexity: O(n)  where, n is the total number of elements in the array. The time complexity is same for Worst and Average cases.

Space Complexity: O(1)

C++ CODE FOR LINEAR SEARCH:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,n,key,position=-1;
    cout << "Enter the number of elements in the array" << endl;
    cin >> n; // Taking number of elements in the array as input
    int array[n];
    cout << "Enter the elements in the array" << endl;
    for(i=0;i<n;i++) // loop to take array elements as input
    {
        cin >> array[i];
    }
    cout << "Enter the element to be searched" << endl;
    cin >> key; // Taking element to be searched as input
    for(i=0;i<n;i++) // loop to check each element in the array
    {
        if(key==array[i]) // checking if the value of key is equal to array[i]
        {
            // if yes, updating the value of position and stoping the iteration
            position=i;
            break;
        }
    }
    if(position==-1) // checking if the value of position still remains -1
    {
        cout << "key is not found in the array" << endl; // if yes, key is not found
    }
    else
    {
        cout << "key found at position " << position << endl; // if no, key is found at the updated position
    }
    return 0;
}

 Test Case for Linear Search:

Enter the number of elements in the array
6
Enter the elements in the array
66 12 34 56 78 90
Enter the element to be searched
34
key found at position 2