Linear Search in C++

Linear Seach Algorith in C++

What is a linear search in C++?

Linear search is one of the simplest algorithm of data structure. In the process of linear search, the element to be searched is compared with every element of the list one by one until the element that is to be searched is found. If the element is not found till the end this means that the element is not present in the list. This can be performed on both the sorted list or the unsorted list. Further in this article, we will study the algorithm and a program showing implementation of an algorithm for linear search in C++.

Algorithm to implement linear search in C++

  1. Read the element to be search from the user.
  2. Compare the search element with the first element in the list.
  3. If they both matches,  terminate the function.
  4. Else compare the search element with the next element in the list.
  5. Repeat steps 3 and 4 until the element to be search is found.
Linear search in C++

Program to implement linear search algorithm in C++

#include <iostream>
using namespace std;
int main()
{
  int list[100],size,i,search_el;//Initializing variables.

  cout<<"Enter size of the list: ";//Taking inputs.
  cin>>size;

  cout<<"Enter elements of the list: ";
  for(i = 0; i < size; i++)
  cin>>list[i];

  cout<<"Enter the element to be search: ";
  cin>>search_el;
  
  //Searching element using linear search.
  for(i = 0; i < size; i++)
  {
     if(search_el == list[i])
     {
        cout<<"Element is found at "<< i+1 <<" place in the list";
        break;
     }
  }
  if(i == size)
     cout<<"Element is not present in the list";
  
}
Output:
Enter size of the list: 6
Enter elements of the list: 12
28
41
31
11
43
Enter the element to be search: 31
Element is found at 4 place in the list


Linear search and Binary Search Comparison

  • Linear search (Time complexity): O(n)
  • Binary search (Time complexity): Log(n)
Linear search in C++ Meme

Time Complexity
For Linear Search

Best

O(1)

Average

O(n)

Worst

O(n)

Space Complexity

O(1)

Average Comparisions

(N+1)/2

Quiz time

Fun Fact!

Quiz time

About Linear Search

We follow linear search in our daily life while finding a specific book, medicine or movie in stores. Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your Uber ride? The obvious thing is to go to the parking lot and search all the cars one by one. This method of searching is called linear search, where we search for all possible options until we get our desired result.