C++ Program to Implement Linear Search

Linear search in C++ is a simple search algorithm used to find the position of a target element in an array by sequentially checking each element until a match is found or the end is reached.

Write a C++ Program that finds the position of an element in an array using a Linear Search Algorithm.

1. Create an array of numbers by taking input from the user.
2. Implement the linear search algorithm to find the position of an element in the array, if it exists.
3. Sequentially search through the array elements, starting from the beginning.
4. If the requested element is found, return its position in the array.
5. If the element is not found, return -1 to indicate its absence in the array.

In this method, we use the Linear Search Algorithm to find the position of an element in an array. It creates a separate function for the search and calls it using an object.

Case 1. Best Case: When the element to be searched is the first element of the array.
For example:

If the input array is {4, 6, 1, 2, 5, 3}
and the element to be searched is 4,
then the output will be Position: 1

Best Case time complexity: O(1)

Case 2. Average Case: When the element to be searched is any random element in an array.
For example:

If the input array is {66, -3, 31}
and the element to be searched is 31,
the output will be Position: 3

Average Case time Complexity: O(n)

Case 3. Worst Case: When the element to be searched is absent.
For example:

If the input array is {1, 3, 6, 1, 9}
and the element to be searched is 10,
then the output will be "Element not present".

Worst Case time complexity: O(n)

Here is the source code of the C++ Program to find the position of an element requested by the user using Linear Search Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

/*
 * C++ program to input N numbers and store them in an array.
 * Do a linear search for a given key and report success
 * or failure.
 */
 
#include <iostream>
using namespace std;
class LS
{
    public:
        void LinearSearch(int arr[], int value, int i, int n)
        {   int found = 0;
            for (i = 0; i < n ; i++)
            {
                if (value == arr[i] )
                {
                    found = 1;
                    break;
                }
            }
            if (found == 1)
            {
                cout<<"Element is present in the array at position   "<<i+1;
            }
            else
            {
                cout<<"Element is not present in the array.";
            }
        }
};
int  main()
{  int num;
    int i,  keynum, found = 0;
    cout<<"Enter the number of elements   ";
    cin>>num;
    int array[num];
    cout<<"Enter the elements one by one \n";
    for (i = 0; i < num; i++)
    {
        cin>> array[i];
    }
    cout<<"Enter the element to be searched   ";
    cin>>keynum;
    /*  Linear search begins */
    LS l1;
    l1.LinearSearch(array,keynum,i,num);
    return 0;
}

1. Here in this program we have taken the array as an input from the user along with the key to be searched. We have created a separate function for Linear Search.
2. When the function is called we have to run a loop n times where n is the number of elements in an array.
3. In each iteration we are comparing the value of key with elements of array in increasing order of array index.
4. If key is equal to one of the array elements we print the value of index at which we found them to be equal.

Testcase 1: In this case, we use the linear search algorithm to find the position of the element. The elements are entered in random order (e.g., {4, 6, 1, 2, 5, 3}), and the element to be searched is “4”.

Enter the number of elements   6
Enter the elements one by one
4
6
1
2
5
3
Enter the element to be searched   4
Element is present in the array at position   1

Testcase 2: In this case, we use the linear search algorithm to find the position of the element. The elements are entered in random order (e.g., {66, -3, 31}), and the element to be searched is “31”.

Enter the number of elements   3
Enter the elements one by one
66
-3
31
Enter the element to be searched   31
Element is present in the array at position   3

Testcase 3: In this case, we use the linear search algorithm to find the position of the element. The elements are entered in random order (e.g., {1, 3, 6, 1, 9}), and the element to be searched is “10”.

Enter the number of elements   5
Enter the elements one by one
1
3
6
1
9
Enter the element to be searched   10
Element is not present in the array.

This method uses a linear search algorithm to find an element in a vector of integers. The program takes the number of elements, input values, and the element to be searched. It searches through the elements until the required one is found.

Here is the source code of the C++ Program to find element in a vector using Linear Search Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

/*
 * C++ Program to Implement Linear Search Algorithm
 */
 
#include <iostream>
#include <vector>
 
/* Function to fill Vector */
void make_vector(std::vector<int>& v)
{
    int num, val;
 
    std::cout << "Enter the number of elements in vector ";
    std::cin >> num;
    for (int i = 0; i < num; i++)
    {
        std::cin >> val;
        v.push_back(val);
    }
}
 
/* Linear Search Function */
int lin_search(std::vector<int> v, int val)
{
    int key = -1;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == val)
        {
            key = i;
            break;
        }
    }
    return key;
}
 
int main()
{
    int key, val;
    std::vector<int> v;
 
    make_vector(v);
    std::cout << "Enter the number : ";
    std::cin >> val;
    key = lin_search(v, val);
    if (key != -1)
        std::cout << "\nElement " << val
                  << " is at position " << ++key;
    else
        std::cout << "\nElement " << val
                  << " is not present";
}

1. The program includes necessary header files: <iostream> for input/output and <vector> for using vectors.
2. The make_vector() function fills a vector by taking the number of elements and the elements themselves as input.
3. The lin_search() function performs a linear search on the vector to find a given value and returns its position or -1 if not found.
4. In the main() function, the program creates a vector, takes input elements, and a value to be searched from the user.
5. The program calls the lin_search() function and prints the position if the value is found, else prints a message of its absence.

In this case, we use the linear search algorithm to find the position of the element in vector. The elements are entered in random order (e.g., {2, 4, 10, 23, 32}), and the element to be searched is “4”.

$ g++ main.cpp
$ ./a.out
Enter the number of elements in vector 5
2 4 10 23 32
Enter the number : 4
Element 4 is at position 2

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.