Linear Search: Searching Made Easy
Updated: Jun 3, 2022
Algorithm
Linear search is one of the simplest searching algorithms. Linear search finds the target element by sequentially checking every element in the given input array. This is why linear search is sometimes also referred to as sequential search. Linear search works on both sorted and unsorted arrays.
For an input array arr and a target element lets say x, linear search does the following steps:
Iterate through the input array from start to end (or end to start, traversal order does not matter).
In each iteration compare the current element to the target element x.
If current element is equal to the target element x, you have found the element you are looking for. Stop the iteration and return the current element index as result.
If current element is not equal to x, continue to the next element and repeat the above steps until you find the target element or you have reached the end of the array. If the target element x is not found then return -1 as the result indicating the target value is not present in the given array.
Working
Consider the given input array is [3, 7, 1, 5, 11] and the target element x=1 as shown below:
Lets say i is our index variable. Linear search algorithm starts by checking the element at index 0, as shown in the below diagram.
Now the algorithm checks whether the current element arr[0] is equal the target element x. Clearly arr[0] is not equal to the target element x. So, the algorithm continues to the next element at index i=1 as shown below:
Again arr[1] is also not equal to the target element x. So our algorithm continues to the element at next index i=2.
Now the element at index 2, arr[2]=1. This is nothing but the target element we are looking for which means we have found our answer. So the algorithm returns 2 as the result indicating that the target element x is found at index 2 in the given array [3, 7, 1, 5, 11].
Implementation
Language: Go
Complexity Analysis
Time Complexity: O(n)
Time complexity of linear search algorithm is O(n). In the worst case our algorithm would end up comparing every element in the given input array to the target element x.
The worst case occurs if the target element is the last element in the input array or the target element itself is not present in the array.
Space Complexity: O(1)
The algorithm doesn't use any extra space.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Applications
Linear search is mostly used in cases where the size of the given input array is small. When the size of the array is large it is preferable to use other search algorithms like binary search which has a better time complexity than linear search.
Unlike some other search algorithms like binary search, jump search, exponential search etc. which work only on sorted arrays, linear search works on both sorted and unsorted arrays. So linear search could be useful in this case. It is also important to note that for cases where the input array is not sorted, it might make sense to sort the array first and then search using faster algorithms like binary search. But if it is a frequently changing list, sorting every time and then sorting using binary search might not be worth it.
Output
You can test your code using the below code snippet:
Language: Go
Below is the result of test execution:
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe in our blogs section.
Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time. Join now.
留言