Linear search is defined as a sequential search algorithm. This algorithm starts from one end and goes through each element of a list until the desired element is found. In this article, we will discuss the basics of linear search algorithms, their Applications, Advantages, Disadvantages, etc. Let’s deep-dive into the linear search algorithm.

What is Linear Search?

Linear search is a method for searching elements in a collection of elements or data structures, such as linked lists, arrays, stacks, and queues. It is also known as Sequential Search. It is the simplest search algorithm in computer programming. In a linear search algorithm, we simply traverse the list and match the item with the desired item. If that item is found, then return its location otherwise, return the NULL.

Get curriculum highlights, career paths, industry insights and accelerate your technology journey.

Download brochure

Algorithm for Linear Search

The following steps explain the linear search algorithm’s working functionality:

Start: It starts from the first element in the list.

Compare: Then, compare that element with the desired element.

Found: If the current element is equal to the desired element, return true or index to the current element.

Move: If the desired element is not found, then move to the next element in the collection or list.

Repeat: Repeat steps 2 – 4 until we have reached the end of the list or collections.

Not Found: If the end of the list is reached without finding the desired element in the list. Then, return that the desired element is not in the array.

How Does Linear Search Algorithm Work?

In this section, we will see “How linear search algorithm works”:

In the linear search algorithm, every element is considered a potential match for the key, and each element is checked one by one.

If the desired element is found equal, then return successful with an index of the desired element.

If no element is found, then return the “No Match Found”.

For example: Consider that array arr[] = {30,90,70,20,450} and key = 20

Step 1: Start from the first element in the array (index 0) and compare the key with each element (arr[j]).

Compare the key with the first element arr[0]. If the key or element is not equal, then the iterator moves to the next element as a potential match.

Step 2: Now, when comparing arr[2] with the key, the value matches. If the key value is equal to the iterator’s next value. Then return successfully otherwise, return the “Match is Not Found”.

Implementation of Linear Search Algorithm

In this section, we will implement a linear search algorithm. Linear search algorithm, we iterate over all the elements of the array
and check if the current element is equal to the desired element. If we find any element to be equal to the desired element. Then, return the index of the current element. Otherwise, If no element is found, then return -1.

The following program implements the Linear search algorithm in C language:

Program

// Linear Search in C language
// Code written by Neeraj Kumar
#include <stdio.h>
int search(int arr[], int N, int x)
{
for (int i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void)
{
int arr[] = { 34, 534, 343, 124, 4340 };
int x = 343;
int length = sizeof(arr) / sizeof(arr[0]);
// Function call
int result = search(arr, length, x);
if(result == -1){
printf(“Element is not present in Array”) ;
}else{
printf(“Element is present at index %d”,result);
}
return 0;
}

Output

Element is present at index 2

Time and Space Complexity of Linear Search

Time Complexity of Linear Search Algorithm:

Best Case: In the Best case Linear Search Algorithm, If the key might be present in the first index, then it will return the best time complexity is O(1).

Worst Case: In the worst case, the key might be present at the last index. The time complexity will be O(N), where N is the size of the list.

Average Case: O(N).

Auxiliary Space: Auxiliary space in Linear search is O(1).

Applications of Linear Search

Unsorted List: When we have an unsorted array or list, the linear search algorithm is most used to find any element in the
collections.

Small Data Sets: When we have small data sets, the linear search algorithm is most efficient compared to the binary search
algorithm.

Searching Linked List: In a Linked List implementation, linear search is commonly used to find elements within the list. Each node is checked sequentially until the desired element is found.

Simple Implementation: Linear Search is much easier to understand and implement as compared to the Binary Search algorithm.

Linear search can be used for any type of data, whether the array is sorted or not.

Does not require additional space in memory for finding the desired element.

It is a well-suited algorithm for small data sets in memory.

Disadvantages of Linear Search

Linear Search has a time complexity of O(N), which in turn makes it slow for large datasets.

Not suitable for large arrays

When to use Linear Search?

When you are using a small dataset.

When you are searching for a dataset that is stored in contiguous memory locations, for example, arrays.

FAQs

What is Linear Search?

Linear Search algorithm, also known as sequential search algorithm. It is a simple searching algorithm that traverses a list or array sequentially to find a target element. In Linear Search.

What is the time complexity of linear search?

The time complexity of linear search is O(n). where n is the number of elements in the list of arrays or any data structure.

What are the advantages of the Linear Search Algorithm?

Linear Search algorithm is easy implementation is easy as compared to binary search algorithm implementation. It does not require pre-processing like sorting an array before finding the desired element in the array or linked list.

Which is faster, linear or binary search algorithm?

The Binary Search Algorithm is faster than the Linear Search Algorithm. In the Binary search algorithm, we must have a sorted array or list for finding the element.

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.