There are many algorithms you can use to search a dataset. Of these, linear search is one of the simplest. The algorithm isn’t suitable for all scenarios but remains one that programmers of all levels should know. What’s more, understanding how linear search works will make it easier to understand more complex algorithms. Today, we’re going to look at how linear search works and how to best use it.
What is Linear Search?
Linear search is an algorithm used to search an element list. This is done sequentially, meaning each element is checked consecutively, one by one. If the current element doesn’t match the element we’re looking for, then NULL is returned. If the element does match, the position of the element is returned and the search is complete. Linear search is useful because it’s relatively easy to use, and can be used for both sorted and unsorted lists.
How is Linear Search Used?
The steps involved in the linear search algorithm are quite easy to follow. These are the general steps:
- Firstly, the array of elements is traversed, usually by using a for loop.
- The current element is then compared with the element we’re looking for, known as the search element.
- If the element isn’t found, NULL is returned and the iterations continue.
- Once the element matches, the index of this element is returned.
- If the entire array is traversed and the element is still not found, -1 is returned to indicate the algorithm was unsuccessful.
Implementation of Linear Search
To show how linear search works, we’ll demonstrate with an example in the Python language. Let’s consider a fairly basic array of 10 elements – [4, 8, 2, 9, 14, 3, 6, 10, 19, 24]. In this case, we’re looking for the element with the value “3”. This would be conducted in Python as follows:
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
array = [4, 8, 2, 9, 14, 3, 6, 10, 19, 24]
element = 3
index = linear_search(array, element)
if index != -1:
print("Element", element, "found at", index)
else:
print("Element", element, "not found.")First, we define the “linear_search” function, which takes the “arr” and “target” parameters. These are the array to be searched and the target element respectively.
We then declare a for loop, which iterates over each element of the array, comparing the current element to the target. As mentioned before, this returns -1 if the element isn’t found, and the element index if it is found.
We then give our example array and the value of the target element. After this, we finish by using an if-else statement. If the element matches, the index is printed to the console, preceded by “Element” and succeeded by “found at [index]”. If the element isn’t found, the message “Element [value] not found” is printed, as per the else statement.
We can see that element “3” has been found at index 5 in the accompanying image.
©History-Computer.com
Time and Space Complexity
While linear search is a simple algorithm, it may not be suitable for all scenarios, since it must search the entire array. The time complexity of linear search is given as:
| Case | Time Complexity |
|---|---|
| Best | O(1) |
| Average | O(n) |
| Worst | O(n) |
We can see that, in the best case, the time complexity is constant-time. This would be when the element we’re looking for is at the first index of the array. In this case, the time is independent of the array size.
However, that situation would be fairly unlikely. In the average case, the complexity is proportional to the array size, because the element has equal probability of being found anywhere in the array. This means that we would have to, on average, search around half of the array elements each time. The worst case is when the element is found at the last index of the array. This also gives a complexity proportional to the array size. Whereas we may expect to find the element relatively quicker in the average case, the complexity still increases proportionally to the array size.
Regarding the space complexity, this is the same in all cases, and equal to O(1). This means that the memory required is constant, independent of array size. This is because the iterations of the algorithm are of the same complexity, and no additional operations are needed. Overall, linear search is quite efficient in terms of memory usage.
What Are the Best Practices of Linear Search?
As mentioned, linear search isn’t complicated, but this also means it might not be the most efficient choice. Therefore, to use the algorithm most effectively, it’s a good idea to keep these guidelines in mind:
- Break statements – If your data is sorted, a break condition is preferable. This is because, once the element is found, we know there will be no more matches further in the array. Therefore, using a break statement to exit the for loop will significantly increase efficiency.
- Consider the array size – If your array is of appreciable size, it’d be wise to use a more efficient data structure, such as a binary search tree or a hash table. This allows the algorithm to search the elements in less time.
- Readability – As with any coding project, it’s beneficial to pay attention to the descriptors you’re using, as well as make sure you’re following typical conventions. Chances are you may be collaborating with other coders on the project, and it’s useful to make sure they can understand your workings easily.
What Are the Pros and Cons of Linear Search?
No algorithm is without its perks or its flaws. When we’re talking about linear search, these are some of the most important advantages and drawbacks:
| Pros | Cons |
|---|---|
| A simple algorithm to execute and understand | Can be inefficient for larger datasets, since each element must be checked |
| Works well with both sorted and unsorted datasets | Must be specifically modified to exit once the element is found |
| Memory usage is efficient | May not work as well for complex data structures like graphs or elaborate trees |
Wrapping Up
Overall, linear search is a simple algorithm that’s very useful for searching smaller or sorted datasets. While it may not be efficient for large datasets or complex data structures, it works well for unsorted and sorted data and has constant memory requirements. Whatever your knowledge level, knowing how linear search works is important as this will help you understand more elaborate search algorithms.
The image featured at the top of this post is ©Patthana Nirangkul/Shutterstock.com.
