Linear Search in C++

May 24, 2022

Linear Search in C

Linear search is one of the simplest algorithms of data structure.

  • 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. 
Linear Seach Algorith in C++
Time ComplexityO(n)
Best CaseO(1)
Worst CaseO(n)
Space ComplexityO(1)
Avg. Comparisons(n+1)/2

Algorithm to implement linear search in C++

  1. Read the item to be searched by 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++

Run

#include<iostream>
using namespace std;

void LinearSearch(int arr[], int len, int item){

    for(int i=0;i<len;i++){
        if(arr[i] == item){
            cout << item << " Found at index : " << i;
            return;
        }
    }
    cout << "Not found";
    
}

int main() {
    int arr[] = {10, 5, 15, 21, -3, 7};
    
    // calculating length of array
    int len = sizeof(arr)/sizeof(arr[0]);
    
    // item to be searched
    int item = 21;
    LinearSearch(arr, len, item);

    return 0;
}
// space complexity: O(N)
// time complexity : O(N)

Output:

21 Found at index : 3

Method 2 (Using Recursion)

This method uses recursion in c++

Run

// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include<iostream>
using namespace std;

int LinearSearch(int arr[], int index, int item)
{
    if(arr[index] == item)
        return index;
    else if (index == -1)
        return -1;
    
    return LinearSearch(arr, index - 1, item);
}

int main() 
{
    int arr[] = {10, 5, 15, 21, -3, 7};

    // calculating length of array 
    int len = sizeof(arr)/sizeof(arr[0]);

    // item to be searched
    int item = 21;
    
    int index = LinearSearch(arr, len - 1, item);

    if(index >= 0)
        cout << "Item found at index: " << index;
    else
        cout << "Item not found";
        
    return 0;
}

Output

Item found at index: 3

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.

Searching

Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.