Linear Search in Python: A Beginner's Guide with Examples

When it comes to search algorithms, linear search is one of the simplest. If you’ve ever looked through a list of items one by one until you found what you were searching for, then you’ve already done a linear search!

In addition to being easy to understand, linear search is useful because it works on unsorted data, unlike some other search algorithms. This versatility makes it a useful option in scenarios where data sorting isn’t possible. I'll be using Python in this tutorial so, if, before we get started, you want a refresher on Python, check out the Python Programming skill track.

What is Linear Search?

Linear search is an algorithm that locates a specific value within a list by checking each element one by one. It starts at the first item, compares it to the target, and then continues to move through the list until it either finds the target, or it reaches the end of the list. It’s a simple and intuitive algorithm.

Linear search doesn’t need the data to be sorted in order to work, so it is primarily used in unsorted datasets. This makes it handy for situations where sorting isn’t practical, or you’re working with data in its raw form. However, this benefit comes with a cost: it’s not as efficient as other algorithms that require presorted data.

Linear search is ideal in situations where you’re working with relatively small datasets or when sorting the data is not feasible. The below diagram gives a simplified explanation.

Choosing Linear Search

Let's take a look at the advantages and also one distinct drawback: 

Why Choose Linear Search?

To my mind, linear search has three distinct benefits:

When Simplicity is Key

One of the biggest advantages of linear search is its simplicity. The algorithm is easy to understand and implement. There’s no need to worry about complex sorting or splitting the data. Simply start at the beginning of the list and check each element until you find what you’re looking for.

When You Don’t Have Time to Sort

Unlike other search algorithms like binary search, linear search doesn’t require the dataset to be sorted. This makes it perfect for when you need a quick way to find something.

When You Need Versatility

Another perk of linear search is that it’s versatile. It works not just with arrays but also with other Python data structures, like linked lists. As long as you can sequentially access the elements, linear search can get the job done. It’s flexible enough to handle different data types, from numbers to strings, and even objects.

Why Think Twice About Linear Search?

There is an issue to consider:

When Efficiency Matters

The major downside to linear search is its inefficiency, especially with large datasets. Its time complexity is O(n), meaning that in the worst case, you might have to check every single element in the list! This can really slow things down if you’re working with thousands or millions of entries. For small datasets, however, this inefficiency may be negligible.

Implementing a Linear Search Algorithm in Python

In Python, there are two common ways to write a linear search: the iterative method and the recursive method. To demonstrate these two methods, let’s first create a simple dataset of 100 numbers with no duplicates.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]

Iterative method

The iterative approach is probably the easiest way to understand linear search. You loop through the list, checking each element until you find the target or reach the end.

First, we’ll create our function:

1. We’ll loop through each element in the list arr.

2. We’ll compare each element with the target.

3. If we find a match, we return the index where the target was found.

4. If we finish the loop without finding the target, we return 1 to indicate that the element isn’t present.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not found

Next, we’ll run our function on our dataset, and print the result:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")

Running this code, we find the target value at the 23rd element.

Recursive method

The recursive method uses a function that calls itself to search through the list. Each recursive call processes one element at a time and then moves on to the next element. This continues until the target is found or the end of the list is reached.

Let’s create our recursive function:

1. We’ll start by checking the first element (at index 0).
2. If the target matches, we’ll return the index.
3. If the target doesn’t match, we’ll call the same function recursively, but increment the index by 1 to check the next element.
4. The recursion continues until we find the target or reach the end of the list.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next element

We can use the same code as above to run this function and it returns the same index value for our target: 23.

Keep in mind that this approach uses more memory because each recursive call adds a new layer to the call stack. Check out Understanding Recursive Functions in Python for a closer look at recursion.

Time and Space Complexity

One way to evaluate the efficiency of an algorithm is to look at its time and space complexity. Check out the Analyzing Complexity of Code through Python tutorial for a look at the different ways to measure the complexity of an algorithm.

Time complexity

The time complexity of an algorithm refers to how the time it takes to complete increases as the size of the input grows. The time complexity of linear search is O(n), where n is the number of elements in the list. This means that in the worst case, the algorithm may need to check every single element before finding the target (or determining that the target isn’t in the list). This is pretty inefficient, especially for large datasets. That’s why linear search works best when we have smaller, unsorted datasets that we only need to search through once.

