Skip main navigation

Implementing linear search

How can linear search be implemented in Python? In this article, James Robinson gives you advice to go from the algorithm to a working program.

In this step you’re going to implement your own basic version of linear search, and then write a more efficient algorithm that is optimised to work on sorted lists.

The algorithm in English

To begin with, we can write a structured English version of the algorithm, just as we did for bubble sort. You can then turn this into your linear_search function.

  1. Take a sequence of integers and a value that is being searched for.
  2. Iterate over the length of the list, using position to keep track of the item in the list being looked at.
  3. If the item at the position in the sequence is equal to the value being searched for, return the position.
  4. If the entire sequence has been iterated over, and the value has not been found, then return False.

Implementing the algorithm

A quick note, before you get started: there are three main ways to iterate over a list of values, and keep track of your position in the list. Have a look at the examples below, and you can choose the method you are most comfortable with.

This first example uses a while loop along with a counter variable called position. The loop repeats and increments the position variable until it matches the last element of the list.

sequence = ['A','B','C','D']

#Example 1 - A while loop
position = 0
while position < len(sequence):
print(sequence[position], "is at position", str(position))
position += 1

The second example does exactly the same thing, but using a for loop. The duration of the loop is set to the length of the list.

#Example 2 - A for loop over a range
for position in range(len(sequence)):
print(sequence[position], "is at position", str(position))

This final example is specific to Python, which has a built in function enumerate. This function maps a number to each list item, and means you don’t need a separate counter variable. While this looks very similar to the previous example, it also allows you to do some clever things. For example enumerate(sequence,1) would label each element starting at 1 rather than 0, which might be useful for communicating the position to human beings.

#Example 3 - The enumerate function
for position, item in enumerate(sequence):
print(item, "is at position", position)

Now have a go at implementing your own linear search function, in a way that would work on an unsorted sequence of integers.

Share your code in the comments section and help each other out if anyone gets stuck.

Working with sorted lists

Now that you have implemented a basic search, its performance can be improved by altering it to work on sorted lists.

Remember you just need to add an extra conditional into your code, so that if the item in the list being looked at is larger than the value being searched for, then the function can return False.

Again, try this independently first, and ask for help in the comments if you need to.

This article is from the free online

Programming 102: Think Like a Computer Scientist

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education