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.
- Linear Search
- 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
|
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.
Also Read: What Is An Algorithm? Characteristics, Types and How to write it
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.
- Best Case
- Worst Case
- 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.
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
|
#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:
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!
