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.
What is Searching
Searching is the act of locating a specific item within a group of items. This group can be represented as an array or a linked list. If the item is found, the search is considered successful and its location is returned.
On the other hand, if the item is not found, the search is deemed unsuccessful.
Two common search strategies are widely used for finding a specific element in a list. The choice of algorithm depends on the structure of the list. These are Linear Search and Binary Search. In this tutorial, you will learn about the Linear Search algorithm in detail.
Linear Search
Linear Search is a data search technique that traces all data. If data matches are found, the program will return the output. Otherwise, the search will continue until the end of the array.
This algorithm is unsuitable for large data sets because the complexity of this algorithm is Ο(n), where n is the number of items. If the data you are looking for is at the end of the array, then the program must browse through all the collections first.
For example, the number you are looking for is 40. Here is an overview of the implementation of linear search:
1st Cycle:
(70, 60, 30, 50, 40,20)
(70==40) //FALSE
2nd Cycle:
(70, 60, 30, 50, 40,20)
(60==40) //FALSE
3rd Cycle:
(70, 60, 30, 50, 40,20)
(30==40) //FALSE
4th Cycle:
(70, 60, 30, 50, 40,20)
(50==40) //FALSE
5th Cycle:
(70, 60, 30, 50, 40,20)
(40==40) //TRUE
If data is found, the program will exit the loop. If we want to display the index of the data we are looking for, all we have to do is store the index of the array and say it.
The Complexity of Linear Search Algorithm
The complexity of a linear search algorithm is measured by the number of operations it performs before finding the target element or determining that it is not present in the data set.
You have three different complexities faced while performing Linear Search Algorithm, they are mentioned as follows.
- Best Case
- Worst Case
- Average Case
In the worst-case scenario, the target element is not present in the data set, and the algorithm must examine each element, one by one, resulting in a time complexity of O(n) where n is the number of elements in the data set.
In the best-case scenario, the target element is the first element in the data set, and the algorithm only needs to perform one operation, resulting in a time complexity of O(1).
On average, the time complexity of a linear search algorithm is O(n/2) for a randomly ordered data set.
Therefore, the linear search algorithm is efficient for small data sets or when the target element is likely to be near the beginning of the data set.
Let’s take a look at explanation below for the details
1. Best Case Complexity
In computer science, the best case complexity of an algorithm refers to the scenario where the algorithm performs the least number of operations or takes the least amount of time to find the solution.
This is typically when the input data is already in the desired state or the solution is easily found.
For example, in a linear search algorithm, the best case scenario would be when the element being searched for is the first element in the array.
In this case, the algorithm would only need to perform one comparison and would immediately return the location of the element, making the best-case time complexity O(1) (constant time)
It is important to note that the best-case scenario is not always the most likely scenario and it is often more useful to consider the average or worst-case complexities of an algorithm when evaluating its performance.
2. Worst Case Complexity
The worst-case complexity of an algorithm refers to the maximum amount of resources (such as time or memory) that the algorithm may require to run, given certain inputs.
For the linear search algorithm, the worst-case scenario occurs when the element being searched for is not present in the array or list.
In this case, the algorithm must examine every element in the array or list before determining that the element is not present. As such, the worst-case time complexity of the linear search algorithm is O(n), where n is the number of elements in the array or list.
This means that the running time of the algorithm increases linearly with the number of elements in the array or list.
3. Average Case Complexity
The average case complexity of an algorithm refers to the expected performance of the algorithm when applied to a randomly selected input of a given size
. In the case of linear search, the average case complexity is O(n), where n is the number of elements in the input list. This means that on average, the algorithm will take n/2 steps to find the target element in a list of n elements.
It’s because on average, the target element is located at the middle of the list, and the algorithm needs to examine half of the elements before finding it. However, in the worst-case scenario, it will take n steps, in the case that the element is not present in the array.
Linear Search Algorithm Application
1. As Search Engine in E-commerce
One application of the linear search algorithm is in searching for a specific element in an unordered list or array. For example, a linear search algorithm can be used to search for a specific item in a list of products in an e-commerce website.
The algorithm would start at the first element of the list and compare it to the target item, then move on to the next element and repeat the comparison until a match is found or the end of the list is reached.
This method is simple and easy to implement, and is efficient for small lists or when searching for a single element in an unordered array.
2. Library Catalog System
A library catalog system can use a linear search algorithm to search for a specific book by iterating through a list of all books in the library’s collection.
The algorithm would start at the first book in the list and compare the title or author of the book to the search query.
If the book does not match the search query, the algorithm would move to the next book in the list and repeat the comparison until a match is found or the end of the list is reached. This method is simple but it can be slow for large collections.