Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide to Stacks and Queues Data Structures

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 11

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 12

All You Need to Know About Linear Search Algorithm

Lesson - 13

All You Need to Know About Breadth-First Search Algorithm

Lesson - 14

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 15

The Best Tutorial to Understand Trees in Data Structure

Lesson - 16

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 17

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 18

All You Need to Know About Tree Traversal in Data Structure

Lesson - 19

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 20

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 21

Your One-Stop Solution for Graphs in Data Structures

Lesson - 22
All You Need to Know About Linear Search Algorithm

A linear search is the simplest approach employed to search for an element in a data set. It examines each element until it finds a match, starting at the beginning of the data set, until the end. The search is finished and terminated once the target element is located. If it finds no match, the algorithm must terminate its execution and return an appropriate result. The linear search algorithm is easy to implement and efficient in two scenarios:

  • When the list contains lesser elements¬†
  • When searching for a single element in an unordered array

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.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

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.

what-is-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

Linear Search ( Array Arr, Value a ) // Arr is the name of the array, and a is the searched element.

Step 1: Set i to 0 // i is the index of an array which starts from 0

Step 2: ifi > n then go to step 7 // n is the number of elements in array

Step 3: if Arr[i] = a then go to step 6

Step 4: Set i to i + 1

Step 5: Goto step 2

Step 6: Print element a found at index i and go to step 8

Step 7: Print element not found

Step 8: Exit

Pseudocode of Linear Search Algorithm

Start 

linear_search ( Array , value)

For each element in the array

    If (searched element == value)

        Return's the searched lament location

    end if

end for

end

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

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

example-of-linear-search-algorithm.

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

example-of-linear-search-algorithm1.

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.

example-of-linear-search-algorithm2.

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.

example-of-linear-search-algorithm3.

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.

example-of-linear-search-algorithm4

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.

example-of-linear-search-algorithm5.

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.

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.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

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.

Code Implementation of Linear Search Algorithm

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>  

int main()

{

    int array[50],i,target,num;

    printf("How many elements do you want in the array");

    scanf("%d",&num);

    printf("Enter array elements:");

    for(i=0;i<num;++i)

        scanf("%d",&array[i]);

    printf("Enter element to search:");

    scanf("%d",&target);

    for(i=0;i<num;++i)

        if(array[i]==target)

            break;

    if(i<num)

        printf("Target element found at location %d",i);

    else

        printf("Target element not found in an array");

    return 0;

}

The output of linear search algorithm code:

code-implementation-of-linear-search-algorithm.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

Your next topic will be the binary search method, and you will go over the binary search algorithm in detail.

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!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.