What is Linear Search Algorithm | Time Complexity

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

What Is Searching?

Searching is the process of fetching a specific element in a collection of elements. The collection can be an array or a linked list. If you find the element in the list, the process is considered successful, and it returns the location of that element.

And in contrast, if you do not find the element, it deems the search unsuccessful.

Two prominent search strategies are extensively used to find a specific item on a list. However, the algorithm chosen is determined by the list's organization.

1. Linear Search
2. Binary Search 

Moving ahead in this tutorial, you will understand what exactly a linear search algorithm is.

What Is a Linear Search Algorithm?

Linear search, often known as sequential search, is the most basic search technique. In this type of search, you go through the entire list and try to fetch a match for a single element. If you find a match, then the address of the matching target element is returned. 

On the other hand, if the element is not found, then it returns a NULL value. 

Following is a step-by-step approach employed to perform Linear Search Algorithm.

The procedures for implementing linear search are as follows:

Step 1: First, read the search element (Target element) in the array.

Step 2: In the second step compare the search element with the first element in the array.

Step 3: If both are matched, display "Target element is found" and terminate the Linear Search function. 

Step 4: If both are not matched, compare the search element with the next element in the array. 

Step 5: In this step, repeat steps 3 and 4 until the search (Target) element is compared with the last element of the array.

Step 6 - If the last element in the list does not match, the Linear Search Function will be terminated, and the message "Element is not found" will be displayed.

So far, you have explored the fundamental definition and the working terminology of the Linear Search Algorithm. 

Algorithm and Pseudocode of Linear Search Algorithm

Algorithm of the Linear Search Algorithm

Pseudocode of Linear Search Algorithm

Following your understanding of the linear search algorithm and pseudocode, in the next segment, you will go through the practical implementation of the algorithm.

Also Read: What Is An Algorithm? Characteristics, Types and How to write it

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

How Does Linear Search Algorithm Work?

The linear search algorithm is one of the most basic search techniques for locating an element in a list or array. It functions by iteratively reviewing each item in the list until the desired item is located or the list is reached. Here's a detailed breakdown of how it operates:

1. Initialization

• Start at the first element of the list (index 0).

2. Comparison

• Compare the current element with the target element.

3. Check for Match

• If the current element matches the target element, the search is booming, and the algorithm returns the index of the matching element.
• If the current element does not match the target element, move to the next element in the list.

4. Repeat

• Repeat steps 2 and 3 for each element in the list.

5. End of List

• If the end of the list is reached without finding the target element, the search is unsuccessful, and the algorithm returns a value indicating that the element is not in the list (often -1 or ‘None’).

Example of Linear Search Algorithm

Consider an array of size 7 with elements 13, 9, 21, 15, 39, 19, and 27 that starts with 0 and ends with size minus one, 6.

Search element = 39

Step 1: The searched element 39 is compared to the first element of an array, which is 13.

The match is not found, you now move on to the next element and try to implement a comparison.

Step 2: Now, search element 39 is compared to the second element of an array, 9.

As both are not matching, you will continue the search.

Step 3:  Now, search element 39 is compared with the third element, which is 21.

Again, both the elements are not matching, you move onto the next following element.

Step 4; Next, search element 39 is compared with the fourth element, which is 15.

As both are not matching, you move on to the next element.

Step 5: Next, search element 39 is compared with the fifth element 39.

A perfect match is found, you stop comparing any further elements and terminate the Linear Search Algorithm and display the element found at location 4.

Followed by the practical implementation, you will move on to the complexity of the linear search algorithm.

The Complexity of Linear Search Algorithm

You have three different complexities faced while performing Linear Search Algorithm, they are mentioned as follows.

1. Best Case
2. Worst Case
3. Average Case

You will learn about each one of them in a bit more detail.

Best Case Complexity

• The element being searched could be found in the first position.
• In this case, the search ends with a single successful comparison.
• Thus, in the best-case scenario, the linear search algorithm performs O(1) operations.

Become an Automation Test Engineer in 11 Months!

Automation Testing Masters ProgramExplore Program

Worst Case Complexity

• The element being searched may be at the last position in the array or not at all.
• In the first case, the search succeeds in ‘n’ comparisons.
• In the next case, the search fails after ‘n’ comparisons.
• Thus, in the worst-case scenario, the linear search algorithm performs O(n) operations.