Space complexity

The space complexity of an algorithm is a measure of how much memory it requires as the size of the input grows. The space complexity of the linear search algorithm depends on which method we use. For the iterative method, the space complexity is O(1), meaning the algorithm requires a constant amount of memory, regardless of the size of the input list. This is because the iterative version doesn’t require any additional memory, aside from the input list and a few variables to keep track of the current index.

For the recursive method, the space complexity is O(n), meaning the memory required grows linearly with the size of the input list. This is due to the recursive function calls, which add layers to the call stack for each element in the list. A larger list requires more memory to store those calls, making the recursive approach less space-efficient.

Real-World Applications of Linear Search

While linear search may not be the most efficient algorithm for large datasets, it has practical uses in many scenarios. Let’s take a look at some situations where linear search is the best tool for the job.

Small datasets where sorting is not practical

Linear search is often my go-to when dealing with small datasets that aren’t worth the time or resources to sort. In these cases, the simplicity of linear search can be more efficient than the overhead of sorting the data for more complex search algorithms.

Finding the first occurrence of a target

Another common use case for linear search is when you need to find the first occurrence of a target value. Since linear search moves through the list one element at a time, it naturally finds the first instance of the target and returns its position. This can be especially useful in cases like searching through a string for the first appearance of a character.

When minimal setup is needed

Sometimes, the simplicity of linear search makes it the best option. For example, if you’re quickly searching through data that you don’t expect to reuse or you need a back-of-the-envelope answer quickly, linear search’s minimal setup can save you time.

Linear Search vs. Other Search Algorithms

Linear search is only one of many search algorithms out there. Let’s look at two other common search algorithms: binary search and hash lookup.

Linear search vs. binary search

Binary search is an algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. It has a time complexity of O(log n), making it far more efficient than linear search. However, it only works on sorted data. When your dataset is sorted, binary search is almost always the better choice because it cuts the search space in half with each step, drastically reducing the number of comparisons needed to find the target.

Linear search can be more appropriate in situations where your data is unsorted, since linear search works on any dataset, sorted or not. However, with a time complexity of O(n), linear search is much less efficient on sorted datasets.

Linear search vs. hash lookup

Hash lookup is a method that uses a hash table to quickly find an element. With a time complexity of O(1), it is significantly faster than either linear or binary search. However, this speed comes at a cost: you need to first build a hash table, which requires both time and additional memory. Hash lookups work best when you need to search through large datasets multiple times so that the initial setup pays off over time.

In contrast, linear search requires no setup, making it a more straightforward option. It is the better choice when you only need to search once or just a few times, where the extra time to set up a hash table isn’t justifiable. Linear search can also be more space-efficient because you don’t need to store a hash table to use the algorithm.

Common Pitfalls and How to Avoid Them

While linear search is a straightforward algorithm, there are a few common mistakes to watch out for.

Off-by-one errors in iteration

One of the most frequent mistakes when implementing a linear search is an off-by-one error. This is caused by starting or stopping the iteration at the wrong index. It’s important to remember that Python lists are zero-indexed, meaning the first element has an index of 0. Forgetting this may lead you to accidentally skip the first element or iterate one step too far, leading to incorrect results or errors.

Misunderstanding the index returned

Another common pitfall is misunderstanding what the function returns when the target isn’t found in the list. By convention, many search algorithms (including linear search) return -1 to indicate that the target is not present. However, some beginners might assume it returns None, False, or some other value, leading to confusion when interpreting results.

When not to use linear search

As we mentioned earlier, linear search quickly becomes inefficient for larger datasets. For this reason, it is best reserved for small, unsorted datasets or quick, one-time searches.

Conclusion

As one of the most straightforward search methods, linear search checks each element in a list sequentially, making it easy to understand and implement. Linear search is a reliable choice for quick, one-time searches on small datasets, particularly when the data is unsorted.

If you’re interested in search algorithms, check out my other articles in this series: Binary Search in Python, Depth-First Search in Python, and Breadth-First Search in Python. You may also be interested in AVL Tree: Complete Guide With Python Implementation and Introduction to Network Analysis in Python as more advanced topics.