C++ program to implement linear search

C++ linear search implementation:

In this post, we will learn how to implement linear search in C++ with example. Linear search is also called sequential search. It searches for an element sequentially until a match is found or the whole list is searched.

Example of linear search:

To understand how linear search works, let’s take an example of the following array:

[1, 4, 8, 2, 3, 10]

Suppose, we want to search 2 in this array by using linear search.

The search will start from index 0.
It will compare 1 with 2. As these are not equal, it will move to the next element.
The loop will stop at index 3 and return this index as the element at this index is 2.

C++ program to implement linear search:

Below is the complete C++ program that uses linear search to search for an element in an array:

#include <iostream>
using namespace std;

int linearSearch(int arr[], int size, int v)
{
    for (int i = 0; i < size - 1; i++)
    {
        if (arr[i] == v)
        {
            return i;
        }
    }
    return -1;
}

int main()
{
    int givenArray[] = {2, 8, 1, 5, 30, 21};
    int size = sizeof(givenArray) / sizeof(givenArray[0]);
    int item = 5;

    int itemIndex = linearSearch(givenArray, size, item);

    if (itemIndex != -1)
    {
        cout << "The given number is found at index: " << itemIndex << endl;
    }
    else
    {
        cout << "The given number is not found in the array!" << endl;
    }
}

Here,

The linearSearch method is used for the linear search. It takes one array, the size of the array and the item to search in the array as its parameters.
It uses a for loop to iterate over the items of the array one by one and compares each item with the array elements. It returns the index where the array element is equal to the given number. Else, it returns -1.
Based on the returned index value, it prints a message to the user i.e. the given number is found or not found in the array.

If you run the above program, it will print:

The given number is found at index: 3

You can try by changing the item to different values.

Time and Space complexities of linear search:

The linear search has O(n) time complexity and O(1) space complexity. It makes at most n comparisons if the element is not found in the list.

You might also like:

Updated on 14 Nov 2022

Journey with Code and DesignCodeVsColor on Twitter About
Privacy Policy
T&C
Contact