Average Case Complexity

When the element to be searched is in the middle of the array, the average case of the Linear Search Algorithm is O(n).

Next, you will learn about the Space Complexity of Linear Search Algorithm.

Space Complexity of Linear Search Algorithm

The linear search algorithm takes up no extra space; its space complexity is O(n) for an array of n elements.

Now that you’ve grasped the complexity of the linear search algorithm, look at some of its applications.

Application of Linear Search Algorithm

The linear search algorithm has the following applications:

• Linear search can be applied to both single-dimensional and multi-dimensional arrays.
• Linear search is easy to implement and effective when the array contains only a few elements. 
• Linear Search is also efficient when the search is performed to fetch a single search in an unordered-List.

Finally, in this tutorial, you will implement the linear search algorithm in code.

Also Read: Arrays in Data Structure

Code Implementation of Linear Search Algorithm

The output of linear search algorithm code:

Unleash a High-paying Automation Testing Job!

Automation Testing Masters ProgramExplore Program

1. C Implementation

#include <stdio.h>
#include <string.h>

// Define the Employee structure
struct Employee {
    int EmployeeID;
    char FirstName[50];
    char LastName[50];
    char BirthDate[11]; // YYYY-MM-DD format
    char HireDate[11];  // YYYY-MM-DD format
    double Salary;
};

// Function to display employee information
void displayEmployee(struct Employee emp) {
    printf("ID: %d\n", emp.EmployeeID);
    printf("First Name: %s\n", emp.FirstName);
    printf("Last Name: %s\n", emp.LastName);
    printf("Birth Date: %s\n", emp.BirthDate);
    printf("Hire Date: %s\n", emp.HireDate);
    printf("Salary: %.2f\n", emp.Salary);
}

int main() {
    // Create an instance of Employee
    struct Employee emp;

    // Assign values to the employee instance
    emp.EmployeeID = 1;
    strcpy(emp.FirstName, "John");
    strcpy(emp.LastName, "Doe");
    strcpy(emp.BirthDate, "1980-01-01");
    strcpy(emp.HireDate, "2020-01-01");
    emp.Salary = 50000.00;

    // Display employee information
    displayEmployee(emp);

    return 0;
}

2. C++ Implementation

In C++, you can define a class to represent the ‘Employees’ table.

#include <iostream>
#include <string>

class Employee {
public:
    int EmployeeID;
    std::string FirstName;
    std::string LastName;
    std::string BirthDate;
    std::string HireDate;
    double Salary;

    Employee(int id, std::string firstName, std::string lastName, std::string birthDate, std::string hireDate, double salary)
        : EmployeeID(id), FirstName(firstName), LastName(lastName), BirthDate(birthDate), HireDate(hireDate), Salary(salary) {}

    void display() {
        std::cout << "ID: " << EmployeeID << "\n"
                  << "First Name: " << FirstName << "\n"
                  << "Last Name: " << LastName << "\n"
                  << "Birth Date: " << BirthDate << "\n"
                  << "Hire Date: " << HireDate << "\n"
                  << "Salary: " << Salary << std::endl;
    }
};

int main() {
    Employee emp(1, "John", "Doe", "1980-01-01", "2020-01-01", 50000.00);
    emp.display();
    return 0;
}

3. Java Implementation

In Java, you can define a class to represent the ‘Employees’ table.

public class Employee {
    private int EmployeeID;
    private String FirstName;
    private String LastName;
    private String BirthDate;
    private String HireDate;
    private double Salary;

    public Employee(int employeeID, String firstName, String lastName, String birthDate, String hireDate, double salary) {
        this.EmployeeID = employeeID;
        this.FirstName = firstName;
        this.LastName = lastName;
        this.BirthDate = birthDate;
        this.HireDate = hireDate;
        this.Salary = salary;
    }

    public void display() {
        System.out.println("ID: " + EmployeeID);
        System.out.println("First Name: " + FirstName);
        System.out.println("Last Name: " + LastName);
        System.out.println("Birth Date: " + BirthDate);
        System.out.println("Hire Date: " + HireDate);
        System.out.println("Salary: " + Salary);
    }

    public static void main(String[] args) {
        Employee emp = new Employee(1, "John", "Doe", "1980-01-01", "2020-01-01", 50000.00);
        emp.display();
    }
}

