Hi everyone, inside this article we will see the concept about Linear Search Analysis.
Linear search is a simple search algorithm that is used to find a target element within a collection or data structure. It is also known as a sequential search because it sequentially compares each element in the collection with the target element until a match is found or the end of the collection is reached.
How Algorithm of Linear Search works?
Here is the step-by-step process for implementing a linear search algorithm:
- Start at the first element of the collection.
- Compare the current element with the target element.
- If the elements match, return the index of the current element.
- If the elements do not match, move on to the next element in the collection.
- Repeat steps 2-4 until a match is found or the end of the collection is reached.
- If the end of the collection is reached without finding a match, return a message indicating that the target element is not in the collection.
In summary, linear search is a simple search algorithm that sequentially compares each element in a collection with a target element until a match is found or the end of the collection is reached. It is easy to understand and can be used with any type of collection, but it may be inefficient for large collections.
Here is the pseudocode for linear search:
linear_search(collection, target):
for each element in collection:
if element equals target:
return true
return false
In this pseudocode, the collection parameter represents the collection of elements that we want to search, while the target parameter represents the element that we want to find within the collection. The algorithm works by iterating through each element in the collection one by one, and checking whether it is equal to the target element. If a match is found, the function returns true. If the end of the collection is reached and no match is found, the function returns false.
Here’s an example of how the linear search algorithm works:
Suppose we have the following collection of numbers.
[6, 4, 9, 2, 3, 7, 5, 8, 1]And we want to find the index of the number 7 in the collection.
- Set index to 0
- While index is less than the length of the collection (which is 9 in this case), repeat steps 3-4:
- Index = 0: The current element is 6, which is not equal to 7, so we move to the next element.
- Index = 1: The current element is 4, which is not equal to 7, so we move to the next element.
- Index = 2: The current element is 9, which is not equal to 7, so we move to the next element.
- Index = 3: The current element is 2, which is not equal to 7, so we move to the next element.
- Index = 4: The current element is 3, which is not equal to 7, so we move to the next element.
- Index = 5: The current element is 7, which is equal to the target element, so we return the index 5 and terminate the search.
The linear search algorithm found the target element 7 at index 5, and it took 6 comparisons (iterations) to do so.
Example Code
Here’s an example of a C++ program that performs linear search:
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int target)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == target)
{
return i; // return the index of the target element
}
}
return -1; // return -1 if the target element is not found
}
int main()
{
int arr[] = {5, 10, 15, 20, 25, 30};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 20;
int index = linearSearch(arr, n, target);
if (index != -1)
{
cout << "Element found at index " << index << endl;
}
else
{
cout << "Element not found" << endl;
}
return 0;
}
The above program will output:
Element found at index 3In this program, we define a function linearSearch that takes an integer array arr, its size n, and a target integer target. The function returns the index of the target element in the array, or -1 if the target element is not found. The function works by iterating over the elements of the array one by one, and comparing each element with the target element. If the target element is found, the function returns its index.
Complexity Analysis of Linear Search
The time complexity of linear search algorithm is O(n), where n is the number of elements in the collection being searched.
This means that in the worst case scenario, the algorithm will need to look at every element in the collection to determine if the target element is present or not. In the average case, the algorithm may only need to examine half of the collection before finding the target element.
However, the space complexity of linear search is O(1), because the algorithm only needs to store a few variables (like the index and the target element) in memory at any given time.
It’s important to note that linear search is a simple and straightforward algorithm, but it may not be efficient for very large collections. In cases where the collection is sorted or has some other structure, there may be more efficient search algorithms available, such as binary search. Nonetheless, linear search remains an important algorithm to know and understand, as it is often used as a baseline for comparison with more complex search algorithms.
When is the Linear Search algorithm used?
Linear search is used when the collection of elements is small or unsorted, and we need to find the presence of a specific element in the collection. It is a simple and easy-to-understand algorithm that works by scanning each element of the collection one by one until the target element is found.
Linear search is particularly useful in cases where the collection of elements is constantly changing, and there is no time to sort the collection before searching for an element. For example, linear search could be used to search for a specific word in an unsorted text file.
Linear search is also a useful algorithm for educational purposes, as it provides a good starting point for learning about search algorithms and their complexities. In addition, linear search can be useful as a baseline for measuring the efficiency of more complex search algorithms, such as binary search or hash table lookup.
Advantages of Linear Search Algorithm:
- Linear search is a simple and easy-to-understand algorithm, making it ideal for beginners learning about search algorithms.
- Linear search is effective when searching for a single occurrence of a specific element in a small or unsorted collection of elements.
- Linear search can be implemented using a small amount of memory, making it suitable for use in memory-constrained environments.
Disadvantages of Linear Search Algorithm:
- Linear search has a time complexity of O(n), which means that the search time increases linearly with the size of the collection. This makes it inefficient for large collections or applications that require frequent searches.
- Linear search is not suitable for finding multiple occurrences of the same element, as it will only return the first occurrence it finds.
- Linear search does not take advantage of any structure or ordering within the collection, which means it may not be the most efficient algorithm for sorted or partially sorted collections. In such cases, binary search or other more complex algorithms may be more appropriate.
Overall, while linear search has some advantages, its inefficiency for larger collections and inability to find multiple occurrences of the same element make it less suitable for many practical applications. Nonetheless, it remains an important algorithm to understand, as it serves as a baseline for comparison with more complex search algorithms.
We hope this article helped you to understand Linear Search Analysis in a very detailed way.
Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.
If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.