Skip main navigation

Linear search explained

Watch an animation explaining the linear search algorithm, narrated by James Robinson.
2.9
Linear search is a simple search algorithm to understand and implement. It involves checking each item in the list to see if it’s the right one. Let’s have a look at our shelf of sports balls again. The robot arm has been programmed with the linear search algorithm, and has been instructed to find the baseball. It looks at the size of the baseball in its database, and knows that the ball’s diameter is 76 millimetres. So the arm goes to the first ball on the shelf and checks the size of the ball. It’s 218 millimetres, so not the baseball. The arm then moves down to the next ball on the shelf and checks again.
40
This process continues until the correct ball has been found.
46.9
When the correct ball has been identified, it can be picked up by the arm. Whilst in this case finding the ball only took a few moves, it could have taken an incredibly long time if there were millions of balls to search through. The worst case for this algorithm is when the item being searched for isn’t there. Imagine if the robot arm had been told to find a ball that was 60 millimetres in diameter. There isn’t a ball of this size on the shelf. It would have to inspect every ball on the shelf before it could end its search.
82.7
So how could this algorithm be made more efficient? Well, what if we sorted the balls on the shelf first. Now if we asked to search for the ball that’s 60 millimetres in diameter, we can tweak the algorithm, and instruct the arm that if it finds a ball that is larger than 60 millimetres, it can stop its search. The arm is searching for a ball that is equal to or less than 60 millimetres in diameter, rather than exactly 60 millimetres.
112.4
In the next step, you’ll go to implement your own version of linear search using Python. Use the comment section below to check your understanding of the linear search algorithm.

Linear search is a simple search algorithm to understand and to implement. It just involves checking each item in a list in order (hence “linear”) to see if it’s the right one.

A set of 10 sports balls, with a robotic claw above them. The balls in order from the left are a bowling ball, a pool ball, a cricket ball, a ping-pong ball, a baseball, a golf ball, a basketball, a netball, a tennis ball and a soccer ball.

Let’s have a look at our shelf of sports balls again. The robot arm has been programmed with the linear search algorithm, and has been instructed to find the baseball. It looks up the size of a baseball in its database, and finds that the ball’s diameter is 76mm.

The arm goes to the first ball on the shelf and checks the size of the ball. It’s 218mm, so not the baseball. The arm then moves down to the next ball on the shelf, and checks again. If this ball is not the baseball, it will move down to the next ball, and check again. This pattern continues until the correct ball has been found and can be picked up by the arm.

An animated GIF showing the claw checking the size of the first five balls in turn, with the width shown on the claw for each one. The number is red for the first 4 balls, but green for the baseball.

While in this case finding the ball only took a few moves, it could have taken an incredibly long time if there were millions of balls to search through. The worst case for this algorithm is when the item being searched for isn’t there. Imagine if the robot arm had been told to find a ball that was 60mm in diameter. There isn’t a ball of this size on the shelf, and the robot would have to inspect every ball on the shelf before it could end its search!

How could this algorithm be made more efficient? We could try sorting the balls on the shelf by size before we searched. Then, if we needed to search for a ball that is 60mm in diameter, we could tweak the algorithm and instruct the arm that if it finds a ball larger than 60mm, it can stop its search. To enable it to do this, at each step, the arm will check if the ball is equal to or less than 60mm in diameter, not just if it is exactly 60mm.

In the next step, you’re going to implement your own version of linear search using Python. In the meantime, use the comments section to share other ideas for contexts or analogies that might help your students understand how linear search works, and its limits.

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