Understanding Linear Search Algorithm, With Examples

Linear Search

Understanding Linear Search Algorithm, With Examples

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)
    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.

Linear Search
Illustration of linear search implemented, with its output shown.


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:

CaseTime Complexity

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:

A simple algorithm to execute and understandCan be inefficient for larger datasets, since each element must be checked
Works well with both sorted and unsorted datasetsMust be specifically modified to exit once the element is found
Memory usage is efficientMay 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.

Understanding Linear Search Algorithm, With Examples FAQs (Frequently Asked Questions) 

What is linear search?

Linear search is a sequential search algorithm that works by searching each element of an array until either the target element is found or the entire array has been searched.


What is the time complexity of linear search?

The time complexity in the average and worst cases is O(n), as it’s directly proportional to the array size. In the best case, however, the complexity is equal to O(1) and independent of array size. This is because the element will be found at the first index.

What is the space complexity of linear search?

The space complexity is equal to O(1), since the memory required by each iteration is constant. This makes the algorithm efficient in terms of memory usage.

What is linear search used for?

Linear search is generally used for relatively simple datasets, where only a simple algorithm is required.

Can linear search be used on sorted or unsorted data?

Linear search can be used for both sorted and unsorted data. The whole array may still be searched, however, if the default implementation is used.

How is linear search best used?

To make linear search more efficient, it’s a good idea to include a break condition, especially if the data is sorted. This will terminate the algorithm once the target element is found, which is particularly useful for sorted data. This is because we can guarantee there will be no more instances of the element.

What are the pros and cons of linear search?

Linear search can be inefficient for large datasets or complex data structures, as it generally searches the entire array. However, it’s a simple algorithm to use, so can be a good choice for small datasets.

To top