4. Python Implementation

In Python, you can define a class to represent the ‘Employees’ table.

class Employee:
    def __init__(self, employee_id, first_name, last_name, birth_date, hire_date, salary):
        self.EmployeeID = employee_id
        self.FirstName = first_name
        self.LastName = last_name
        self.BirthDate = birth_date
        self.HireDate = hire_date
        self.Salary = salary

    def display(self):
        print(f"ID: {self.EmployeeID}")
        print(f"First Name: {self.FirstName}")
        print(f"Last Name: {self.LastName}")
        print(f"Birth Date: {self.BirthDate}")
        print(f"Hire Date: {self.HireDate}")
        print(f"Salary: {self.Salary}")

emp = Employee(1, "John", "Doe", "1980-01-01", "2020-01-01", 50000.00)
emp.display()

5. JavaScript Implementation

In JavaScript, you can define a class to represent the ‘Employees’ table.

class Employee {
    constructor(employeeID, firstName, lastName, birthDate, hireDate, salary) {
        this.EmployeeID = employeeID;
        this.FirstName = firstName;
        this.LastName = lastName;
        this.BirthDate = birthDate;
        this.HireDate = hireDate;
        this.Salary = salary;
    }

    display() {
        console.log("ID: " + this.EmployeeID);
        console.log("First Name: " + this.FirstName);
        console.log("Last Name: " + this.LastName);
        console.log("Birth Date: " + this.BirthDate);
        console.log("Hire Date: " + this.HireDate);
        console.log("Salary: " + this.Salary);
    }
}

const emp = new Employee(1, "John", "Doe", "1980-01-01", "2020-01-01", 50000.00);
emp.display();

Next Steps

Your next topic will be the binary search method, and you will go over the binary search algorithm in detail. Finding an entry in an unordered list is the main application for linear search, the most straightforward search technique. Another name for it is the sequential search algorithm. The list is iterated sequentially in a linear search, comparing each element to the target element whose position must be determined.

Simplilearn's mobile and software development course will be ideal for you if you want a more comprehensive study that goes beyond Data Structure and covers the most in-demand programming languages and abilities today. Now is the time to get out there and explore.

Do you have any questions about this Linear Search Algorithm tutorial? Please leave them in the comments section at the bottom of this page if you have any. Our experts will respond as quickly as possible!

FAQs

1. What Are the Steps of a Linear Search Algorithm?

• Begin with the array's first entry.
• The target value and the current element should be compared.
• Return the current element's index if the current element and the target value match.
• Proceed to the next element if the current element does not match the desired value.
• Till the end of the array is reached, repeat steps 2-4.
• Return -1 or indicate that the target value is not present in the array if, after verifying every element, the target value cannot be located.

2. What Is the Best Case Algorithm for Linear Search?

When the target value is located at the first position in the list, the best-case technique for linear search is used. In this case, finding the requested element just requires one comparison on the part of the algorithm. As a result, the best-case scenario's time complexity for linear search is O(1), indicating continuous time complexity. This suggests that if the target value is at the beginning, the search will be finished in a single step regardless of the list size. For small or unsorted datasets, linear search is simple and efficient, but as list sizes grow, especially in average and worst-case circumstances, its effectiveness diminishes.

3. What Is the Technique Used in Linear Search?

Until it discovers the target value or reaches the end of the list, linear search employs a simple technique that involves checking each element in a list one after the other. Beginning with the first element, the search proceeds through each one, comparing the current element with the desired value. The search ends, and the matched element's index is returned if a match is discovered. The search determines that the target is not in the list if the end of the list is reached without it being found. This method is straightforward and doesn't need the list to be sorted, which makes it adaptable to different kinds of data. However, because of its linear time complexity, it is ineffective for big datasets O(n)

4. What Is a Real-Life Example of a Linear Search Algorithm?

Looking up a specific contact in a phone book provides a practical illustration of a linear search process. Envision possessing a tangible address book with contacts arranged in an arbitrary sequence. Starting at the beginning of the book, you go through each entry one by one to locate a particular contact. You cross-reference each name to ensure it is the one you want. You give up looking if you find the contact. You conclude that the contact is only in the book if you finish the book with locating the name. This procedure resembles the linear search algorithm, in which every element is examined one after the other until the target element or the search space is exhausted.