Introduction

Self-taught developers tend to have a very pragmatic approach to software development. We learnt from projects, tutorials, practical courses, and technical books. There's nothing wrong with that. But, we're missing some of the fundamentals that traditional Computer Science majors get during their coursework. The goal of this series is to expose self-taught developers to algorithm design and anaylsis. This post covers Linear Search, one of the most commonly used algorithms in computer science.

Linear Search - O(n) Complexity

Search functions find the position of an item in a list. Linear Search is the simplest form of search. It simply starts at the beginning and examines every item until it finds a match. The worst case scenario would be when the item being searched for is at the very end of the list. Here's a visual representation of linear search across a 15 element sequence where we're looking for the value 9:

A home-grown linear search implementation in Python might look something like this:

my_list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

def linear_search(target, src_list):
    for i in range(0, len(src_list)):
        if src_list[i] == target:
          return i
    raise ValueError
    
linear_search(9, my_list)   # 8
linear_search(1, my_list)   # 0
linear_search(42, my_list)  # ValueError

However, as I've mentioned previously, most programming languages ship with common algorithms already built in. In Python, the Sequence Types implement the index() method, which performs a linear search similar to our homegrown solution.

my_list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

my_list.index(9)   # 8
my_list.index(1)   # 0
my_list.index(42)  # ValueError

# since strings Sequence Types, we can call index on them as well
'foobarbaz'.index('r')  # 5

# it's worth remembering that linear search returns the position of the first element it matches on
'foobarbaz'.index('b')  # 3

Summary

Conclusion

The fact that linear search works on unsorted lists is probably its most compelling feature. You'll use it all the time, and it's a great example of O(n) algorithmic complexity. Just remember, any time you have to look at every item in a sequence once (and only once), it's O(n).

As usual, feel free to hit me up on Twitter or send me a message on LinkedIn if you have any questions!