What is Linear Search Algorithm in C and its Types?

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.

Read Also: Linear Search vs Binary 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

Output

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.

Read Also: Linked List in a Data Structure

Advantages of Linear Search

• 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.